AlgoViz
HomeBacktracking

N-Queens

Hard

Place row by row, backtrack on attack

In simple words

Place one queen per row; if a spot is safe move on, and if you get stuck, back up and try elsewhere.

The idea

Place one queen per row. Before placing, check the column and both diagonals are free. If a row has no safe column, backtrack to the previous row.

n4

Step 1 of 32. Place one queen per row. A square is safe only if its column and both diagonals are free — otherwise backtrack. n 4.

1/32
Optimal
timeO(n!)spaceO(n)

O(1) attack checks with sets.

1function place(row) {2  if (row === n) { count++; return; }3  for (let col = 0; col < n; col++) {4    if (cols.has(col) || diag.has(row-col) || anti.has(row+col)) continue;5    mark(row, col);6    place(row + 1);7    unmark(row, col);8  }9}

Input

grid
4 × 4

Memory

n
4
row
—

Output

solution
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
n = 4
Output:
2
Explanation:
There are 2 ways to place 4 non-attacking queens.

Example 2

Input:
n = 1
Output:
1
Explanation:
One queen, one board.

Example 3

Input:
n = 8
Output:
92
Explanation:
The classic 8-queens puzzle has 92 solutions.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.