1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/examples/shikaku.mod	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,107 @@
     1.4 +/* A solver for the Japanese number-puzzle Shikaku
     1.5 + * http://en.wikipedia.org/wiki/Shikaku
     1.6 + *
     1.7 + * Sebastian Nowozin <nowozin@gmail.com>, 27th January 2009
     1.8 + */
     1.9 +
    1.10 +param ndim := 10;
    1.11 +set rows := 1..ndim;
    1.12 +set rows1 := 1..(ndim+1);
    1.13 +set cols := 1..ndim;
    1.14 +set cols1 := 1..(ndim+1);
    1.15 +param givens{rows, cols}, integer, >= 0, default 0;
    1.16 +
    1.17 +/* Set of vertices as (row,col) coordinates */
    1.18 +set V := { (i,j) in { rows, cols }: givens[i,j] != 0 };
    1.19 +
    1.20 +/* Set of all feasible boxes of the right size: only this boxes are possible.
    1.21 + * The box contains (i,j) and ranges from (k,l) to (m,n)
    1.22 + */
    1.23 +set B := { (i,j,k,l,m,n) in { V, rows, cols, rows1, cols1 }:
    1.24 +    i >= k and i < m and j >= l and j < n and   /* Contains (i,j) */
    1.25 +    ((m-k)*(n-l)) = givens[i,j] and /* Right size */
    1.26 +    card({ (s,t) in V: s >= k and s < m and t >= l and t < n }) = 1
    1.27 +        /* Contains only (i,j), no other number */
    1.28 +};
    1.29 +
    1.30 +var x{B}, binary;
    1.31 +
    1.32 +/* Cover each square exactly once */
    1.33 +s.t. cover_once{ (s,t) in { rows, cols } }:
    1.34 +    sum{(i,j,k,l,m,n) in B: s >= k and s < m and t >= l and t < n}
    1.35 +        x[i,j,k,l,m,n] = 1;
    1.36 +
    1.37 +minimize cost: 0;
    1.38 +
    1.39 +solve;
    1.40 +
    1.41 +/* Output solution graphically */
    1.42 +printf "\nSolution:\n";
    1.43 +for { row in rows1 } {
    1.44 +    for { col in cols1 } {
    1.45 +        printf{0..0: card({(i,j,k,l,m,n) in B:
    1.46 +                col >= l and col <= n and (row = k or row = m) and
    1.47 +                x[i,j,k,l,m,n] = 1}) > 0 and
    1.48 +            card({(i,j,k,l,m,n) in B:
    1.49 +                row >= k and row <= m and (col = l or col = n) and
    1.50 +                x[i,j,k,l,m,n] = 1}) > 0} "+";
    1.51 +        printf{0..0: card({(i,j,k,l,m,n) in B:
    1.52 +                col >= l and col <= n and (row = k or row = m) and
    1.53 +                x[i,j,k,l,m,n] = 1}) = 0 and
    1.54 +            card({(i,j,k,l,m,n) in B:
    1.55 +                row >= k and row <= m and (col = l or col = n) and
    1.56 +                x[i,j,k,l,m,n] = 1}) > 0} "|";
    1.57 +        printf{0..0: card({(i,j,k,l,m,n) in B:
    1.58 +                row >= k and row <= m and (col = l or col = n) and
    1.59 +                x[i,j,k,l,m,n] = 1}) = 0 and
    1.60 +            card({(i,j,k,l,m,n) in B:
    1.61 +                col >= l and col <= n and (row = k or row = m) and
    1.62 +                x[i,j,k,l,m,n] = 1}) > 0} "-";
    1.63 +        printf{0..0: card({(i,j,k,l,m,n) in B:
    1.64 +                row >= k and row <= m and (col = l or col = n) and
    1.65 +                x[i,j,k,l,m,n] = 1}) = 0 and
    1.66 +            card({(i,j,k,l,m,n) in B:
    1.67 +                col >= l and col <= n and (row = k or row = m) and
    1.68 +                x[i,j,k,l,m,n] = 1}) = 0} " ";
    1.69 +
    1.70 +        printf{0..0: card({(i,j,k,l,m,n) in B:
    1.71 +            col >= l and col < n and (row = k or row = m) and
    1.72 +            x[i,j,k,l,m,n] = 1}) > 0} "---";
    1.73 +        printf{0..0: card({(i,j,k,l,m,n) in B:
    1.74 +            col >= l and col < n and (row = k or row = m) and
    1.75 +            x[i,j,k,l,m,n] = 1}) = 0} "   ";
    1.76 +    }
    1.77 +    printf "\n";
    1.78 +
    1.79 +    for { (col,p) in { cols, 1 }: card({ s in rows: s = row }) = 1 } {
    1.80 +        printf{0..0: card({(i,j,k,l,m,n) in B:
    1.81 +            row >= k and row < m and (col = l or col = n) and
    1.82 +            x[i,j,k,l,m,n] = 1}) > 0} "|";
    1.83 +        printf{0..0: card({(i,j,k,l,m,n) in B:
    1.84 +            row >= k and row < m and (col = l or col = n) and
    1.85 +            x[i,j,k,l,m,n] = 1}) = 0} " ";
    1.86 +        printf{0..0: card({ (i,j) in V: i = row and j = col}) > 0} " %2d", givens[row,col];
    1.87 +        printf{0..0: card({ (i,j) in V: i = row and j = col}) = 0} "  .";
    1.88 +    }
    1.89 +    printf{0..0: card({ r in rows: r = row }) = 1} "|\n";
    1.90 +}
    1.91 +
    1.92 +data;
    1.93 +
    1.94 +/* This Shikaku is from
    1.95 + * http://www.emn.fr/x-info/sdemasse/gccat/KShikaku.html#uid5449
    1.96 + */
    1.97 +param givens : 1 2 3 4 5 6 7 8 9 10 :=
    1.98 +           1   9 . . . 12 . . 5 . .
    1.99 +           2   . . . . . . . . . .
   1.100 +           3   . . . . . . . . . 6
   1.101 +           4   8 . 6 . 8 . . . . .
   1.102 +           5   . . . . . . . . . .
   1.103 +           6   . . . . . . . . . .
   1.104 +           7   . . . . . 6 . 8 . 12
   1.105 +           8   4 . . . . . . . . .
   1.106 +           9   . . . . . . . . . .
   1.107 +          10   . . 3 . . 9 . . . 4
   1.108 +           ;
   1.109 +
   1.110 +end;