{title}

{title} is a constraint backtracking lesson about moving through open cells while marking and unmarking the path. It explores one valid move at a time, rejects illegal states early, and undoes moves before trying alternatives.

Topic

Constraint Problems

Pattern

Constraint Backtracking

Time

Exponential, pruned by constraints

Space

O(depth)

Call tree simulation

initial state

depth 0

choice

candidate

choice

valid?

choice

place

choice

undo

Code Tracker

:::

1bool solve(state) {

2 if (isComplete(state)) return true;

3 for (choice : choices(state)) {

4 if (!isValid(choice)) continue;

5 apply(choice);

6 if (solve(nextState)) return true;

7 undo(choice);

8 }

9 return false;

10}

Loading Lab...

Rat In A Maze

Rat In A Maze

{title}

{title}