Sudoku


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.

Sudoku Puzzle: Problem (Left) and Solution (Right)

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

Advertisements

About hsimonis

Researcher at the Insight Centre for Data Analytics, University College Cork, Ireland
This entry was posted in 2005, ECLiPSe, ModRef Workshop, Other, puzzle and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s