= Solution
<Backtracking> assigns one <variable> at a time and abandons a partial assignment as soon as it cannot extend to a solution. With <forward checking>, placing a knight deletes its occupied and attacked squares from every remaining knight's <constraint domain>. An empty <constraint domain> rejects the branch immediately; stronger <constraint propagation>, such as <arc consistency>, can detect additional incompatibilities among future choices.
This combines early rejection with depth-first storage. It retains the current assignment and domain changes rather than the entire breadth-first layer of partial placements. A direct knight-variable implementation uses $O(kn^2)$ space for explicit domains, plus its assignment and restoration trail, instead of an exponentially large <breadth-first search> <search frontier>. Propagation has a computational cost and does not guarantee improvement on every input, but often prevents exploration of vast inconsistent subtrees.
The \b[<minimum remaining values heuristic>] selects an unassigned <variable> with the fewest currently legal values, exposing the likeliest failure first. The \b[<degree heuristic>] selects a <variable> constrained to the largest number of other unassigned <variables>, often breaking <minimum remaining values heuristic> ties. Degree is measured in the remaining <constraint graph>, not by counting assigned neighbors. In the symmetric knight-variable encoding the remaining degrees can all tie, so the heuristic need not discriminate there.<CS 188 constraint ordering and structure notes>[§2.4, Minimum Remaining Values: choose an unassigned variable with the fewest valid remaining values]{ref}
Back to article page
