Algorithm Guidecomplexity: O(N!)

N-Queens

The problem of placing N queens on an N×N chessboard so none can attack another. It tries one queen per row, checking column and diagonal conflicts, and backs off to the previous choice when stuck — the classic backtracking pattern.

01N-Queens

Explore How It Works

4-Queens problem. Place 4 queens on a 4×4 board so none can attack another — one per row, with no column or diagonal overlap.

Row 0 · place a queen on (0,0) in the first row.

Row 1 · (1,1) clashes on a diagonal. (1,2) is safe, so place a queen there.

Row 2 · all four cells clash on a column or diagonal. Nowhere to place.

Backtrack · move Row 1's queen one cell over to (1,3) and place it again.

Row 2 · this time (2,1) is safe. Place a queen.

Row 3 · every cell in the last row clashes. Blocked again.

Backtrack up the chain to move Row 0's queen to (0,1), and re-explore from that branch.

Place queens safely in turn: Row 1 (1,3), Row 2 (2,0).

Row 3 · place the last queen on (3,2). It clashes with no queen — four queens complete!

Solution [1, 3, 0, 2] found. Backtracking prunes a branch the moment a clash appears, reaching a solution without examining all N! arrangements.

Live Python

1def solve(row, board, n):

2 if row == n:

3 return board[:] # solution found

4 for col in range(n):

5 if safe(board, row, col):

6 board.append(col) # place

7 res = solve(row + 1, board, n)

8 if res: return res

9 board.pop() # backtrack

10 return None

1 / 11

02 Understand It Simply

For Everyone

🔑How It Works

Places one queen per row, and whenever a placement shares a column or diagonal with an earlier one, takes it back. When a row runs out of squares it returns to the previous row and chooses again.

💡In Plain Words

Place one queen per row; the moment a column or diagonal clashes, back off to the previous choice and try another cell.

Pruning dead branches early avoids examining all N! arrangements.

📍Where It's Used

–Constraint-satisfaction problems
–seat/resource placement
–puzzle solving

03 Python Implementation

A clean, readable reference implementation of the core logic of N-Queens.

core_implementation.py

def solve_n_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    board, solutions = [], []

    def backtrack(row):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col); diag1.add(row - col); diag2.add(row + col)
            board.append(col)
            backtrack(row + 1)
            board.pop()
            cols.discard(col); diag1.discard(row - col); diag2.discard(row + col)

    backtrack(0)
    return solutions

04 Frequently Asked Questions

FAQ

What is N-Queens?+

What is the time complexity of N-Queens?+

The time complexity of N-Queens is O(N!). Follow the step-by-step visualization to see exactly why.

Where is N-Queens used?+

Constraint-satisfaction problems, seat/resource placement, puzzle solving.

What's a simple analogy for N-Queens?+

Places one queen per row, and whenever a placement shares a column or diagonal with an earlier one, takes it back. When a row runs out of squares it returns to the previous row and chooses again.

→ Backtracking — see allRelated