Passeio do cavalo. Um dos desafios mais interessantes que os jogadores de xadrez enfrentam é o problema do Passeio do Cavalo, proposto originalmente pelo matemático Euler. O problema é o seguinte: a peça do xadrez chamada cavalo pode se movimentar por um tabuleiro vazio e tocar cada um dos 64 quadrados uma e somente uma vez? Estudaremos esse problema interessante em detalhes. O cavalo se movimenta em forma de L (por duas casas em uma direção e depois por uma casa em uma direção perpendicular). Assim, por um quadrado no meio de um tabuleiro vazio, o cavalo pode fazer oito movimentos diferentes (numerados de 0 a 7), como mostra a Figura 6.25.

Passo 1

Beleza pessoal, espero que todos estejam bem por ai. Hoje iremos resolver mais uma atividade então é bom estarem com seu compilador aberto para podermos iniciarmos.

  1. Estime o número de movimentos que você fará. Um palpite nos anos vinte deve ser factível.
  2. Em primeiro lugar, haverá 4 funções.
  3. A função checkCoord verificará se o cavalo está fora dos limites.

    A função de atualização marcará o local atual do cavaleiro como visitado e marcará o novo local como atual. Também mudará a posição das variáveis currentRow e currentColumn do cavaleiro.

    As funções checkCoord e update:

    Passo 2

    A função makeMove percorrerá todos os movimentos possíveis e depois verificará se o movimento é legal (o cavalo não sai do tabuleiro), usando a função checkCoord.

    Também verificará se o local de destino já foi ocupado. Uma vez que um movimento é feito, ele atualizará o tabuleiro usando a função de atualização.

    A função makeMove:

    A função knightsTour moverá o cavalo enquanto houver um movimento disponível.

    A função knightsTour:

    Passo 3

    horizontal e vertical são usados para combinações de movimentos, conforme explicado no livro. O resto é autoexplicativo.

  4. Em primeiro lugar, marcaremos a casa em que o cavalo está atualmente com 1001 e uma casa visitada com 1000. Em seguida, definiremos 3 novas funções.

    A função updateBoardAccess percorre todo o quadro e chama updateSquareAccess para aumentar o número de acessibilidade daquele quadrado.

    O número de acessibilidade é o número de quadrados a partir dos quais o quadrado atual pode ser alcançado. Isso é feito para alcançar a abordagem heurística de acessibilidade descrita na tarefa.

    As funções:

    A terceira função é decreaseAcessonde serão passadas as coordenadas para as quais o cavalo se moverá. Em seguida, a função diminuirá a acessibilidade para cada quadrado alcançável a partir do novo quadrado.

    A função:

    O cavalo fez 63 lances, então visitou todas as 64 casas, quando a primeira casa é o canto superior esquerdo.

    O cavalo faz 63 movimentos de quase todas as 64 casas.

  5. Adicionaremos uma função findMin que olhará para frente e verificará qual quadrado tem a menor acessibilidade do quadrado fornecido.

A função:

Também teremos que modificar a função makeMove.

O código adicionado:

Resposta

Ver todo o desenvolvimento!!