A simple recursive backtracking algorithm for knight's tours puzzle on standard 8×8 chessboard

摘要

In this paper, we propose a simple recursive backtracking algorithm and compare its performance against existing algorithms for a classical chessboard puzzle in recreational mathematics known as knight's tour on standard or regular 8×8 square chessboard. In this work, we re-investigate this celebrated problem with the help of modern computer. Our algorithm is easy to implement compared to other existing algorithms for knight's tour puzzle. It has previously been proven that a knight's tour is always possible for sufficiently large sized chessboards either rectangular or square, but the novelty of our work lies in its simplicity and the fact that here we restrict knight's tour for 8×8 chessboard only.