{title}

{title} is a constraint backtracking lesson about assigning graph colors so adjacent vertices differ. 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...

M Coloring

M Coloring

{title}

{title}