POSTED ON 14 APR 2021
READING TIME: 6 MINUTES
Constraint programming: solving Sudoku with Choco Solver library
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 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 with choco solver.
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, you can find a full example of this in Sudoku.java
If you don’t know 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
Before we do anything else, we must first create an empty model for the game, this is as simple as:
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.
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
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.
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 constraint for this.
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.
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
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
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
- For a nice explanation of how to formalise actual problems, check out lectures 7, 8 and 9 of this AI lecture series from MIT (actually, all of this series is worth watching)