Few years ago I was programmer that write my own algorithms for every problem I’ve tried to resolve. One day I asked myself „Is any library that help me to resolve decisions in way, I provide data and conditions and get solution in back?” That day I’ve found Constraint programming.

Contraint programming is an emergent software technology for declarative description and effective solving of large, particularly combinatorial, problems especially in areas of planning and scheduling. It represents the most exciting developments in programming languages of the last decade and, not surprisingly, it has recently been identified by the ACM (Association for Computing Machinery) as one of the strategic directions in computer research.(source)


Since that day I use this type of programming very regular. As Java programmer best for me is Choco Solver library.
Choco’s current version is 3 but documentation is still in writing (since last summer at least) It’s sad. Developers starting with this tool has no documentation. You have option to choose version 2 (well documented), but both of them aren’t compatible and upgrade won’t be easy process.

The summary cheat is only documentation provided for 3rd version of tool.

Although Choco is worth of few minutes.

I’ll try write quick example how it works.

Resolving Sudoku grid with Choco

Sudoku is well known, I don’t write what is this. If you don’t know, just click link and read the wiki page :)

Our goal:

Write code that get the 9×9 grid as parameter with digits from 0-9 and change all 0 to digit from range 1-9. All digits in row, column and 3×3 sector should be different.

What we need? JDK1.6 and choco 3.1 library it’s a lot. To write code use your IDE or notepad, your will.

Start

We need object for our grid. We can use simple int[][] two dimensional array for it. But we wrap this array into Grid class for cleaning code (there’ll be a lot of arrays :))

Our helper is ready. Time to write Sudoku solver.

What field we need?
first will be width of grid, Sudoku’s use 9×9 grid, but if you want to resolve any bigger clone of this puzzle?

Another fields are arrays for rows, columns and sectors. All of them are 2 dimensional array 9×9

We use a smart code to retrieve 3×3 two-dimensional array and exchange it into one-dimensional 9-elements array for every sector. We should only check that all elements are different no matter what position they are at.

The another one is gridData provided as argument.
The last but most important is Solver model. Solver is central object that collect data and compute solution. Let’s see:

Ok. That was easy, but what is IntVal? This is wrapper for Integer value. We can set is as fixed value or as need to be computed value. In fact computing this values is our main goal.

Maybe we should start from this, but it’s time to think about alogithm. It’s pretty clean and simple. Invoke solver, set grid to resolve and resolve it.

Algorithm is made, than we can implement it. I won’t use Test classes or any other external tool, just include my own test code into main method to simplify the code.

Now we have a little more code to write. Time to setting data.

first set data to fields.

Next steps is filling rows and columns. To fill in rows, just iterate over two-dimensional grid, read seeded data and put elements into rows array: If origin value is within range 1-9 then just copy it, if it is 0 then tell Solver it should be computed in this place.

Filling in columns is made by copying value from rows array.

I think almost all in code above is self explanatory. But two things needs few words.
VarableFactory is a class that compute variables. We use it 2 times. First time we use it for setting provided value with fixed method. Second time we use it to tell solver the value here should be computed. We use enumerated method that get minimum and maximum values and all possible computed values are returned from array :MIN, MIN+1, ... , MAX-1, MAX.First argument is string that represents name of computed variable. We used number of row and column prefixed by „c_”. Last argument in both cases is Solver object needed for computation.

Now the smart code for exchange sectors from 3×3 grid into 1×9 grid:

We already have data set, now we need to make computations.

just write last one method solve():

First in we should define constrains:

Every row, column and sector should has different values. We have all data at 3 9×9 arrays.

Ok. Iterate over them and let’s set constraints.

„AC” is algorithm we use for computation. We can use „AC”, „BC” or „DEFAULT”. First is faster, second is more precise, third is mix of both previous.

Now set up strategy:

Choco provides a lot of strategies just look into API. We’ve choosed Mix of firstFail and InDomainMin method. FirstFail will work at smallest domain data, InDomainMin will start from smallest possible value.

Now we have all done. Starting computation is made by calling findSolution method that give boolean value as return.

Easy, isn’t it?

All code at gist:
Grid.java
SudokuSolver.java
.