Chapter 9. Implicit Graphs: A Knight’s Tour

The knight’s-tour problem is as follows: Find a path for a knight to touch all of the squares of an n × n chessboard exactly once. The knight’s tour is an example of a Hamiltonian path—that is, a simple closed path that passes through each vertex of the graph exactly once (where each square of the chessboard is treated as a vertex in the graph). The edges of the graph are determined by the pattern in which a knight can jump (for example, up two and over one). In this section, we use a generic backtracking search algorithm to find the knight’s tour. The backtracking algorithm is a brute-force algorithm and quite slow, so we also show an improvement to the algorithm using Warnsdorff’s heuristic [46

Get The Boost Graph Library: User Guide and Reference Manual now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.