COIN-OR::LEMON - Graph Library

source: glpk-cmake/examples/shikaku.mod

Last change on this file was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

  • Generated files and doc/notes are removed
File size: 3.8 KB
Line 
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
7param ndim := 10;
8set rows := 1..ndim;
9set rows1 := 1..(ndim+1);
10set cols := 1..ndim;
11set cols1 := 1..(ndim+1);
12param givens{rows, cols}, integer, >= 0, default 0;
13
14/* Set of vertices as (row,col) coordinates */
15set 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 */
20set 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
27var x{B}, binary;
28
29/* Cover each square exactly once */
30s.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
34minimize cost: 0;
35
36solve;
37
38/* Output solution graphically */
39printf "\nSolution:\n";
40for { 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
89data;
90
91/* This Shikaku is from
92 * http://www.emn.fr/x-info/sdemasse/gccat/KShikaku.html#uid5449
93 */
94param 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
107end;
Note: See TracBrowser for help on using the repository browser.