N Queens Problem Algorithm - All Solving Methods

The N queens problem asks: how many ways can N non-attacking queens be placed on an N×N chessboard? It is a fundamental benchmark problem in combinatorial optimization and artificial intelligence. Different algorithms tackle it with very different trade-offs between completeness, optimality, and speed.

Key dimensions to compare algorithms:

• Complete: Does it guarantee finding all solutions?
• Optimal: Does it find a solution (or best solution) in minimum time?
• Scalability: How does runtime grow with n?
• Implementation complexity: How hard is it to implement correctly?

For most use cases — finding all solutions, education, or interview prep — backtracking is the right choice. For finding a single solution quickly in large n, min-conflicts heuristic is often fastest. For exploring the problem from an AI perspective, see the 8 Queens in AI guide.

The naivest approach: enumerate every possible placement of n queens on n² cells, checking each configuration for validity. This gives O(n^n) time complexity — for n=8 that is 8^8 = 16,777,216 configurations to check, most of them wildly invalid.

A slightly smarter brute force restricts to permutations of column assignments (one queen per row, one per column), yielding n! possibilities. For n=8 this is 8! = 40,320 — still much worse than backtracking in practice because it does not prune early.

Pseudocode:

for each permutation P of [0..n-1]:
    if noTwoDiagonalConflicts(P):
        record P as a solution

Verdict: Only suitable for educational illustration of why optimization matters. Never use for n > 8.

Backtracking is the standard algorithm for the N queens problem. It builds solutions incrementally, abandoning partial solutions ("pruning") as soon as a constraint violation is detected. This reduces the effective search space from O(n^n) to approximately O(n!) and in practice to far fewer nodes.

Key insight: By placing exactly one queen per row, we eliminate row conflicts by design. The isSafe check then only needs to verify column and diagonal conflicts with already-placed queens.

Pseudocode:

function backtrack(board, row):
    if row == n: record solution; return
    for col in 0..n-1:
        if isSafe(board, row, col):
            board[row] = col
            backtrack(board, row+1)
            board[row] = -1  // undo

For complete language-specific implementations, see: Python, Java, C++, JavaScript.

Verdict: Best general-purpose algorithm for finding all solutions. Fast for n ≤ 15, feasible for n ≤ 20 with bitwise optimization.

Branch and bound extends backtracking by also tracking a lower bound on the number of conflicts in unexplored subtrees. When a subtree's lower bound exceeds the best-known solution quality, that branch is pruned.

For the N queens problem (where we want exact solutions, not approximate), the distinction from plain backtracking is subtle. The main enhancement is forward checking: after placing a queen, immediately compute which cells in remaining rows become unavailable. If any row has zero available columns, backtrack immediately rather than waiting to reach that row.

Forward checking pseudocode:

function solveFC(board, row, available[]):
    if row == n: record solution; return
    for col in available[row]:
        place queen at (row, col)
        newAvail = propagate constraints to rows row+1..n-1
        if all rows have at least 1 available cell:
            solveFC(board, row+1, newAvail)
        remove queen from (row, col)

Verdict: Forward checking typically reduces recursive calls by 2–5× compared to basic backtracking, especially for large n. More complex to implement but worth it for n ≥ 12.

Constraint propagation, used in full Constraint Satisfaction Problem (CSP) solvers, applies arc consistency algorithms (AC-3) to aggressively reduce variable domains before and during search. The N queens problem maps cleanly to CSP:

• Variables: Q₁, Q₂, ..., Qₙ (one per row)
• Domains: Each variable has domain {0, 1, ..., n-1} (columns)
• Constraints: All-different constraints for columns and both diagonal expressions

AC-3 propagates constraints between pairs of variables. When a queen is placed in column c, row r, the algorithm removes c from the domains of all later rows, removes r-c from the domains (via the main diagonal constraint), and removes r+c via the anti-diagonal constraint. This can reduce domains to size 1 or 0, triggering immediate assignment or backtracking.

Libraries like Python's python-constraint or Prolog's built-in CLP(FD) implement this automatically, reducing the N queens problem to a few lines of declarative code.

Verdict: Powerful for large CSPs. For N queens specifically, the overhead of AC-3 bookkeeping can make it slower than optimized backtracking for small n, but faster for n ≥ 20.

Local search algorithms start with a complete (but likely conflicting) assignment and iteratively improve it. They are incomplete (not guaranteed to find all solutions) but can find a single solution very quickly for large n.

Min-Conflicts Heuristic:

1. Place n queens randomly (one per row, one per column).
2. Pick the queen with the most conflicts.
3. Move it to the column in its row with the fewest conflicts.
4. Repeat until no conflicts remain.

Min-conflicts finds a solution for n=1,000,000 in roughly n steps on average — nearly constant time regardless of board size. It is the algorithm of choice when you only need one solution, not all of them.

Simulated Annealing adds a temperature parameter that allows occasional "bad" moves, helping escape local optima. It is more robust than pure min-conflicts but harder to tune. For a detailed treatment, see the 8 Queens in AI guide.

Verdict: Best for finding a single solution quickly for large n. Not suitable when you need all solutions.

Genetic algorithms (GAs) model evolution: maintain a population of candidate solutions, select the fittest, combine them via crossover, and introduce mutations. For N queens:

• Chromosome: A permutation of [0..n-1] representing column positions
• Fitness: Number of non-attacking queen pairs (max = n*(n-1)/2)
• Crossover: PMX (Partially Mapped Crossover) to preserve permutation validity
• Mutation: Swap two column values

GAs are not competitive with backtracking for exact enumeration, but they illustrate evolutionary computation principles clearly. For a complete Python implementation, see the Genetic Algorithm guide.

Verdict: Educational value high; practical performance for exact enumeration low. Better suited for approximate or large-n single-solution scenarios.

* With bitwise optimization, the constant factor is dramatically smaller even though asymptotic class is the same.