# Sudoku¶

Sudoku puzzles, originating from Japan, have recently made their appearance in many western newspapers. The idea of these puzzles is to complete a given, partially filled 9 × 9 board with the numbers 1 to 9 in such a way that no line, column, or 3 × 3 subsquare contains a number more than once. The figures Fig. 22 and Fig. 23 show two instances of such puzzles. Whilst sometimes tricky to solve for a human, these puzzles lend themselves to solving by a constraint programming approach.

Fig. 22 Sudoku (‘The Times’, 26 January, 2005)

Fig. 23 Sudoku (‘The Guardian’, 29 July, 2005)

## Model formulation¶

As in the examples, we denote the columns of the board by the set and the rows by . For every in and in we define a decision variable taking as its value the number at the position .

The only constraints in this problem are:

• all numbers in a row must be different,

• all numbers in a column must be different,

• all numbers in a 3 × 3 subsquare must be different.

These constraints can be stated with the KAllDifferent constraint that ensures that all variables in the relation take different values (see definition here).

In addition, certain variables are fixed to the given values.

## Implementation¶

The implementation for the Sudoku puzzle in figure Fig. 23 looks as follows:

// index variables
int indexX,indexY;
// Creation of the problem in this session
KProblem problem(session,"Sudoku");

// creation of a 9x9 matrix of KintVar
// we use the following bijection: A,B,..,I <-> 0,1,..,8
char name[80];
KIntVar *** vars = new KIntVar **[9];
for (indexX = 0;indexX < 9 ; indexX++)
{
vars[indexX] = new KIntVar * [9];
for (indexY = 0;indexY < 9 ; indexY++)
{
sprintf(name,"v[%i,%i]",indexX,indexY);
vars[indexX][indexY] = new KIntVar(problem,name,1,9);
}
}

// Data from "The Guardian", 29 July, 2005. http://www.guardian.co.uk/sudoku
vars[0][0]->instantiate(8); vars[5][0]->instantiate(3);
vars[1][1]->instantiate(5); vars[6][1]->instantiate(4);
vars[0][2]->instantiate(2); vars[4][2]->instantiate(7); vars[7][2]->instantiate(6);
vars[3][3]->instantiate(1); vars[8][3]->instantiate(5);
vars[2][4]->instantiate(3); vars[6][4]->instantiate(9);
vars[0][5]->instantiate(6); vars[5][5]->instantiate(4);
vars[1][6]->instantiate(7); vars[4][6]->instantiate(2); vars[8][6]->instantiate(3);
vars[2][7]->instantiate(4); vars[7][7]->instantiate(1);
vars[3][8]->instantiate(9); vars[8][8]->instantiate(8);

// All-different values in rows
for (indexX = 0;indexX < 9 ; indexX++)
{
KIntVarArray tmpY;
for (indexY = 0;indexY < 9 ; indexY++)
{
tmpY += *vars[indexX][indexY];
}
problem.post(new KAllDifferent("alldiffVert",tmpY,KAllDifferent::GENERALIZED_ARC_CONSISTENCY));
}

// All-different values in columns
for (indexY = 0;indexY < 9 ; indexY++)
{
KIntVarArray tmpX;
for (indexX = 0;indexX < 9 ; indexX++)
{
tmpX += *vars[indexX][indexY];
}
problem.post(new KAllDifferent("alldiffHoriz",tmpX,KAllDifferent::GENERALIZED_ARC_CONSISTENCY));
}

// All-different values in 3x3 squares
int i,j;
for (j=0;j<3;j++)
{
for (i=0;i<3;i++)
{
KIntVarArray tmpXY;
for (indexY = i*3;indexY < i*3+3 ; indexY++)
{
for (indexX = j*3;indexX < j*3+3 ; indexX++)
{
tmpXY += *vars[indexX][indexY];
}
}
problem.post(new KAllDifferent("alldiff3x3",tmpXY,KAllDifferent::GENERALIZED_ARC_CONSISTENCY));
}
}

// propagating problem
if (problem.propagate())
{
printf("Problem is infeasible\n");
exit(1);
}

// creation of the solver
KSolver solver(problem);
// look for all solutions
int result = solver.findAllSolutions();
// solution printing
KSolution * sol = &problem.getSolution();

// print solution resume
sol->printResume();
printf("|-------|-------|-------|\n");
for (indexY = 0;indexY < 9 ; indexY++)
{
printf("| %i %i %i | %i %i %i | %i %i %i |\n",
sol->getValue(*vars[0][indexY]),
sol->getValue(*vars[1][indexY]),
sol->getValue(*vars[2][indexY]),
sol->getValue(*vars[3][indexY]),
sol->getValue(*vars[4][indexY]),
sol->getValue(*vars[5][indexY]),
sol->getValue(*vars[6][indexY]),
sol->getValue(*vars[7][indexY]),
sol->getValue(*vars[8][indexY])
);

if (indexY % 3 == 2)
{
printf("|-------|-------|-------|\n");
}
}

// memory desallocation
for (indexX = 0;indexX < 9 ; indexX++)
{
for (indexY = 0;indexY < 9 ; indexY++)
{
delete vars[indexX][indexY];
}
delete[] vars[indexX];
}
delete[] vars;


## Results¶

The model shown above generates the following output; this puzzle has only one solution, as is usually the case for Sudoku puzzles.

Fig. 24 Result of the Sudoku described in Fig. 23