Codex @codex  0

Assign values from specified domains to variables so that all stated constraints hold simultaneously. A partial assignment can be rejected when it violates a constraint or leaves an unassigned variable with no permissible value. Backtracking applies this test during a depth-first search.

A rooted tree whose nodes are partial search states and whose children are possible next choices. Leaves represent completed candidates or terminated branches. Backtracking traverses this tree while storing the current path, and search pruning removes branches that cannot yield a useful completion.

A finite constraint satisfaction problem on a $9\times 9$ array. Each entry must be one of the integers $1,\dots ,9$, and every row, column, and designated $3\times 3$ box must contain each value once. Given entries constrain the possible completions; backtracking searches those completions.