Implementação e visualização computacional do problema do tour do cavalo em tabuleiro 8×8
uma abordagem algorítmica e análise matemática
DOI:
https://doi.org/10.47385/tudoeciencia.2566.2025Palavras-chave:
Tour do Cavalo. Problema Hamiltoniano. Algoritmos de Busca. Visualização Computacional. Teoria dos Grafos.Resumo
O presente trabalho apresenta uma implementação computacional e análise matemática do clássico problema do Tour do Cavalo em um tabuleiro de xadrez 8×8. O problema, que consiste em encontrar uma sequência de movimentos válidos do cavalo que visite todas as 64 casas do tabuleiro exatamente uma vez, representa um caso particular do problema do caminho hamiltoniano em grafos. Utilizando a linguagem de programação Python com as bibliotecas NumPy e Matplotlib, foi desenvolvida uma solução que não apenas encontra um tour válido, mas também fornece uma visualização gráfica completa da sequência de movimentos. A metodologia empregada combina representação matricial do tabuleiro com algoritmos de busca sistemática, resultando em uma solução completa que inicia na posição (0,0) e termina na posição (7,0), percorrendo todas as 64 casas em uma sequência numerada de 0 a 63. Os resultados obtidos demonstram a viabilidade da abordagem computacional para resolver este problema NP-completo, fornecendo insights sobre a estrutura matemática subjacente e as propriedades geométricas dos movimentos do cavalo no tabuleiro de xadrez.
Downloads
Referências
BERGHOLT, E. Knight's tour notes. British Chess Magazine, v. 38, p. 404-407, 1918.
CONRAD, A.; HINDRICHS, T.; MORSY, H.; WEGENER, I. Solution of the knight's Hamiltonian path problem on chessboards. Discrete Applied Mathematics, v. 50, n. 2, p. 125-134, 1994.
DE JAENISCH, C. F. Applications de l'analyse mathématique au jeu des échecs. St. Petersburg: Imprimerie de l'Académie Impériale des Sciences, 1862.
DIESTEL, R. Graph theory. 5th ed. Berlin: Springer-Verlag, 2017.
EULER, L. Solution d'une question curieuse qui ne paroit soumise à aucune analyse. Mémoires de l'Académie Royale des Sciences et Belles Lettres de Berlin, v. 15, p. 310-337, 1759.
HOOPER, D.; WHYLD, K. The Oxford companion to chess. 2nd ed. Oxford: Oxford University Press, 1992.
HUNTER, J. D. Matplotlib: A 2D graphics environment. Computing in Science & Engineering, v. 9, n. 3, p. 90-95, 2007.
OLIPHANT, T. E. A guide to NumPy. Spanish Fork: Trelgol Publishing, 2006.
PARBERRY, I. An efficient algorithm for the knight's tour problem. Discrete Applied Mathematics, v. 73, n. 3, p. 251-260, 1997.
SQUIRREL, D.; CULL, P. A Warnsdorff-rule algorithm for knight's tours on square boards. In: COMPUTING AND COMBINATORICS CONFERENCE, 2., 1996, Hong Kong. Proceedings... Berlin: Springer-Verlag, 1996. p. 268-276.
TUFTE, E. R. The visual display of quantitative information. 2nd ed. Cheshire: Graphics Press, 2001.
WARNSDORFF, H. C. Des Rösselsprungs einfachste und allgemeinste Lösung. Schmalkalden: Varnhagen, 1823.
WATKINS, J. J. Across the board: the mathematics of chessboard problems. Princeton: Princeton University Press, 2004.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2025 Tudo é Ciência: Congresso Brasileiro de Ciências e Saberes Multidisciplinares
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
