LESSON 19 · PATTERN GUIDE

Backtracking with Constraints

Prune partial choices as soon as they cannot lead to a valid complete solution.

FIRST, LEARN THE PATTERNAdd a constraint check before recursing. A good pruning rule can eliminate huge parts of the search tree.

The task asks for valid board placements, word paths, combinations with limits, or assignments under constraints.

How to approach it

Maintain the partial state, test whether a new choice is legal, recurse if so, then undo the state change.

Watch out for

Pruning must never remove a valid solution. Track shared mutable state carefully when returning multiple answers.

A CLOSER EXPLANATION

Constraint checks prune a branch as soon as a partial assignment becomes impossible. Keep the partial state small and update it in place when possible, then undo it after recursion. Strong early constraints can reduce a huge search tree to a manageable number of candidates.

NOW YOU TRY

Practice question

Place one queen in each of 4 rows of a chessboard so no two queens share a column or diagonal. How many arrangements exist?

EXAMPLEBoard size = 4 × 4Give your answer before revealing the explanation.

Show a hint

When placing a queen, track occupied columns and the two diagonal directions.

Show an answer

2 arrangements.

CONNECT IT TO REAL LIFE

Backtracking with Constraints at work

Four meetings must be assigned to rooms. Meetings 1 and 2 overlap, and meetings 2 and 3 overlap; meetings 1 and 3 do not. What is the fewest rooms needed?

Show one possible approach

Two rooms. The overlap constraints forbid meetings 1 and 2 sharing a room, and meetings 2 and 3 sharing; meetings 1 and 3 can use the same room. Backtracking can assign rooms while pruning conflicts.

Practice next

Use these problem IDs to find additional practice for this pattern:

4017791315152