AlgoScope

Constraint Search and Pruning

Checking a constraint at each placement prunes whole subtrees before they are explored.

Backtracking, analysis, advanced
Square 0, 0 is safe, a queen is placed.0123450123451
Square 0, 0 is safe, a queen is placed.0123450123451

Backtracking: 6 queens, the long way

Decision, step 2 of 198

Row 0, square (0, 0): no queen shares its column or a diagonal. Place a queen and move to row 1.

How backtracking works

Cost

Space
O(depth)

Leads to

Topics that need this one first.

Taught by the same lesson

Backtracking covers these too, in the same run.