This is the mother of all constraint applications :-). If you understand how humans solve Sudoku puzzles, then you understand how computers solve finite domain constraint programs.
A Sudoku puzzle is typically presented as a 9×9 grid, with some cells containing numbers between 1 and 9, and other cells being empty. The objective is to fill in the empty cells with numbers between 1 and 9, so that
- in each row
- in each column
- and in each of the 9 major 3×3 blocks
each of the numbers from 1 to 9 occurs exactly once.
This is a constraint satisfaction problem: The problem is expressed by variables and constraints.
Each cell of the grid is a variable, which can take values from 1 to 9, we also say that its domain ranges from 1 to 9. As the domains range over a finite set of values, we also say that this is a finite domain constraint program.
There are 27 constraints in this problem. For each row, each column and each major block we have an alldifferent constraint, which states that all variables it contains must be pairwise different. Each of the constraints contains 9 variables, which range over 9 possible values, which must be pairwise different. This implies that each value must occur exactly once.
Once we have defined our problem with its variables and constraints, we can use a constraint solver to find a solution (or even all solutions) of the problem. If the problem is simple enough, the constraint solver will find the solution quite quickly, without any further help from the programmer. For more complex problems, the programmer can give hints to the constraint solver, how the problem should be solved.
To learn more:
I discussed different model variants for the Sudoku puzzle in a 2005 paper, which can be found on my website: Sudoku as a Constraint Problem
If you are interested how a typical constraint engine solves a puzzle, you can watch chapter 5 of my on-line ELearning course on constraint programming: http://4c.ucc.ie/~hsimonis/ELearning/index.htm