Lecture Notes: Backtracking and the Eight Queens Problem

Introduction to Backtracking

• Many problems require systematic searching through possibilities to find a solution.
• Solutions can be built incrementally, but hitting a dead end may require backtracking.
• Example: Solving a Sudoku puzzle by filling in numbers and backtracking if a number doesn't work.

The Eight Queens Problem

• Problem Statement: Place 8 queens on a chessboard so that no queens attack each other.
• Queen's Attack Range: A queen attacks all squares in its row, column, and diagonals.
  • Example: A queen at (3, 3) attacks all squares in its row 3, column 3, and both diagonals.
• Generalization: Can we place n queens on an n x n chessboard?
  • Trivial Case: n = 1 (one square).
  • Impossible Cases: n = 2 and n = 3.
    • For n = 2: Any queen placed attacks all remaining squares.
    • For n = 3: Placing the first queen blocks options for the others.
  • Possible Cases: n = 4 and higher.
    • Example for n = 4: A configuration exists where no queens attack each other.

Approach to Solve the Eight Queens Problem

• Constraints: One queen per row and column.
• Method: Place queens row by row, attempting to find valid positions.
• Backtrack when no valid placement is available.

Steps in the Backtracking Process

1. Start with an empty board and place a queen in the first row.
2. Move to the next row and attempt to place the next queen in the first available column.
3. If you reach a row where no valid placements exist, undo the last move (backtrack) and try a different position.
4. Repeat until all queens are placed or all options are exhausted.

Data Structure Representation

• Board Representation: Use a 1D array to represent the column positions of queens in each row.
• Attack Tracking: Maintain arrays to track attacked rows, columns, and diagonals.
  • Row attacks: row[i] = 1 if row i is attacked.
  • Column attacks: column[j] = 1 if column j is attacked.
  • Diagonal attacks:
    • Main diagonal (j - i): Represents northwest to southeast.
    • Anti diagonal (j + i): Represents southwest to northeast.
• Check if position (i, j) is free by checking corresponding arrays.

Python Implementation Overview

• Functions:
  • Initialize Board: Create a nested dictionary for tracking queens and attacks.
  • Place Queen: Attempts to place a queen at (i, j) and updates the board.
  • Undo Queen: Removes a queen and resets the board state.
  • Check Free Position: Verifies if placing a queen at a position is valid.
  • Print Board: Displays the board configuration of queens.
• Recursive Function: Attempts to place queens until a solution is found or all options are exhausted.

Finding All Solutions

• Instead of stopping after the first valid solution, modify the implementation to find and print all possible solutions by continuing the search.
• The final version of the code is capable of printing all unique configurations of 8 queens on the board.

Conclusion

• Backtracking is a systematic way to search for solutions in constraint satisfaction problems like the Eight Queens Problem.
• The presentation provided insight into the approach, data structures, and a practical implementation in Python.