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