Constraint Programming: Solving Sudoku with Choco Solver library
Tags: java, programming
Published: 2021-04-27 09:51:20


## Why solve sudoku?

Enterprise application development is, for the most part, solving one of these types of problems:

*   _“Let me create, read, update and delete these things”_
*   _“Do this same task to as many things as possible, as quickly as possible”_
*   _“What’s the best way to allocate the resources I have to do these tasks, if whatever does task X, can’t be used to do task Y?”_

This last problem type is a [**graph colouring**](https://en.wikipedia.org/wiki/Graph_coloring) problem, and the nature of these is that solving one of them is much the same as solving another.

Sudoku is one of these types of problems, but it has very simple rules, so it’s a nice playground to try out different ways to solve graph colouring problems. This post outlines a solution using [**constraint programming**](https://en.wikipedia.org/wiki/Constraint_programming) with [**choco solver**](https://choco-solver.org/).

## What is constraint programming?

Constraint programming is a paradigm for programming that can be a little unusual the first time you come to it, since it’s completely different to imperative programming.

In short: you tell the program what problem needs to be solved, but not how to solve that problem.

What this means in practical terms is:

*   First you define your variables.
    *   _These are my tasks_
    *   _These are my workers_
*   Then you define the domains in which these variables exist. For example:
    *   _This variable has to have the value of 3_
    *   _This variable can have any value between 1 and 42_
    *   _This variable is a set of between 4 and 10 numbers, that are all taken from a domain running from 1 to 99._
*   Then you define the constraints for these variables, for example:
    *   _If one variable has a value, the other variable must have a different value._
    *   _One variable must be the sum/max/min of a few other variables._
    *   _One set must be a compliment of another set._
*   If you’re looking for any solution, then you’re done. If you’re looking for the best solution, then you need to define a set of cost variables that you aim to minimise or maximise. For example:
    *   _Find a solution that minimizes the “cost of doing business” variable._
    *   _Find a solution that maximises the “how many messages are being transmitted” variable._
*   Finally, you give this to the framework to solve, and it will use different AI approaches to find solutions to the problem you’ve defined.

## Solving Sudoku in Choco Solver

So, to make these ideas more concrete, we’ll use them to solve a simple problem.

For this example, we will choose the [**world’s hardest sudoku problem**](https://puzzling.stackexchange.com/questions/252/how-do-i-solve-the-worlds-hardest-sudoku), you can find a full example of this in [**Sudoku.java**](https://github.com/sonalake/chocosolver-samples)

![](https://sonalake.com/wp-content/uploads/2021/04/sudoku.png)

If you don’t know [**Sudoku**](https://en.wikipedia.org/wiki/Sudoku), the rules are:

*   The grid is a 9 X 9 area of squares.
*   Each square must contain a single number, from 1 to 9.
*   The same number can’t appear in the same row twice.
*   The same number can’t appear in the same column twice.
*   The grid is broken down into 9 distinct sub-grids of 9 squares each. The same number can’t appear in the same sub-grid twice.

That’s it. If you’re wondering what this has to do with resource usage, you could imagine the numbers represent available channels in a cell tower, and the squares represent the messages that need to be sent. The solution to this problem will tell you how you could send out these messages in an evenly distributed manner, without getting any resource contention on the channels.

### Getting started with Choco Solver

The complete code for this is available here: [**Sudoku**](https://github.com/sonalake/chocosolver-samples)

Before we do anything else, we must first create an empty [**model**](https://choco-solver.org/docs/modeling/) for the game, this is as simple as:

```java
Model model = new Model("sudoku");
```

This model is where new variables, constraints and optimizations are created.

### Defining variables and domains

For the sudoku problem, there are 81 variables, one for each square in our grid.

```java
IntVar[][] grid = new IntVar[9][9];
```

These come in one of two flavours:

*   If the value is not known at the start, then we need to define it with a domain of possible values, in our case, they are values from 1 to 9

```java
grid[row][col] = model.intVar(row, col), 1, 9);
```
*   If the value is known at the start, then we define it as a simple constant that can’t change. This is, in effect, saying that the variable has a domain of a single value.

```java
grid[row][col] = model.intVar(value)
```
### Define constraints

Once we have the variables, we need to set up their constraints, we have 9 rows, columns, and sub-squares where the values must all be different. We use the [**allDifferent**](https://choco-solver.org/docs/modeling/intconstraints/) constraint for this.


```java
for (int i = 0; i != 9; i++) {
  model.allDifferent(getCellsInRow(grid, i)).post();
  model.allDifferent(getCellsInColumn(grid, i)).post();
  model.allDifferent(getCellsInSquare(grid, i)).post();
}
```

### Solve it

Finally, we solve it as follows.

```java
Solver solver = model.getSolver();
solver.solve();
```

Choco solver will keep looking for solutions until it gives up, because it’s used them all, or because it thinks it won’t find anything better, or because you’ve told it to give up after doing enough work.

Once this is done you can get at the value that choco solver found for each cell as follows

```java
grid[row][column].getValue()
```
And that’s it, the world’s hardest sudoku is solved in under a second.

## So what else can you do with choco solver?

Whatever you want it to, so long as you can turn it into a combinatorics constraint problem.

For example, here’s a more complex graph colouring program: [**GraphColouring.java**](https://github.com/sonalake/chocosolver-samples)

What it’s doing is:

*   Given a graph: _imagine these are tasks that can’t be done at the same time._
*   Given you have N possible colours to choose from: _imagine these are workers that are available to do these tasks._
*   Given that no colour can be used more the M times: _imagine a worker can only do so many things in a day._
*   Given you want to use the least number of colours: _use the fewest workers required to do this work._
*   Colour the graph in: _suggest a roster for the tasks and workers that uses the least number of people without overworking them._

## Where do we go now?

This post refers to two simple examples of what is possible, but really most combinatorial problems can be solved using this approach.

*   For a more formal and complete description of constraint programming, check out [**Explaining Constraint Programming**](https://arxiv.org/pdf/cs/0602027.pdf)
*   For a nice explanation of how to formalise actual problems, check out lectures 7, 8 and 9 of this AI [**lecture series**](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-034-artificial-intelligence-fall-2010/lecture-videos/) from MIT (actually, all of this series is worth watching)
    *   [**Lecture 7: Constraints: Interpreting Line Drawings**](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-034-artificial-intelligence-fall-2010/lecture-videos/lecture-7-constraints-interpreting-line-drawings)
    *   [**Lecture 8: Constraints: Search, Domain Reduction**](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-034-artificial-intelligence-fall-2010/lecture-videos/lecture-8-constraints-search-domain-reduction)
    *   [**Lecture 9: Constraints: Visual Object Recognition**](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-034-artificial-intelligence-fall-2010/lecture-videos/lecture-9-constraints-visual-object-recognition)