The eight queens puzzle places eight queens on a chessboard so that no two attack horizontally, vertically, or diagonally. A recursive backtracking search explores the board one column at a time. section 15.9
The search proceeds by:
- Trying safe rows from top to bottom in the current column. section 15.9
- Recursing into the next column after placing a queen. section 15.9
- Backtracking when no safe position remains, then removing the previous queen and trying another path. section 15.8 section 15.9
- Printing a solution when the rightmost column is safely occupied; continuing afterward finds additional solutions. section 15.9
Python implementation
A Queens class stores occupied squares in a Boolean matrix. find_solutions() starts recursion at column 0; _is_safe_position() checks earlier rows and diagonals. The search produces 92 solutions, including reflections and rotations. section 15.9
Figure 15.15 A decision tree showing recursion to move from one stage to the next and backtracking to try other paths in earlier stages
Use the decision tree to trace recursive advances, dead ends, and returns to earlier stages. section 15.8
