An Approach to the Knight’s Tour Problem Using 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

Abstract

The Knight's Tour is a well-known problem in graph theory and combinatorial optimization, where a knight moves across a chessboard visiting each square exactly once. This paper presents an approach based on Depth First Search (DFS) to explore possible knight's tours, analyzing its computational complexity and efficiency. We also discuss heuristic optimizations, such as Warnsdorff's Rule, to improve search performance. The results demonstrate the feasibility of using DFS for solving this NP-hard problem.

References

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.