Skip to content

Instantly share code, notes, and snippets.

@marioosh
Created February 24, 2014 13:13
Show Gist options
  • Save marioosh/9188179 to your computer and use it in GitHub Desktop.
Save marioosh/9188179 to your computer and use it in GitHub Desktop.
Sudoku Solver with choco, more at http://marioosh.5dots.pl
package sudoku;
import solver.Solver;
import solver.constraints.IntConstraintFactory;
import solver.search.strategy.IntStrategyFactory;
import solver.variables.IntVar;
import solver.variables.VariableFactory;
import util.tools.ArrayUtils;
/**
* Created with IntelliJ IDEA.
* User: marioosh
* Date: 23.02.2014
* Time: 21:34
*/
public class SudokuSolver {
//fields n grid
final int n = 9;
Solver solver;
IntVar[][] cols, rows, sectors;
private Grid gridData;
public SudokuSolver() {
solver = new Solver("Sudoku Solver");
}
public void printIt() {
System.out.println("Solving sudoku grid!\n\n");
StringBuilder sb = new StringBuilder();
sb.append("\t");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
sb.append(rows[i][j].getValue()).append(" ");
}
sb.append("\n\t");
}
System.out.println(sb.toString());
}
public void solve() {
//define contrains
for (int i = 0; i < 9; i++) {
solver.post(IntConstraintFactory.alldifferent(rows[i], "AC"));//we should choose algoritm, we choosed "AC", look into documentation
//the same for columns and sectors
solver.post(IntConstraintFactory.alldifferent(cols[i], "AC"));
solver.post(IntConstraintFactory.alldifferent(sectors[i], "AC"));
}
//set search strategy
solver.set(IntStrategyFactory.firstFail_InDomainMin(ArrayUtils.append(rows))); //set smallest values first
//Just solve it!
if (solver.findSolution()) {
printIt();
} else {
System.out.println("No Solution!");
}
}
public void setGridData(Grid gridData) {
this.gridData = gridData;
//create new model;
rows = new IntVar[n][n];
cols = new IntVar[n][n];
sectors = new IntVar[n][n];
//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);
}
//copy value to cols array
cols[j][i] = rows[i][j];
}
}
//compute sectors
//Sudoku game has 9 sectors 3x3, to simplify we'll made 9 arrays with 9 values, 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 to 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];
}
}
}
}
public static void main(String[] args) {
SudokuSolver ss = new SudokuSolver();
System.out.println("We'll solve sudoku puzzle now!");
ss.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}
}));
ss.solve();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment