Knight's Tour

The Knight's Tour requires a chess knight to visit every square on a board (typically 8×8) exactly once using only legal L-shaped knight moves. It is an example of a Hamiltonian path problem in graph theory. Solutions have been documented as far back as the 9th century by Arab mathematician al-Adli ar-Rumi.

An open tour ends on a square from which the knight cannot legally jump back to the starting square, while a closed tour (or re-entrant tour) finishes one knight's move away from the start, forming a complete loop. On a standard 8×8 board, both types of solutions exist and have been studied for centuries.

Yes, the puzzle can be attempted on boards of various sizes, but solutions do not exist for every dimension. For example, a closed tour is impossible on a 4×4 board, while 5×5 and 6×6 boards each have known solutions under certain conditions.

Backtracking is the most straightforward computational approach, but Warnsdorff's heuristic—always moving the knight to the square with the fewest onward moves—is far more efficient. Neural networks and divide-and-conquer methods have also been used to generate tours on large boards.