CodeWithYash

Intermediate · Module 12 · Lesson 5

Constraint search

N-Queens, Sudoku, word search, and pruning.

15–25 min readLesson 68 of 123 Interactive Lab
Jump to interactive visualizer

Lesson 68 of 123

1d streak

Interactive Visualization

Trace the algorithm state by state

Change the inputs, run an operation, and connect each visible state change to the explanation below.

Interactive algorithm lab

N-Queens Backtracking

Choose, explore, reject, and undo

Step 1 / 39

Row

0

Column

0

Queens

0/4

Action

try

·

Why this step happens

This cell is not attacked by any earlier queen.

Invariant to protect

Only safe partial boards are allowed to recurse to the next row.

Theory lesson · Step-by-step

Understand Constraint search

N-Queens, Sudoku, word search, and pruning.

Worked approach

Trace the reasoning step by step

  1. 1Choose the next constrained position.
  2. 2Try each legal candidate.
  3. 3Commit and propagate constraints.
  4. 4Undo immediately when the branch cannot succeed.

Concrete example

Place queens on a 4×4 board.

  1. 1Choose one safe column in row 0.
  2. 2Mark occupied columns and diagonals.
  3. 3Backtrack when a row has no safe column.

Only branches preserving all constraints are explored.

What must remain true (Loop Invariant)

Every partial assignment satisfies all constraints checked so far.

Cost Model

Complexity & Trade-offs

Search tree
Exponential / output-sensitive
O(depth)
Branching factor, depth, pruning, and number of produced answers control cost.

When to use it

  • Self-similar subproblems, enumeration, constraint solving, and decision trees.
  • Generating combinations and permutations.
  • Converting overlapping recursion into dynamic programming.

Common mistakes

  • Missing a base case or failing to make strict progress.
  • Forgetting to undo shared mutable state.
  • Using exponential search when states repeat and should be memoized.

Practice prompts

  • Reproduce the worked Constraint search example without looking at the trace.
  • Change one input condition and explain whether the Constraint search invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.