(!**************************************************************** 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