Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

N-Queens

LeetCode #51Hard
Place row by row, backtrack on attack

Given an integer n, return all distinct ways to place n queens on an n-by-n chessboard so that no two queens attack each other, with each solution shown as a board layout.

Asked atAmazonGoogleAdobe
step 1 / 37
4 × 4 board · place 1 queen per row
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Backtracking · one queen per row
▸
1solve(N):
2    return place(row = 0)
3place(row):
4    if row == N: return true        // all queens placed
5    for col in 0..N-1:
6        if attacked(row, col):
7            continue                // reject, try next column
8        board[row][col] = Q         // choose
9        if place(row + 1): return true
10        board[row][col] = .         // un-choose (backtrack)
11    return false                    // no safe column in this row
12attacked(row, col):
13    any earlier queen in same column or diagonal
state
  • N4
  • ruleno shared column / diagonal

line 1N-Queens (N = 4): place 4 queens so none attack another — no two in the same column or on the same diagonal (rows are automatically distinct because we place exactly one queen per row). We go row by row: in each row try columns left to right, place a queen where it is safe, recurse to the next row, and BACKTRACK (lift the queen) whenever a row has no safe square.