(!****************************************************************
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
|
(!****************************************************************
CP example problems
===================
file sudoku2_ka.mos
```````````````````
Sudoku puzzle.
- Choosing the propagation algorithm -
*** 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) - 2"
uses "kalis", "mmsystem"
parameters
ALG = KALIS_GEN_ARC_CONSISTENCY ! or: KALIS_FORWARD_CHECKING
end-parameters
forward procedure print_solution(numsol: integer)
starttime:= gettime
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)}, ALG)
! All-different values in columns
forall(x in XS) all_different(union(y in YS) {v(x,y)}, ALG)
! 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)}, ALG)
writeln("Time for posting constraints: ", gettime-starttime, " sec")
! 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"))
writeln("Total time: ", gettime-starttime, " sec")
!****************************************************************
! 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
|
(!****************************************************************
CP example problems
===================
file sudoku_conflict.mos
````````````````````````
Sudoku puzzle.
- Analyzing infeasibilities in value assignments -
*** This model cannot be run with a Community Licence
for the provided data instance ***
(c) 2008 Artelys S.A. and Fair Isaac Corporation
Creation: 2008, rev. Mar. 2013
*****************************************************************!)
model "Conflicts"
uses "kalis"
forward procedure print_values
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
forall(x in XS,y in YS) setname(v(x,y), "v("+x+","+y+")")
setparam("KALIS_AUTO_PROPAGATE", 0) ! Disable automatic propagation
! 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)})
! Prompt user for new assignments
declarations
NX: array(1..9) of string
val: integer
end-declarations
NX::(1..9)['A','B','C','D','E','F','G','H','I']
cp_save_state
res:=cp_propagate
print_values
setrandseed(3)
while (res and (or(x in XS,y in YS) not is_fixed(v(x,y))) ) do
! Select randomly a yet unassigned cell
rx:=round(0.5+9*random); ry:=round(0.5+9*random)
while (is_fixed(v(NX(rx),ry))) do
rx:=round(0.5+9*random); ry:=round(0.5+9*random)
end-do
! Prompt for user input
writeln(v(NX(rx),ry), " = ")
readln(val)
! Add the new constraint
v(NX(rx),ry)=val ! State a new constraint
cp_save_state ! Save system state before propagation
res:=cp_propagate ! Propagate the new constraint
! Print resulting board
print_values
end-do
! An infeasible state has been reached
if not res then
cp_restore_state ! Restore state before propagation
cp_infeas_analysis ! Analyze infeasibility, print report
else
writeln("Problem solved")
end-if
!****************************************************************
! Print fixed values
procedure print_values
writeln(" A B C D E F G H I")
forall(y in YS) do
write(y, ": ")
forall(x in XS)
write(if(is_fixed(v(x,y)), string(getval(v(x,y))), "."),
if(x in {'C','F'}, " | ", " "))
writeln
if y mod 3 = 0 then
writeln(" ---------------------")
end-if
end-do
end-procedure
end-model
|
