Entendendo o jogo do cavaleiro na prática
O jogo do cavaleiro, ou problema do cavalo, é um desafio clássico de tabuleiro onde você precisa mover um cavalo de xadrez por todas as casas de um tabuleiro sem repetir nenhuma. Parece simples quando ouve pela primeira vez, mas a complexidade cresce rápido. Num tabuleiro 8x8 padrão, existem bilhões de possibilidades de caminhos, e a maioria deles leva a um beco sem saída nas últimas casas. A solução mais usada no dia a dia é o algoritmo de Warnsdorff, que simplesmente prioriza movimentos que têm menos saídas possíveis. Você olha para cada movimento disponível, conta quantas casas cada um leva, e escolhe o que tem menos opções de continuidade. Funciona surpreendentemente bem na maior parte dos casos.
jogo do cavaleiro: como resolver passo a passo
Eu comecei a trabalhar com isso faz alguns anos, tentando implementar solucionadores para um projeto interno. A primeira coisa que você aprende é que não adianta tentar força bruta. Uma DFS ingênua num tabuleiro 8x8 pode levar horas ou dias dependendo da implementação. Eu passei duas semanas tentando otimizar um backtracking puro antes de finalmente aceitar que precisava de heurística. O método prático funciona assim. Você inicia o cavalo numa casa qualquer, depois em cada turno você identifica todos os movimentos válidos do cavalo — até oito possíveis em teoria, embora nas bordas e cantos esse número caia bastante. Para cada movimento válido, você calcula quantos movimentos válidos existem a partir da casa de chegada. Você ordena essas opções em ordem crescente e segue a de menor valor. Esse é o_warnsdorff_ básico.
👉 Clique no botão abaixo para saber mais sobre o assunto!
O que muita gente não sabe é que oWarnsdorff_ simples tem uma falha conhecida. Existem posições onde a heurística engana e você acaba travado perto do final. No meu caso, o problema apareceu quando eu estava gerando tours completos num tabuleiro 8x8 a partir de certos pontos de partida específicos. O algoritmo preenchia cerca de 58 a 64 casas e depois travava, mesmo restarem dezenas de casas livres. A solução foi adicionar uma verificação de conectividade: antes de fazer cada movimento, eu verificava se a casa de destino ainda mantinha o grafo de movimentos restantes conexo. Se um movimento isolasse qualquer casa não visitada, eu descartava essa opção. Isso aumentou o tempo médio de resolução de cerca de 3 segundos para 45 segundos num processador comum, mas a taxa de sucesso subiu de 60% para algo próximo de 99%. Se você quer apenas jogar ou visualizar o problema sem programar, existem várias implementações disponíveis online. A maioria dos projetos em Python no GitHub resolvem o problema, e há versões em JavaScript que rodam direto no navegador. Procure por knight's tour solver ou jogo do cavaleiro solver para encontrar opções úteis. O código costuma ser entre 50 e 150 linhas, dependendo se inclui interface gráfica ou apenas a lógica pura.
O que poucas pessoas mencionam é que o jogo do cavaleiro fechado — aquele em que o cavalo termina numa casa que permite retornar à posição inicial com um único movimento — é significativamente mais restritivo. Encontrar um tour fechado exige verificações adicionais no final do algoritmo, e a taxa de sucesso cai drasticamente. Meu workaround foi rodar o Warnsdorff múltiplas vezes com sementes diferentes e filtrar apenas os resultados que também satisfazem a condição de fechamento. Em média, são necessárias cerca de 200 a 500 tentativas para encontrar um tour fechado válido a partir de uma dada posição inicial. Se o seu objetivo é apenas resolução rápida e você não se importa com tours fechados, o Warnsdorff básico resolve em milissegundos. Se precisa de garantias matemáticas completas, considere usar um solver especializado como o z3 ou até uma abordagem SAT, mas aí o tempo de computação salta para dezenas de segundos ou minutos. Para a grande maioria dos casos práticos, o Warnsdorff com a correção de conectividade é o ponto ideal entre velocidade e confiabilidade. Vou parar por aqui, já disse o suficiente sobre o assunto.
