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