At every step you have many options, not just two. Try each one, but only if it is safe (no clash with what is already placed). Recurse on it, and if the path fails, undo it and try the next option.

When to use it:

Reach for this when placing something depends on what is already on the board, grid, or graph.

Key Difference:

A safe choice can still lead to a dead end later, so you undo it and try another. In the generate pattern, following the rule can never get you stuck.

Template code:

boolean solve(state) {
    if (goalReached(state)) return true;

    for (Option opt : optionsAt(state)) {
        if (!isValid(state, opt)) continue;   // prune early

        place(state, opt);                    // choose
        if (solve(nextState(state))) return true;   // explore
        undo(state, opt);                     // un-choose
    }
    return false;
}

Complexity:

• Time: exponential in the worst case, and pruning cuts it down a lot in practice
• Space: recursion depth (rows, cells, or nodes) plus the board or color array

Image