N Queen

Hard

One queen per column, backtrack on conflict

Problem

Place N queens on an NxN board so no two attack each other; return all distinct solutions.

In simple words

Place one queen per row; skip any column or diagonal already attacked, and backtrack on dead ends.

The idea

Place one queen per column and, for each, try every row that is not already attacked. Checking rows and the two diagonals with three boolean arrays makes each placement test O(1), and abandoning a column as soon as no safe row exists prunes the vast majority of the search tree.

The trick

Both diagonals have a constant index: row + col and row - col + n.
One queen per column is assumed by construction, so only rows and diagonals need checking.
A solution is complete when you have placed a queen in every column.

←→stepspaceplay

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.