AlgoScope

N-Queens

Place one queen per row. A column or diagonal conflict forces backtracking.

Backtracking, algorithm, intermediate
Square 1, 0 is attacked.012301231
Square 1, 0 is attacked.012301231

Backtracking: 4 queens, with backtracking

Decision, step 3 of 32

Row 1, square (1, 0): the queen in row 0 is in the same column. Try the next square.

Cost

Best
O(n!)
Average
O(n!)
Worst
O(n!)
Space
O(n)

Leads to

Topics that need this one first.

Taught by the same lesson

Backtracking covers these too, in the same run.