N-Queens Problem Lecture Notes

Introduction

• The N-Queens problem involves placing N queens on an N x N chessboard.
• The objective is to arrange the queens such that no two queens threaten each other.
  • Queens can attack in the same row, column, or diagonal.

Problem Setup

• Example: 4-Queens problem on a 4 x 4 chessboard (16 cells).
• A standard chessboard has a dimension of 8 x 8.
• We need to find all arrangements of 4 queens on the 4 x 4 board without them being under attack.

Backtracking Approach

• Backtracking is a key technique used to find all possible solutions, not just one.
• It systematically explores the possible placements of queens.
• To reduce complexity, we fix the position of the first queen in each row.

Placement Strategy

• We will place the queens in different columns of each row.
• Primary conditions to avoid:
  1. No two queens in the same row.
  2. No two queens in the same column.
  3. No two queens on the same diagonal.

State Space Tree Generation

• The problem is visualized as a state space tree where:
  • Each node represents a placement of a queen.
  • The branches represent possible placements of queens in subsequent rows.

Example of Node Generation

• Starting with queen 1 in the first column, explore placements for queen 2 in subsequent columns.
• Continue this for all four queens, tracking all node possibilities.
• Example:
  • Placements of queens generate several nodes:
    • 1st Row: 4 options
    • 2nd Row: 3 options for each of the first row options
    • Continuation leads to multiple combinations.

Total Nodes Calculation

• For each queen placed, the number of nodes can be determined:
  • Formula:
    • Total nodes = 4 (choices for 1st queen) x 3 (choices for 2nd) x 2 (choices for 3rd) x 1 (choice for 4th) = 24 nodes.
• This count gives a maximum idea of potential configurations.

Applying the Bounding Function

• The bounding function checks for validity (no attacks between queens):
  • Start with queen 1 at a column.
  • Validate placements of subsequent queens based on the above conditions.

Example of Backtracking Process

1. Place queen 1 in the first column.
2. Attempt to place queen 2 in the second column (not valid if under attack).
3. Move to next column and check validity (continue until all queens are placed or backtrack).
4. Identify a valid arrangement (e.g., positions 2, 4, 1, 3).
5. Explore all possible configurations, including mirror images, until all solutions are found.

Solutions Found

• Two valid configurations found:
  1. (2, 4, 1, 3)
  2. (3, 1, 4, 2)

Conclusion

• The N-Queens problem illustrates the use of backtracking and state space trees efficiently.
• The bounding function is critical in pruning the search space to find valid configurations.
• Emphasis on finding all solutions rather than just one.