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.

../_images/3_Sudoku1.png

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

../_images/3_Sudoku2.png

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

Model formulation

As in the examples, we denote the columns of the board by the set XS = \{A, B, ..., I\} and the rows by YS = \{0, 1, ..., 8\}. For every x in XS and y in YS we define a decision variable V_{xy} taking as its value the number at the position (x, y).

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

&\forall x \in XS, y \in YS : V_{xy} \in \{1, ..., 9\} \\ &\forall x \in XS : \text{all-different}(V_{x1}, ..., V_{x9}) \\ &\forall y \in YS : \text{all-different}(V_{Ay}, ..., V_{Iy}) \\ &\text{all-different}(V_{A1}, ..., V_{C3}) \\ &\text{all-different}(V_{A4}, ..., V_{C6}) \\ &\text{all-different}(V_{A7}, ..., V_{C9}) \\ &\text{all-different}(V_{D1}, ..., V_{F3}) \\ &\text{all-different}(V_{D4}, ..., V_{F6}) \\ &\text{all-different}(V_{D7}, ..., V_{F9}) \\ &\text{all-different}(V_{G1}, ..., V_{I3}) \\ &\text{all-different}(V_{G4}, ..., V_{I6}) \\ &\text{all-different}(V_{G7}, ..., V_{I9})

In addition, certain variables V_{xy} 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.

../_images/3_Sudoku_result.png

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