Win any game by cheating with constraint programming

Constraint programming is a declarative programming paradigm. Declarative means that you only (mostly) declare what you want the programm to do (e.g. the end result) and not how to do it (e.g. you don’t specify the procedure; like you’re used in Python, which is a procedural or imperative programming language). Since you don’t specify the procedure (only the desired result), the program must somehow find the solution by itself. And it does indeed find it, if it exists and is reasonably calculable!

The way such a program finds the solution is by trying out all the possibilities of all distinct variables, and then compare variable states to given constraints. If all the variables match all of the specified constraints (limits or rules regarding their values), a possible solution is proclaimed (there may be several possible solutions to any problem).

But this is internal to the interpreter. What you should worry about is decomposition of the problem into specification of:

• all variables that play part in your system,
• all possible input values for each variable,
• the constraining limits and rules that the interaction of these variables must conform to.

For example, if you were to solve a problem of two equations with two variables:

You can decompose the problem into:

• variables that play part in the system: x and y,
• possible input values for x and y: both can be any integer (-Inf, …, -2, -1, 0, 1, 2, …, Inf)
• the constraints:
  1. the equation 4*x + 3*y must evaluate and be equal to 12, and
  2. the equation 3*x + 2*y must evaluate and be equal to 7.

The program automatically finds the solution, which is x=1, y=2.

Even though Python is a procedural language that requires you to specify exactly what to do in steps (e.g. how to do it), its powerful interpreted nature allows one to program with constraints as well.

Task

Your assignment is to write a Sudoku solver in Python. Don’t fright, it’s actually pretty easy-peasy, but you should be thoroughly familiar with basic Python features and syntax!

Follow this short tutorial:

• Constraint programming in Python

Now you should revise Sudoku rules, if you don’t know them already, and then figure out how to represent the ‘Sudoku problem’:

• what are the variables in a game of Sudoku,
• what are their possible values, and
• what are the constraints that define the correct solution?

You will need to install a constraint-solving library to execute this task, and you are free to choose any that you feel comfortable with.

You will witness the power and ease with which your computer solves that one damned hard puzzle.

You are, of course, welcome to suggest your own problem that you would like to solve with constraint programming. You will get points accordingly.

Similar problem suggestion

If you don’t like Sudoku, perhaps you can solve this simple equation for us:

    W O O D Y
+     W O O D
=============
  P E C K E R

We can’t seem to remember what the correct numerical values for C, D, E, K, O, P, R, W, and Y are. Please help.