.. _sudoku:
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 :numref:`fig3_Sudoku1` and :numref:`fig3_Sudoku2` 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.
.. _fig3_Sudoku1:
.. figure:: images/3_Sudoku1.png
:scale: 60%
:align: center
Sudoku (‘The Times’, 26 January, 2005)
.. _fig3_Sudoku2:
.. figure:: images/3_Sudoku2.png
:scale: 60%
:align: center
Sudoku (‘The Guardian’, 29 July, 2005)
Model formulation
-----------------
As in the examples, we denote the columns of the board by the set :math:`XS = \{A, B, ..., I\}` and the rows by :math:`YS = \{0, 1, ..., 8\}`. For every :math:`x` in :math:`XS` and :math:`y` in :math:`YS` we define a decision variable :math:`V_{xy}` taking as its value the number at the position :math:`(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 :ref:`here<all-different>`).
.. math::
&\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 :math:`V_{xy}` are fixed to the given values.
Implementation
--------------
The implementation for the Sudoku puzzle in figure :numref:`fig3_Sudoku2` looks as follows:
.. tabs::
.. code-tab:: c++
// 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;
.. code-tab:: py
import sys, os
from kalis import *
# Creation of the session
session = KSession()
# Creation of the problem in this session
problem = KProblem(session, "Sudoku")
# Creation of a 9x9 matrix of KintVar
vars = [
[
KIntVar(problem, "v[{},{}]".format(i,j), 1, 9)
for j in xrange(9)
]
for i in xrange(9)
]
pb = raw_input("Enter problem to be solved (1 or 2): ")
# Data from "The Guardian", 29 July, 2005. http://www.guardian.co.uk/sudoku
if pb == "1":
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)
elif pb == "2":
vars[0][3].instantiate(3); vars[0][6].instantiate(5)
vars[1][4].instantiate(4); vars[1][7].instantiate(8)
vars[2][1].instantiate(1); vars[2][3].instantiate(5)
vars[2][4].instantiate(7); vars[2][5].instantiate(9)
vars[2][6].instantiate(4); vars[2][8].instantiate(3)
vars[3][0].instantiate(5); vars[3][2].instantiate(2)
vars[4][2].instantiate(4); vars[4][6].instantiate(1)
vars[5][6].instantiate(9); vars[5][8].instantiate(7)
vars[6][0].instantiate(4); vars[6][2].instantiate(7)
vars[6][3].instantiate(9); vars[6][4].instantiate(1)
vars[6][5].instantiate(5); vars[6][7].instantiate(3)
vars[7][1].instantiate(6); vars[7][4].instantiate(8)
vars[8][2].instantiate(1); vars[8][5].instantiate(3)
else:
print "problem must be 1 or 2, not {}".format(pb)
del session
exit(1)
# All-different values in rows
for i in xrange(9):
tmpI = KIntVarArray()
for j in xrange(9):
tmpI.add(vars[i][j])
problem.post(KAllDifferent("alldiffVert {}".format(i), tmpI, KAllDifferent.GENERALIZED_ARC_CONSISTENCY))
# All-different values in columns
for j in xrange(9):
tmpJ = KIntVarArray()
for i in xrange(9):
tmpJ.add(vars[i][j])
problem.post(KAllDifferent("alldiffHoriz {}".format(j), tmpJ, KAllDifferent.GENERALIZED_ARC_CONSISTENCY))
# All-different values in 3x3 squares
for offsetI in xrange(0,9,3):
for offsetJ in xrange(0,9,3):
tmpIJ = KIntVarArray()
for i in xrange(3):
for j in xrange(3):
tmpIJ.add(vars[i + offsetI][j + offsetJ])
problem.post(KAllDifferent("alldiff3x3 {},{}".format(offsetI, offsetJ), tmpIJ, KAllDifferent.GENERALIZED_ARC_CONSISTENCY))
# Propagate problem
if problem.propagate():
print "Problem is infeasible"
exit(1)
# Solve the problem
solver = KSolver(problem)
solver.findAllSolutions()
# Get solution
sol = problem.getSolution()
# Print solution resume
sol.printResume();
print "|-------|-------|-------|"
for j in xrange(9):
print "| {} {} {} | {} {} {} | {} {} {} |".format(
sol.getValue(vars[0][j]), sol.getValue(vars[1][j]), sol.getValue(vars[2][j]),
sol.getValue(vars[3][j]), sol.getValue(vars[4][j]), sol.getValue(vars[5][j]),
sol.getValue(vars[6][j]), sol.getValue(vars[7][j]), sol.getValue(vars[8][j])
)
if j % 3 == 2:
print "|-------|-------|-------|"
del session
.. code-tab:: java
import com.artelys.kalis.*;
import java.io.*;
public class Sudoku {
public static void main(String[] args) {
try {
System.loadLibrary("Kalis"); // uses java option -Djava.library.path=path to find Kalis.dll
System.loadLibrary("KalisJava"); // uses java option -Djava.library.path=path to find KalisJava.dll
KSession session = new KSession();
// Creation of the problem in this session
KProblem problem = new KProblem(session, "Sudoku", 4);
KIntVar[][] vars = new KIntVar[9][9];
int i, j;
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
vars[i][j] = new KIntVar(problem, String.format("v[%d,%d]",
i, j), 1, 9);
}
}
System.out.print("Enter problem to be solved (1 or 2): ");
BufferedReader br = new BufferedReader(new InputStreamReader(
System.in));
String pb = br.readLine();
if (pb.equals("1")) {
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);
} else if (pb.equals("2")) {
vars[0][3].instantiate(3);
vars[0][6].instantiate(5);
vars[1][4].instantiate(4);
vars[1][7].instantiate(8);
vars[2][1].instantiate(1);
vars[2][3].instantiate(5);
vars[2][4].instantiate(7);
vars[2][5].instantiate(9);
vars[2][6].instantiate(4);
vars[2][8].instantiate(3);
vars[3][0].instantiate(5);
vars[3][2].instantiate(2);
vars[4][2].instantiate(4);
vars[4][6].instantiate(1);
vars[5][6].instantiate(9);
vars[5][8].instantiate(7);
vars[6][0].instantiate(4);
vars[6][2].instantiate(7);
vars[6][3].instantiate(9);
vars[6][4].instantiate(1);
vars[6][5].instantiate(5);
vars[6][7].instantiate(3);
vars[7][1].instantiate(6);
vars[7][4].instantiate(8);
vars[8][2].instantiate(1);
vars[8][5].instantiate(3);
} else {
throw new RuntimeException(String.format(
"problem must be 1 or 2, not '%s'", pb));
}
// *** Modeling of the problem
i = 0;
for (KIntVar[] row : vars) {
KIntVarArray tmpRow = new KIntVarArray();
for (KIntVar cell : row) {
tmpRow.add(cell);
}
problem.post(new KAllDifferent(
String.format("alldiffHoriz#%d", i++),
tmpRow,
KAllDifferent.PropagationLevel.GENERALIZED_ARC_CONSISTENCY
.swigValue()));
}
for(i = 0; i < 9; i++) {
KIntVarArray tmpCol = new KIntVarArray();
for(j = 0; j < 9; j++) {
tmpCol.add(vars[j][i]);
}
problem.post(new KAllDifferent(
String.format("alldiffVert#%d", i),
tmpCol,
KAllDifferent.PropagationLevel.GENERALIZED_ARC_CONSISTENCY
.swigValue()));
}
int[] offsets = {0,3,6};
for(int offsetI : offsets) {
for(int offsetJ : offsets) {
KIntVarArray tmpSquare = new KIntVarArray();
for(i = offsetI; i < offsetI+3; i++) {
for(j = offsetJ; j < offsetJ+3; j++) {
tmpSquare.add(vars[j][i]);
}
}
problem.post(new KAllDifferent(
String.format("alldiff%dx%d", offsetI, offsetJ),
tmpSquare,
KAllDifferent.PropagationLevel.GENERALIZED_ARC_CONSISTENCY
.swigValue()));
}
}
if (problem.propagate()) {
throw new RuntimeException("Problem is infeasible");
}
KSolver solver = new KSolver(problem);
solver.findAllSolutions();
KSolution sol = problem.getSolution();
sol.printResume();
System.out.println("|-------|-------|-------|");
for(j = 0; j < 9; j++) {
System.out.println(String.format("| %d %d %d | %d %d %d | %d %d %d |",
sol.getValue(vars[0][j]), sol.getValue(vars[1][j]), sol.getValue(vars[2][j]),
sol.getValue(vars[3][j]), sol.getValue(vars[4][j]), sol.getValue(vars[5][j]),
sol.getValue(vars[6][j]), sol.getValue(vars[7][j]), sol.getValue(vars[8][j])));
if (j % 3 == 2)
System.out.println("|-------|-------|-------|");
}
} catch (Exception e) {
e.printStackTrace();
}
}
}
Results
-------
The model shown above generates the following output; this puzzle has only one solution, as is usually the case for Sudoku puzzles.
.. _fig3_Sudoku_result:
.. figure:: images/3_Sudoku_result.png
:align: center
Result of the Sudoku described in :numref:`fig3_Sudoku2`