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 the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
