Constraint Satisfaction Backtracking

Description

Sudoku, N-Queens, map coloring and timetabling share one shape. There's a set of unknowns, such as cells, rows, regions or time slots. Each needs a value, and rules forbid certain combinations. Trying every complete assignment is hopeless: 8 queens, one per row, already have 16,777,216. Constraint-satisfaction backtracking fills unknowns one at a time and rejects a value the moment it breaks a rule. Good bookkeeping and a good choice of which unknown to fill next make it fast on realistic inputs.

We'll go from simple to more technical:

1. The pattern: place, check the rules immediately, recurse, undo, using O(1) lookups.
2. A second flavor: fill the most constrained unknown first.
3. Where constraint solving runs in production (scheduling, configuration, puzzles).
4. What breaks it: late checks, bookkeeping that isn't undone, and slow checks.

The approach

boolean solve(State state, int position) {
    if (position == totalPositions) return true;          // every unknown filled legally
    for (int value : candidatesFor(position)) {
        if (!isAllowed(state, position, value)) continue;  // check BEFORE going deeper
        place(state, position, value);
        if (solve(state, position + 1)) return true;       // stop at the first full solution
        unplace(state, position, value);                   // undo - try the next value
    }
    return false;                                          // nothing fits here: the caller backtracks
}

def solve(state: State, position: int) -> bool:
    if position == total_positions:
        return True                                    # every unknown filled legally
    for value in candidates_for(position):
        if not is_allowed(state, position, value):
            continue                                   # check BEFORE going deeper
        place(state, position, value)
        if solve(state, position + 1):
            return True                                # stop at the first full solution
        unplace(state, position, value)                # undo - try the next value
    return False                                       # nothing fits here: the caller backtracks

The check comes before the recursive call, so a partial assignment that already breaks a rule is never extended. For 8 queens, placing row by row and skipping attacked columns and diagonals places only 2,056 queens in total to find all 92 solutions. Returning true up the stack stops at the first solution (Sudoku); counting instead of returning explores everything (N-Queens counts).

The checks have to be cheap. Keep lookup structures in step with the board - which digits each row, column and 3 x 3 box already has; which columns and diagonals already hold a queen - so isAllowed is O(1). Cells on the same "" diagonal share r - c, cells on the same "/" diagonal share r + c, so two boolean arrays of size 2n - 1 cover all diagonals.

A second flavor: choose the most constrained unknown first

The order in which unknowns are filled doesn't change what's found, but it hugely changes how much is explored. Filling the empty cell with the fewest remaining candidates first (the "most constrained variable" heuristic) fails fast on dead ends and makes forced moves immediately:

int bestR = -1, bestC = -1, fewest = 10;
for (int r = 0; r < 9; r++)
    for (int c = 0; c < 9; c++)
        if (board[r][c] == 0) {
            int options = countAllowedDigits(r, c);
            if (options < fewest) { fewest = options; bestR = r; bestC = c; }
        }
if (bestR == -1) return true;                              // no empty cell left: solved
// try each allowed digit at (bestR, bestC), recurse, undo

def solve(board: list[list[int]]) -> bool:
    best, fewest = None, 10
    for r in range(9):
        for c in range(9):
            if board[r][c] == 0:
                options = count_allowed_digits(r, c)
                if options < fewest:
                    best, fewest = (r, c), options
    if best is None:
        return True                                    # no empty cell left: solved
    # try each allowed digit at best, recurse, undo

On the classic sample puzzle, row-by-row filling makes 4,208 placements; most-constrained-first makes 51. A cell with zero options ends the branch at once, instead of after filling everything before it.

Where you'll see it

Scheduling (exam timetables, nurse rosters, sports fixtures), resource placement (VMs onto hosts respecting capacity and anti-affinity) and configuration (package version resolution) are constraint satisfaction. Production solvers - SAT and CP-SAT solvers, dependency resolvers - are this backtracking loop plus propagation (removing values ruled out by each placement), smart variable ordering and learning from conflicts.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why check a constraint before recursing rather than when the assignment is complete?

2. A Sudoku solver clears the cell when it backtracks but leaves the digit marked in its row/column/box sets. What happens?

3. How do two arrays of size 2n - 1 track every diagonal for N-Queens?

Key takeaways

• Fill unknowns one at a time; check each value against the rules before recursing, and undo on the way back.
• Keep O(1) lookup structures (per row/column/box, per column/diagonal) in step with every placement and undo.
• Return true to stop at the first solution; count to enumerate all.
• Filling the most constrained unknown first often cuts the search dramatically (4,208 to 51 placements on one Sudoku).
• The worst case stays exponential - CSPs are NP-complete in general.