# 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:
and*x*,*y* - possible input values for
*x*and*y*: both can be any**integer**(-Inf, …, -2, -1, 0, 1, 2, …, Inf) - the
**constraints**:- the equation
`4*x + 3*y`

must evaluate and be equal to`12`

, and - the equation
`3*x + 2*y`

must evaluate and be equal to`7`

.

- the equation

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:

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.