8 Queens Problem Backtracking - Algorithm Guide

Backtracking is a general algorithmic technique that incrementally builds candidates for a solution and abandons a candidate (backtracks) as soon as it determines that the candidate cannot be extended to a valid complete solution. It is a refined form of exhaustive search that prunes the search tree dramatically.

The core idea is simple: try to place a queen in a column, check whether the placement is safe, proceed to the next row if it is, and undo the placement (backtrack) if no safe column exists in the current row. This systematic trial-and-error approach is guaranteed to find all solutions — for the 8x8 board that is exactly 92 distinct solutions.

Backtracking is used throughout computer science: constraint satisfaction, Sudoku solvers, maze navigation, and the N queens problem algorithm in AI courses all rely on this technique. Understanding it through the 8 queens problem gives you a foundation applicable to hundreds of interview problems.

The 8 queens problem asks you to place 8 queens on an 8×8 chessboard so that no two queens attack each other — no shared row, column, or diagonal. The backtracking algorithm exploits one constraint immediately: since each row must contain exactly one queen, we can represent the entire board as a one-dimensional array where board[row] = col.

Here is the high-level pseudocode:

function solveNQueens(n):
    board = array of size n, initialized to -1
    backtrack(board, row=0, n)
    return all solutions

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

Each recursive call tries all columns for the current row, pruning branches early whenever a conflict is detected. For n=8 the algorithm explores far fewer than the theoretical 8^8 = 16,777,216 placements.

Let's trace the first few steps for an 8×8 board:

1. Row 0: Try column 0. No queens placed yet, so it is always safe. Place queen at (0,0). Recurse to row 1.
2. Row 1: Try column 0. Conflicts with queen at (0,0) — same column. Skip. Try column 1. Conflicts diagonally with (0,0). Skip. Try column 2. Safe — place queen at (1,2). Recurse to row 2.
3. Row 2: Try columns 0–3, all conflict. Try column 4. Safe — place queen at (2,4). Continue…
4. Eventually row 3 finds no safe column. Backtrack: remove queen from row 2, try column 5 instead of 4.
5. This continues until all 92 solutions are found.

The search tree has depth 8, and pruning means most branches are cut well before reaching depth 8. The algorithm is said to be depth-first with constraint propagation — a pattern you will encounter again in AI search problems.

The isSafe(board, row, col) function is the heart of the algorithm. It must check three conditions for every already-placed queen in rows 0 to row-1:

• Same column: board[i] === col
• Same main diagonal (top-left to bottom-right): board[i] - col === i - row, which simplifies to board[i] - i === col - row
• Same anti-diagonal (top-right to bottom-left): board[i] + i === col + row

Because we place exactly one queen per row and iterate from top to bottom, we never need to check for row conflicts — they are impossible by construction. This reduces each safety check to O(row) work, and the total work per node in the search tree is linear in the depth.

The following is a complete, runnable JavaScript implementation that finds all 92 solutions to the 8 queens problem. It works in Node.js and in the browser. You can also try the interactive puzzle to visualize the solutions.

The worst-case time complexity of the backtracking approach is O(n!). Here's why:

• In row 0, there are n choices.
• In row 1, at most n-1 non-conflicting columns remain.
• In row 2, at most n-2, and so on.
• The product n × (n-1) × (n-2) × … × 1 = n! gives the factorial upper bound.

For n=8 this is 8! = 40,320 — far fewer than the 8^8 = 16.7 million brute-force permutations. In practice, with constraint checking, the algorithm explores far fewer nodes than the O(n!) bound suggests because many branches are pruned early.

For comparison, the brute-force O(n^n) approach would need to evaluate all 16.7 million cells. Backtracking reduces this to roughly 15,720 recursive calls for n=8 — a 1000x improvement.

The space complexity of the backtracking algorithm is O(n), dominated by:

• The board array of size n — O(n)
• The recursion call stack, which has at most n frames active simultaneously — O(n)

This is a key advantage over approaches that store intermediate board states explicitly. By using a single mutable array and undoing changes on backtrack, we keep memory usage minimal regardless of the number of solutions found. Even for n=15, where there are 2,279,184 solutions, memory usage stays under a kilobyte during search.

Two major optimizations can dramatically speed up the backtracking solver:

1. Symmetry Breaking

The 8×8 board has 8-fold symmetry (4 rotations × 2 reflections). By fixing the first queen in only the first 4 columns and then reflecting or rotating solutions, you can reduce the search space by up to 8×. This is especially useful when you only need distinct solutions rather than all placements.

2. Bit Manipulation

Instead of scanning all placed queens in isSafe, maintain three bitmasks:

• cols — columns already occupied
• diag1 — main diagonals occupied (shift left by 1 each row)
• diag2 — anti-diagonals occupied (shift right by 1 each row)

The set of safe columns for the current row is ~(cols | diag1 | diag2) & fullMask. Extracting each candidate via bit = available & -available (lowest set bit trick) gives O(1) safety checks per candidate. This bit-manipulation approach can be 10–50× faster than the naive version for large n.