all_different: 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 tables Sudoku (`The Times', 26January, 2005) and Sudoku (`The Guardian', 29July, 2005) show two instances of such puzzles. Whilst sometimes tricky to solve for a human, these puzzles lend themselves to solving by a CP approach.

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 = {1,2,...,9}. 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
(1) all numbers in a row must be different,
(2) all numbers in a column must be different,
(3) all numbers in a 3×3 subsquare must be different.

These constraints can be stated with Xpress Kalis's all_different relation. This constraint ensures that all variables in the relation take different values.

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

Implementation

The Mosel implementation for the Sudoku puzzle in Table Sudoku (`The Guardian', 29July, 2005) looks as follows.

model "sudoku (CP)"
 uses "kalis"

 forward procedure print_solution(numsol: integer)

 setparam("kalis_default_lb", 1)
 setparam("kalis_default_ub", 9)         ! Default variable bounds

 declarations
  XS = {'A','B','C','D','E','F','G','H','I'}   ! Columns
  YS = 1..9                              ! Rows
  v: array(XS,YS) of cpvar               ! Number assigned to cell (x,y)
 end-declarations

! Data from "The Guardian", 29 July, 2005. http://www.guardian.co.uk/sudoku
 v('A',1)=8; v('F',1)=3
 v('B',2)=5; v('G',2)=4
 v('A',3)=2; v('E',3)=7; v('H',3)=6
 v('D',4)=1; v('I',4)=5
 v('C',5)=3; v('G',5)=9
 v('A',6)=6; v('F',6)=4
 v('B',7)=7; v('E',7)=2; v('I',7)=3
 v('C',8)=4; v('H',8)=1
 v('D',9)=9; v('I',9)=8


! All-different values in rows
 forall(y in YS) all_different(union(x in XS) {v(x,y)})

! All-different values in columns
 forall(x in XS) all_different(union(y in YS) {v(x,y)})

! All-different values in 3x3 squares
 forall(s in {{'A','B','C'},{'D','E','F'},{'G','H','I'}}, i in 0..2)
  all_different(union(x in s, y in {1+3*i,2+3*i,3+3*i}) {v(x,y)})

! Solve the problem
 solct:= 0
 while (cp_find_next_sol) do
  solct+=1
  print_solution(solct)
 end-do

 writeln("Number of solutions: ", solct)
 writeln("Time spent in enumeration: ",
         getparam("KALIS_COMPUTATION_TIME"), "sec")
 writeln("Number of nodes: ", getparam("KALIS_NODES"))

!****************************************************************
! Solution printing
 procedure print_solution(numsol: integer)
  writeln(getparam("KALIS_COMPUTATION_TIME"), "sec: Solution ", numsol)
  writeln("   A B C   D E F   G H I")
  forall(y in YS) do
   write(y, ": ")
   forall(x in XS)
    write(getsol(v(x,y)), if(x in {'C','F'}, " | ", " "))
   writeln
   if y mod 3 = 0 then
    writeln("   ---------------------")
   end-if
  end-do
 end-procedure

end-model


!****************************************************************

In this model, the call to cp_find_next_sol is embedded in a while loop to search all feasible solutions. At every loop execution the procedure print_solution is called to print out the solution found nicely formatted. Subroutines in Mosel may have declarations blocks for local declarations and they may take any number of arguments. Since, in our model, the call to the procedure occurs before its definition, we need to declare it before the first call using the keyword forward.

For selecting the information that is to be printed by the subroutine we use two different versions of Mosel's if statement: the inline if and if-then that includes a block of statements.

At the end of the model run we retrieve from the solver the run time measurement (parameter KALIS_COMPUTATION_TIME) and the number of nodes explored by the search (parameter KALIS_NODES).

To obtain a complete list of parameters defined by Xpress Kalis type the command

mosel exam -p kalis

(for a listing of the complete functionality of Xpress Kalis leave out the flag -p).

Results

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

0.16sec: Solution 1
   A B C   D E F   G H I
1: 8 6 9 | 2 4 3 | 1 5 7
2: 3 5 7 | 6 1 9 | 4 8 2
3: 2 4 1 | 8 7 5 | 3 6 9
   ---------------------
4: 4 9 8 | 1 3 2 | 6 7 5
5: 7 1 3 | 5 8 6 | 9 2 4
6: 6 2 5 | 7 9 4 | 8 3 1
   ---------------------
7: 1 7 6 | 4 2 8 | 5 9 3
8: 9 8 4 | 3 5 7 | 2 1 6
9: 5 3 2 | 9 6 1 | 7 4 8
   ---------------------
Number of solutions: 1
Time spent in enumeration: 0.41sec
Number of nodes: 2712 

The all_different relation takes an optional second argument that allows the user to specify the propagation algorithm to be used for evaluating the constraint. If we change from the default setting (KALIS_FORWARD_CHECKING) to the more aggressive strategy KALIS_GEN_ARC_CONSISTENCY by adding this choice as the second argument, for example,

  forall(y in YS)
   all_different(union(x in XS) {v(x,y)}, KALIS_GEN_ARC_CONSISTENCY)

we observe that the number of nodes is reduced to a single node—the problem is solved by simply posting the constraints. Whereas the time spent in the search is down to zero, the constraint posting now takes 4-5 times longer (still just a fraction of a second) due to the larger computational overhead of the generalized arc consistency algorithm. Allover, the time for problem definition and solving is reduced to less than a tenth of the previous time.

As a general rule, the generalized arc consistency algorithm achieves stronger pruning (i.e., it removes more values from the domains of the variables). However, due to the increase in computation time its use is not always justified. The reader is therefore encouraged to try both algorithm settings in his models.