N-Queens Visualizer

See backtracking place and remove queens while checking rows and diagonals, with interactive board size and playback controls.

Ready. Use the controls to begin exploring N-Queens.

N-Queens Problem Visualizer

N (4-10):

Speed:

Try placing a queen at row 0, column 0.

Step 1 / 1963

Animation Legend

Trying This Square

Queen Placed

Conflict / Backtrack

The algorithm places queens one row at a time. When a square is attacked by an existing queen (same column or diagonal), it turns red and the algorithm tries the next column. If no column works in a row, it backtracks and removes the queen from the previous row to try a different position there.

Java Implementation

public boolean solve(int[] cols, int row, int n) {
    if (row == n) return true; // all queens placed

    for (int col = 0; col < n; col++) {
        if (isSafe(cols, row, col)) {
            cols[row] = col;
            if (solve(cols, row + 1, n)) return true;
            cols[row] = -1; // backtrack
        }
    }
    return false; // no column worked in this row
}

public boolean isSafe(int[] cols, int row, int col) {
    for (int r = 0; r < row; r++) {
        int c = cols[r];
        if (c == col || Math.abs(c - col) == Math.abs(r - row)) {
            return false;
        }
    }
    return true;
}
Time Complexity: O(N!) worst case

What is the N-Queens Problem?

The N-Queens Problem asks you to place N chess queens on an N×N board so that no two queens attack each other - meaning no two share a row, column, or diagonal. It is one of the classic examples used to teach backtracking, because the constraints are simple to check but the search space grows factorially.

Backtracking solves it by placing queens one row at a time. Whenever a placement conflicts with an existing queen, the algorithm immediately abandons that branch instead of exploring it further - the same "fail fast, undo, retry" pattern used by the Sudoku Solver and Hamiltonian Path visualizers.

Time & Space Complexity

Worst Case TimeO(N!)
Space (Recursion + Board)O(N)
Conflict CheckO(N)

* Pruning conflicting branches early makes the practical runtime far better than the theoretical worst case.

Why Backtracking?

✓
Constraint SatisfactionEach row's choice only needs to be checked against rows already placed.
✓
Early PruningA conflicting placement is rejected immediately, without exploring the rows beneath it.
✓
Undo on FailureRemoving the last queen and trying the next column is the core "backtrack" step.

N-Queens Problem Complete Info Card

BacktrackingConstraint Satisfaction

The N-Queens Problem places queens one row at a time, immediately abandoning any branch where a queen would be attacked, which prunes away most of the theoretical search space.

Algorithm Characteristics

Worst Case Time

Naive exploration of every row/column combination

O(N!)

Space Complexity

One column index stored per row, plus recursion depth

O(N)

Conflict Check

Compare against every previously placed queen

O(N)

Problem Type

Row, column, and diagonal constraints

Constraint Satisfaction

Search Strategy

Commit to a row, recurse, undo on failure

Depth-First

Solutions for N=8

Distinct solutions exist on a standard chessboard

Algorithm Steps

Move to the next row (start at row 0)

Try placing a queen in the leftmost open column

Check the column and both diagonals for conflicts

If safe, place the queen and recurse into the next row

If no column works, backtrack to the previous row

Stop once row N is reached with no conflicts

When to Use

•Teaching backtracking and constraint propagation
•Small to moderate board sizes (roughly N ≤ 20)
•Benchmarking pruning strategies against brute force

When to Avoid

•Very large N without bitmask-based pruning
•When you only need to know if a solution exists (a constructive formula exists for N ≥ 4)
•Counting all solutions for large N (grows extremely fast)

Did You Know? There is no solution for N = 2 or N = 3 - the smallest solvable board size is N = 1 (trivial) or N = 4.

RecursionPruningChessboard puzzle