N-Queens Problem

Introduction

The N-Queens problem is one of the most famous problems in computer science and combinatorics. The challenge is to place N chess queens on an N x N chessboard so that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal. The problem was first posed for 8 queens by chess player Max Bezzel in 1848, and the first solutions were published by Franz Nauck in 1850.

The N-Queens problem serves as a benchmark for constraint satisfaction and backtracking algorithms. It illustrates how intelligent pruning of the search space can make seemingly intractable problems solvable in reasonable time. The problem also has deep connections to group theory, combinatorial optimization, and the theory of Latin squares.

For N = 1, the problem is trivial. For N = 2 and N = 3, no solution exists. For N = 4, there are exactly 2 fundamentally distinct solutions. The number of solutions grows rapidly with N, and counting the exact number of solutions for large N remains an open research problem.

Problem Definition

Given an N x N chessboard, place N queens such that:

1. No two queens are in the same row
2. No two queens are in the same column
3. No two queens are on the same diagonal (both main and anti-diagonals)

Number of Solutions for Small N

Two solutions are considered fundamentally distinct if one cannot be obtained from the other through rotations and reflections of the board. Each fundamentally distinct solution generates up to 8 variants through the symmetry group of the square.

Backtracking Solution

The standard backtracking approach places queens one row at a time. Since each row must contain exactly one queen, we try placing a queen in each column of the current row, check whether the placement is safe, and if so, recursively proceed to the next row. If no valid column exists, we backtrack to the previous row and try the next column.

Pseudocode

procedure SolveNQueens(board, row, N): if row == N: recordSolution(board) return for col from 0 to N-1: if isSafe(board, row, col): board[row] = col // place queen at (row, col) SolveNQueens(board, row + 1, N) board[row] = -1 // backtrack

The board can be efficiently represented as a one-dimensional array where board[i] stores the column index of the queen in row i. This representation automatically ensures no two queens share a row, so only column and diagonal conflicts need to be checked.

Constraint Checking

The isSafe function checks whether placing a queen at position (row, col) conflicts with any previously placed queen. Three conditions must hold:

Column Check

No queen in any previous row occupies column col. Formally: board[i] != col for all i < row.

Diagonal Check

Two squares (r1, c1) and (r2, c2) lie on the same diagonal if and only if |r1 - r2| == |c1 - c2|. This covers both the main diagonal (top-left to bottom-right) and anti-diagonal (top-right to bottom-left).

Efficient Constraint Tracking with Bit Manipulation

procedure SolveNQueensBits(row, columns, diag1, diag2, N): if row == N: count = count + 1 return availablePositions = ((1 << N) - 1) & ~(columns | diag1 | diag2) while availablePositions != 0: position = availablePositions & (-availablePositions) // lowest set bit availablePositions = availablePositions - position col = log2(position) SolveNQueensBits(row + 1, columns | position, (diag1 | position) << 1, (diag2 | position) >> 1, N)

This bit-manipulation approach uses three bitmasks to track occupied columns, main diagonals, and anti-diagonals. It is significantly faster than array-based checking because bitwise operations replace inner loops.

Worked Example

Solving the 4-Queens problem step by step:

Step 1: Place queen in row 0, column 0. Board: [0, -, -, -]

Step 2: Row 1: column 0 blocked (same column), column 1 blocked (diagonal). Try column 2. Board: [0, 2, -, -]

Step 3: Row 2: columns 0, 1, 2, 3 are all blocked by queens at (0,0) and (1,2). Backtrack.

Step 4: Back to row 1. Try column 3. Board: [0, 3, -, -]

Step 5: Row 2: column 1 is safe. Board: [0, 3, 1, -]

Step 6: Row 3: columns 0, 1, 2 blocked. Column 3 blocked (same column as row 1). No valid column. Backtrack.

Step 7: Backtrack to row 0. Try column 1. Board: [1, -, -, -]

Step 8: Row 1: column 3 is safe. Board: [1, 3, -, -]

Step 9: Row 2: column 0 is safe. Board: [1, 3, 0, -]

Step 10: Row 3: column 2 is safe. Board: [1, 3, 0, 2]. Solution found.

Solution 1: Solution 2:. Q . . . . Q .. . . Q Q . . .Q . . . . . . Q. . Q . . Q . .

Finding All Solutions

To find all solutions, the backtracking algorithm does not stop after recording the first valid placement. Instead, it continues to explore the remaining columns after each solution is found.

Exploiting Symmetry

The solution count can be halved by observing that if a placement is a valid solution, so is its reflection. We can restrict the first queen to the left half of the board (columns 0 through floor(N/2) - 1) and multiply the count by 2. For odd N, placements in the middle column must be counted separately.

Further reductions are possible using all eight symmetries of the square (the dihedral group D4), reducing the search space by up to a factor of 8 for finding fundamentally distinct solutions.

Complexity Analysis

The upper bound of N! arises because the column constraint already limits choices: at most N columns in row 0, and for each queen placed, one column is eliminated. However, the diagonal constraints eliminate even more options, so the actual number of nodes explored is significantly smaller than N! for most instances.

Optimizations and Pruning

Bit-Manipulation Approach

As shown above, using three bitmasks (columns, main diagonals, anti-diagonals) replaces O(N) constraint checking with O(1) bitwise operations. This approach was popularized by Jeff Somers and can enumerate all solutions for N = 26 and beyond.

Forward Checking

Instead of only checking whether the current placement is safe, forward checking also examines whether placing a queen at (row, col) leaves at least one valid column in every subsequent row. If any future row has no available column, the current placement is rejected immediately.

Permutation-Based Search

Since the solution is a permutation of column indices (each column appears exactly once), the problem reduces to finding permutations of {0, 1, ..., N-1} that satisfy the diagonal constraints. This automatically eliminates row and column conflicts and reduces the search space from N^N to N! before any diagonal pruning.

The N-Queens problem is often used to benchmark constraint satisfaction solvers and SAT solvers. Modern solvers can handle N = 1,000,000 and beyond by using constructive methods that avoid exhaustive search entirely.

Applications

• VLSI Testing: The N-Queens problem models certain routing and placement constraints in integrated circuit design.
• Parallel Memory Storage: Solutions to the N-Queens problem correspond to schemes for storing data in parallel memory so that various access patterns avoid bank conflicts.
• Constraint Satisfaction: The problem serves as a standard benchmark for evaluating CSP algorithms, including arc consistency, backjumping, and conflict-directed backtracking.
• Load Balancing: Queen placements correspond to non-attacking rook placements with additional constraints, relevant to assigning tasks to processors without conflicts.
• Error-Correcting Codes: Connections exist between N-Queens solutions and certain classes of permutation codes used in coding theory.

References

• Bezzel, M. "Proposal of the Eight Queens Problem." Berliner Schachzeitung, 1848.
• Nauck, F. "Schach, eine Abhandlung." Illustrirte Zeitung, 1850.
• Gauss, C. F. Correspondence with Schumacher on the Eight Queens Problem, 1850.
• Hoffman, E. J., Loessi, J. C., and Moore, C. M. "Constructions for the Solutions of the m Queens Problem." Mathematics Magazine, vol. 42, 1969, pp. 66-72.
• Sosic, R. and Gu, J. "Efficient Local Search with Conflict Minimization: A Case Study of the n-Queens Problem." IEEE Transactions on Knowledge and Data Engineering, vol. 6, 1994, pp. 661-668.
• Bell, J. and Stevens, B. "A Survey of Known Results and Research Areas for n-Queens." Discrete Mathematics, vol. 309, 2009, pp. 1-31.