AlgoScope

Backtracking

Build a solution one choice at a time and undo the last choice when it cannot lead to a solution.

Backtracking, technique, intermediate
No safe square in row 2. The queen at row 1 column 2 is lifted.012301231
No safe square in row 2. The queen at row 1 column 2 is lifted.012301231

Backtracking: 4 queens, with backtracking

Step, step 10 of 32

Row 2 has no safe square, so the choice in row 1 was wrong. Lift the queen from (1, 2) and try the squares after it.

Cost

Space
O(depth)

Time is exponential in general. Pruning determines practical cost.

Leads to

Topics that need this one first.

Taught by the same lesson

Backtracking covers these too, in the same run.