1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/examples/numbrix.mod	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,84 @@
     1.4 +/* Numbrix, Number Placement Puzzle */
     1.5 +
     1.6 +/* Written in GNU MathProg by Robert Wood <rwood@targus.com>  */
     1.7 +
     1.8 +/* Numbrix is a logic-based number-placement puzzle.[1]
     1.9 + * The objective is to fill the grid so that each cell contains
    1.10 + * digits in sequential order taking a horizontal or vertical
    1.11 + * path; diagonal paths are not allowed. The puzzle setter
    1.12 + * provides a grid often with the outer most cells completed.
    1.13 + *
    1.14 + * Completed Numbrix puzzles are usually a square of numbers
    1.15 + * in order from 1 to 64 (8x8 grid) or from 1 to 81 (9x9 grid),
    1.16 + * following a continuous path in sequence.
    1.17 + *
    1.18 + * The modern puzzle was invented by Marilyn vos Savant in 2008
    1.19 + * and published by Parade Magazine under the name "Numbrix",
    1.20 + * near her weekly Ask Marilyn article.
    1.21 + *
    1.22 + *    http://en.wikipedia.org/wiki/Numbrix  */
    1.23 +
    1.24 +set I := {1..9};
    1.25 +set J := {1..9};
    1.26 +set VALS := {1..81};
    1.27 +
    1.28 +param givens{I, J}, integer, >= 0, <= 81, default 0;
    1.29 +/* the "givens" */
    1.30 +
    1.31 +param neighbors{i in I,j in J, i2 in I, j2 in J} , binary :=
    1.32 +(if abs(i - i2) + abs(j -j2) == 1 then
    1.33 +     1
    1.34 + else
    1.35 +     0
    1.36 +);
    1.37 +/*  defines which spots are the boards are neighbors */
    1.38 +
    1.39 +var x{i in I, j in J, k in VALS}, binary;
    1.40 +/* x[i,j,k] = 1 means cell [i,j] is assigned number k */
    1.41 +
    1.42 +s.t. fa{i in I, j in J, k in VALS: givens[i,j] != 0}:
    1.43 +     x[i,j,k] = (if givens[i,j] = k then 1 else 0);
    1.44 +/* assign pre-defined numbers using the "givens" */
    1.45 +
    1.46 +s.t. fb{i in I, j in J}: sum{k in VALS} x[i,j,k] = 1;
    1.47 +/* each cell must be assigned exactly one number */
    1.48 +
    1.49 +s.t. singleNum {k in VALS}:  sum{i in I, j in J} x[i,j,k] = 1;
    1.50 +/*  a value can only occur once */
    1.51 +
    1.52 +s.t. neighborContraint {i in I, j in J, k in 1..80}:
    1.53 +        x[i,j,k] <= sum{i2 in I, j2 in J} x[i2,j2,k+1] * neighbors[i,j,i2,j2];
    1.54 +/* each cell must have a neighbor with the next higher value */
    1.55 +
    1.56 +
    1.57 +/* there is no need for an objective function here */
    1.58 +
    1.59 +
    1.60 +solve;
    1.61 +
    1.62 +for {i in I}
    1.63 +{  for {0..0: i = 1 or i = 4 or i = 7}
    1.64 +      printf " +----------+----------+----------+\n";
    1.65 +   for {j in J}
    1.66 +   {  for {0..0: j = 1 or j = 4 or j = 7} printf(" |");
    1.67 +      printf " %2d", sum{k in VALS} x[i,j,k] * k;
    1.68 +      for {0..0: j = 9} printf(" |\n");
    1.69 +   }
    1.70 +   for {0..0: i = 9}
    1.71 +      printf " +----------+----------+----------+\n";
    1.72 +}
    1.73 +
    1.74 +data;
    1.75 +
    1.76 +param givens : 1 2 3 4 5 6 7 8 9 :=
    1.77 +           1   . . . . . . . . .
    1.78 +           2   . 11 12 15 18 21 62 61 .
    1.79 +           3   .  6 . . . . . 60 .
    1.80 +           4   . 33 . . . . . 57 .
    1.81 +           5   . 32 . . . . . 56 .
    1.82 +           6   . 37 . . . . . 73 .
    1.83 +           7   . 38 . . . . . 72 .
    1.84 +           8   . 43 44 47 48 51 76 77 .
    1.85 +           9   . . . . . . . . . ;
    1.86 +
    1.87 +end;