1 | /* A solver for the Japanese number-puzzle Shikaku |
---|
2 | * http://en.wikipedia.org/wiki/Shikaku |
---|
3 | * |
---|
4 | * Sebastian Nowozin <nowozin@gmail.com>, 27th January 2009 |
---|
5 | */ |
---|
6 | |
---|
7 | param ndim := 10; |
---|
8 | set rows := 1..ndim; |
---|
9 | set rows1 := 1..(ndim+1); |
---|
10 | set cols := 1..ndim; |
---|
11 | set cols1 := 1..(ndim+1); |
---|
12 | param givens{rows, cols}, integer, >= 0, default 0; |
---|
13 | |
---|
14 | /* Set of vertices as (row,col) coordinates */ |
---|
15 | set V := { (i,j) in { rows, cols }: givens[i,j] != 0 }; |
---|
16 | |
---|
17 | /* Set of all feasible boxes of the right size: only this boxes are possible. |
---|
18 | * The box contains (i,j) and ranges from (k,l) to (m,n) |
---|
19 | */ |
---|
20 | set B := { (i,j,k,l,m,n) in { V, rows, cols, rows1, cols1 }: |
---|
21 | i >= k and i < m and j >= l and j < n and /* Contains (i,j) */ |
---|
22 | ((m-k)*(n-l)) = givens[i,j] and /* Right size */ |
---|
23 | card({ (s,t) in V: s >= k and s < m and t >= l and t < n }) = 1 |
---|
24 | /* Contains only (i,j), no other number */ |
---|
25 | }; |
---|
26 | |
---|
27 | var x{B}, binary; |
---|
28 | |
---|
29 | /* Cover each square exactly once */ |
---|
30 | s.t. cover_once{ (s,t) in { rows, cols } }: |
---|
31 | sum{(i,j,k,l,m,n) in B: s >= k and s < m and t >= l and t < n} |
---|
32 | x[i,j,k,l,m,n] = 1; |
---|
33 | |
---|
34 | minimize cost: 0; |
---|
35 | |
---|
36 | solve; |
---|
37 | |
---|
38 | /* Output solution graphically */ |
---|
39 | printf "\nSolution:\n"; |
---|
40 | for { row in rows1 } { |
---|
41 | for { col in cols1 } { |
---|
42 | printf{0..0: card({(i,j,k,l,m,n) in B: |
---|
43 | col >= l and col <= n and (row = k or row = m) and |
---|
44 | x[i,j,k,l,m,n] = 1}) > 0 and |
---|
45 | card({(i,j,k,l,m,n) in B: |
---|
46 | row >= k and row <= m and (col = l or col = n) and |
---|
47 | x[i,j,k,l,m,n] = 1}) > 0} "+"; |
---|
48 | printf{0..0: card({(i,j,k,l,m,n) in B: |
---|
49 | col >= l and col <= n and (row = k or row = m) and |
---|
50 | x[i,j,k,l,m,n] = 1}) = 0 and |
---|
51 | card({(i,j,k,l,m,n) in B: |
---|
52 | row >= k and row <= m and (col = l or col = n) and |
---|
53 | x[i,j,k,l,m,n] = 1}) > 0} "|"; |
---|
54 | printf{0..0: card({(i,j,k,l,m,n) in B: |
---|
55 | row >= k and row <= m and (col = l or col = n) and |
---|
56 | x[i,j,k,l,m,n] = 1}) = 0 and |
---|
57 | card({(i,j,k,l,m,n) in B: |
---|
58 | col >= l and col <= n and (row = k or row = m) and |
---|
59 | x[i,j,k,l,m,n] = 1}) > 0} "-"; |
---|
60 | printf{0..0: card({(i,j,k,l,m,n) in B: |
---|
61 | row >= k and row <= m and (col = l or col = n) and |
---|
62 | x[i,j,k,l,m,n] = 1}) = 0 and |
---|
63 | card({(i,j,k,l,m,n) in B: |
---|
64 | col >= l and col <= n and (row = k or row = m) and |
---|
65 | x[i,j,k,l,m,n] = 1}) = 0} " "; |
---|
66 | |
---|
67 | printf{0..0: card({(i,j,k,l,m,n) in B: |
---|
68 | col >= l and col < n and (row = k or row = m) and |
---|
69 | x[i,j,k,l,m,n] = 1}) > 0} "---"; |
---|
70 | printf{0..0: card({(i,j,k,l,m,n) in B: |
---|
71 | col >= l and col < n and (row = k or row = m) and |
---|
72 | x[i,j,k,l,m,n] = 1}) = 0} " "; |
---|
73 | } |
---|
74 | printf "\n"; |
---|
75 | |
---|
76 | for { (col,p) in { cols, 1 }: card({ s in rows: s = row }) = 1 } { |
---|
77 | printf{0..0: card({(i,j,k,l,m,n) in B: |
---|
78 | row >= k and row < m and (col = l or col = n) and |
---|
79 | x[i,j,k,l,m,n] = 1}) > 0} "|"; |
---|
80 | printf{0..0: card({(i,j,k,l,m,n) in B: |
---|
81 | row >= k and row < m and (col = l or col = n) and |
---|
82 | x[i,j,k,l,m,n] = 1}) = 0} " "; |
---|
83 | printf{0..0: card({ (i,j) in V: i = row and j = col}) > 0} " %2d", givens[row,col]; |
---|
84 | printf{0..0: card({ (i,j) in V: i = row and j = col}) = 0} " ."; |
---|
85 | } |
---|
86 | printf{0..0: card({ r in rows: r = row }) = 1} "|\n"; |
---|
87 | } |
---|
88 | |
---|
89 | data; |
---|
90 | |
---|
91 | /* This Shikaku is from |
---|
92 | * http://www.emn.fr/x-info/sdemasse/gccat/KShikaku.html#uid5449 |
---|
93 | */ |
---|
94 | param givens : 1 2 3 4 5 6 7 8 9 10 := |
---|
95 | 1 9 . . . 12 . . 5 . . |
---|
96 | 2 . . . . . . . . . . |
---|
97 | 3 . . . . . . . . . 6 |
---|
98 | 4 8 . 6 . 8 . . . . . |
---|
99 | 5 . . . . . . . . . . |
---|
100 | 6 . . . . . . . . . . |
---|
101 | 7 . . . . . 6 . 8 . 12 |
---|
102 | 8 4 . . . . . . . . . |
---|
103 | 9 . . . . . . . . . . |
---|
104 | 10 . . 3 . . 9 . . . 4 |
---|
105 | ; |
---|
106 | |
---|
107 | end; |
---|