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 :))

1 2 3 4 5 6 7 8 9 10 11 12 13 |
public class Grid { final int[][] sudokuGrid; public Grid(int[][] grid){ this.sudokuGrid = grid; } public int get(int i, int j){ return sudokuGrid[i][j]; } } |

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class SudokuSolver { //we working on 9x9 grid final int n = 9; IntVar[][] cols, rows, sectors; Grid gridData; Solver solver; public SudokuSolver(){ solver = new Solver("Brilliant Sudoku Solver"); } } |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public static void main(String[] args) { System.out.println("We'll resolve sudoku puzzle now!"); SudokuSolver sudokuSolver = new SudokuSolver(); //set data sudokuSolver.setGridData(new Grid(new int[][]{ {0, 0, 0, 2, 0, 0, 0, 0, 0}, {0, 8, 0, 0, 3, 0, 0, 7, 0}, {3, 0, 0, 5, 0, 4, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 2, 8}, {8, 3, 0, 0, 1, 0, 0, 0, 0}, {0, 4, 0, 7, 2, 0, 3, 5, 1}, {0, 7, 0, 0, 5, 6, 0, 0, 4}, {0, 0, 3, 0, 0, 0, 0, 0, 0}, {2, 0, 5, 4, 0, 1, 6, 0, 3} })); //solve it :) sudokuSolver.solve(); |

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

1 2 |
public void setGridData(Grid gridData){ |

first set data to fields.

1 2 3 4 5 6 7 |
this.gridData = gridData; //fill in arrays rows = new IntVar[n][n]; cols = new IntVar[n][n]; sectors = new IntVar[n][n]; |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
//fill rows and columns for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { //read values from data grid if (gridData.get(i, j) > 0) { //if value is over 0, it should be copied rows[i][j] = VariableFactory.fixed(gridData.get(i, j), solver); } else { //if value is 0, it should be computed rows[i][j] = VariableFactory.enumerated("c_" + i + "_" + j, 1, n, solver);//<- we will talk about it } //copy value to cols array cols[j][i] = rows[i][j]; } } |

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 |
//compute sectors //Sudoku game has 9 sectors 3x3, to simplify we'll made 9 arrays with 9 elements, every array for 1 sector. for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { //iterate over every sector and copy values into arrays sectors[j + k * 3][i] = rows[k * 3][i + j * 3]; sectors[j + k * 3][i + 3] = rows[1 + k * 3][i + j * 3]; sectors[j + k * 3][i + 6] = rows[2 + k * 3][i + j * 3]; } } } |

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.

1 2 3 4 5 6 7 8 |
for (int i = 0; i < 9; i++) { solver.post(IntConstraintFactory.alldifferent(rows[i], "AC")); solver.post(IntConstraintFactory.alldifferent(cols[i], "AC")); solver.post(IntConstraintFactory.alldifferent(sectors[i], "AC")); } |

**„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:

1 2 |
solver.set(IntStrategyFactory.firstFail_InDomainMin(ArrayUtils.append(rows))); |

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.

1 2 3 4 5 6 |
if (solver.findSolution()) { printIt();//pretty print the solution } else { System.out.println("No Solution!"); } |

Easy, isn’t it?

All code at gist:

Grid.java

SudokuSolver.java

.