Uma Abordagem para o Knight’s Tour Problem utilizando Depth First Search

• Bruno Kenzo Yui UFSCar
• Gabriel Andreazi Bertho UFSCar
• Karen Ketlyn Ferreira Barcelos UFSCar
• Rodrigo Takizawa Yamauchi UFSCar
• Helio Crestana Guardia UFSCar

DOI: https://doi.org/10.5753/eradsp.2025.9755

Resumo

Knight’s Tour é um problema clássico da teoria dos grafos e da otimização combinatória, no qual um cavalo deve percorrer um tabuleiro de xadrez e visitar cada casa exatamente uma vez. Este artigo apresenta uma abordagem para o problema baseada em Depth First Search (DFS) e outra usando método de Monte Carlo para explorar possíveis passeios do cavalo, e analisa suas complexidades computacionais e eficiências. Além disso, discutimos otimizações heurísticas, como a Regra de Warnsdorff, para melhorar o desempenho da busca. Os resultados demonstram a viabilidade do uso de DFS para resolver esse problema NP-difícil.

Referências

Warnsdorff, H.C. (1823). Des Rösselsprungs einfachste und allgemeinste Lösung. Schmalkalden. Schwenk, A. (1991). Which rectangular chessboards have a knight’s tour? Mathematics Magazine, 64(5), 325-332.

Demaine, E.D., Demaine, M.L., Kominers, S.D., Lynch, J., & Lynch, N. (2022). Taming the Knight’s Tour: Minimizing Turns and Crossings. Theoretical Computer Science, 921, 88–97.

Conrad, K., Hindman, N., & Schaar, J. (2005). Optimal Algorithms for Constructing Knight’s Tours on Arbitrary n × m Boards. Discrete Applied Mathematics, 145(2), 236–243.