diff options
Diffstat (limited to 'glpk-5.0/examples/shikaku.mod')
| -rw-r--r-- | glpk-5.0/examples/shikaku.mod | 107 |
1 files changed, 107 insertions, 0 deletions
diff --git a/glpk-5.0/examples/shikaku.mod b/glpk-5.0/examples/shikaku.mod new file mode 100644 index 0000000..19cf5dd --- /dev/null +++ b/glpk-5.0/examples/shikaku.mod @@ -0,0 +1,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; |