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