Sudoku Constraint Satisfaction Explained Simply

What is a constraint satisfaction problem

A constraint satisfaction problem, or CSP, has three parts: a set of variables, a domain of possible values for each variable, and a set of constraints that restrict which value combinations are allowed. A solution assigns one value to every variable so that every constraint holds at once. Map coloring, timetabling, and many puzzles fit this template, and Sudoku is among the cleanest examples because its rules are exact and finite. There is no fuzziness about what a valid answer is, which makes it a favorite teaching example for the whole idea. The same three part recipe, variables, domains, constraints, describes problems across artificial intelligence, and once you can state a puzzle this way a general solver can attack it.

Sudoku constraint satisfaction: variables, domains, constraints

• Variables: the 81 cells of the grid, one variable per cell.
• Domains: each empty cell can hold any symbol from 1 to 9, while a given clue has a domain of just its fixed symbol.
• Constraints: every row, every column, and every 3 by 3 box must contain nine different symbols.

Framed as sudoku constraint satisfaction, solving means choosing one symbol per cell so that all 27 groups, the nine rows, nine columns, and nine boxes, are free of repeats. Each group carries an all-different constraint, meaning its nine cells must take nine distinct values. All-different is a well studied global constraint and it is powerful because it links many variables at once: if eight cells in a row have committed to eight symbols, the ninth is forced. Recognizing that force is the seed of every basic Sudoku technique, and in sudoku constraint satisfaction it falls out of the model automatically instead of being a special hand written rule.

Constraint propagation shrinks the search

Before any guessing, a solver can prune domains by propagation. When a cell is set to a symbol, remove that symbol from the domains of every cell sharing its row, column, or box. This may reduce another cell to a single remaining value, which you then commit, triggering more removals in a chain. The routine is simple: assign the known clues and remove their values from peers, find any cell with exactly one value left and assign it, repeat the removals that assignment causes, and continue until nothing changes. This process, a form of arc consistency, often solves easy puzzles completely without a single guess, which is why it feels like the puzzle is solving itself.

Search, and why this framing matters

Harder puzzles stall, because propagation reduces domains but no cell drops to a single value. Now the solver must search: it picks a variable, ideally the one with the smallest domain, tries one value, and propagates again. If a contradiction appears, an empty domain, it backs up and tries the next value. This blend of propagation and backtracking is the standard way to attack any CSP, and it is far faster than blind trial because propagation prunes huge regions of the search space early. Seeing Sudoku as a CSP pays off beyond one puzzle, since the same solver structure schedules classes without clashes or assigns frequencies to radio towers. The value comes from separating the model, what counts as valid, from the search, how you find a valid assignment. Because the model is explicit, you can also prove properties, such as confirming a puzzle has exactly one solution before publishing it. Shapedoku benefits from the same clarity: the shapes are only the display, while underneath each board is a tidy constraint satisfaction problem with one guaranteed solution, which you can feel at app.shapedoku.com as forced cells reveal themselves.