FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Sudoku puzzle: retrieving status information through parameters

Description
Sudoku puzzle:
  • 'all-different' constraints; retrieving status information through parameters (sudoku_ka.mos).
  • Changing the propagation algorithm; time measures with "gettime" (sudoku2_ka.mos).
Further explanation of this example: 'Xpress Kalis User Guide', Section 3.3 all_different: Sudoku


Source Files





sudoku_ka.mos

(!****************************************************************
   CP example problems
   ===================
   
   file sudoku_ka.mos
   ``````````````````
   Sudoku puzzle.

   *** This model cannot be run with a Community Licence 
       for the provided data instance ***

   (c) 2008 Artelys S.A. and Fair Isaac Corporation
       Creation: 2005, rev. Mar. 2013        
*****************************************************************!)

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 


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

Other data sets:

! "The Times", 26 January, 2005
 v('E',1)=4; v('F',1)=3; v('H',1)=6
 v('B',2)=6; v('C',2)=5; v('G',2)=7
 v('A',3)=8; v('D',3)=7; v('I',3)=3
 v('B',4)=5; v('F',4)=1; v('G',4)=3; v('I',4)=7
 v('A',5)=1; v('B',5)=2; v('H',5)=8; v('I',5)=4
 v('A',6)=9; v('C',6)=7; v('D',6)=5; v('H',6)=2
 v('A',7)=4; v('F',7)=5; v('I',7)=9
 v('C',8)=9; v('G',8)=4; v('H',8)=5 
 v('B',9)=3; v('D',9)=4; v('E',9)=6 

! "The Guardian", 3 August, 2005
 v('B',1)=4; v('C',1)=9; v('D',1)=1; v('F',1)=6
 v('A',2)=7; v('F',2)=3
 v('A',3)=1; v('F',3)=4
 v('A',4)=8; v('G',4)=3; v('H',4)=1; v('I',4)=7
 v('A',6)=6; v('B',6)=2; v('C',6)=7; v('I',6)=9
 v('D',7)=8; v('I',7)=1
 v('D',8)=7; v('I',8)=2 
 v('D',9)=5; v('F',9)=2; v('G',9)=4; v('H',9)=9 

Back to examples browserPrevious exampleNext example