lemon-project-template-glpk
view deps/glpk/examples/numbrix.mod @ 11:4fc6ad2fb8a6
Test GLPK in src/main.cc
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 21:43:29 +0100 |
| parents | |
| children |
line source
1 /* Numbrix, Number Placement Puzzle */
3 /* Written in GNU MathProg by Robert Wood <rwood@targus.com> */
5 /* Numbrix is a logic-based number-placement puzzle.[1]
6 * The objective is to fill the grid so that each cell contains
7 * digits in sequential order taking a horizontal or vertical
8 * path; diagonal paths are not allowed. The puzzle setter
9 * provides a grid often with the outer most cells completed.
10 *
11 * Completed Numbrix puzzles are usually a square of numbers
12 * in order from 1 to 64 (8x8 grid) or from 1 to 81 (9x9 grid),
13 * following a continuous path in sequence.
14 *
15 * The modern puzzle was invented by Marilyn vos Savant in 2008
16 * and published by Parade Magazine under the name "Numbrix",
17 * near her weekly Ask Marilyn article.
18 *
19 * http://en.wikipedia.org/wiki/Numbrix */
21 set I := {1..9};
22 set J := {1..9};
23 set VALS := {1..81};
25 param givens{I, J}, integer, >= 0, <= 81, default 0;
26 /* the "givens" */
28 param neighbors{i in I,j in J, i2 in I, j2 in J} , binary :=
29 (if abs(i - i2) + abs(j -j2) == 1 then
30 1
31 else
32 0
33 );
34 /* defines which spots are the boards are neighbors */
36 var x{i in I, j in J, k in VALS}, binary;
37 /* x[i,j,k] = 1 means cell [i,j] is assigned number k */
39 s.t. fa{i in I, j in J, k in VALS: givens[i,j] != 0}:
40 x[i,j,k] = (if givens[i,j] = k then 1 else 0);
41 /* assign pre-defined numbers using the "givens" */
43 s.t. fb{i in I, j in J}: sum{k in VALS} x[i,j,k] = 1;
44 /* each cell must be assigned exactly one number */
46 s.t. singleNum {k in VALS}: sum{i in I, j in J} x[i,j,k] = 1;
47 /* a value can only occur once */
49 s.t. neighborContraint {i in I, j in J, k in 1..80}:
50 x[i,j,k] <= sum{i2 in I, j2 in J} x[i2,j2,k+1] * neighbors[i,j,i2,j2];
51 /* each cell must have a neighbor with the next higher value */
54 /* there is no need for an objective function here */
57 solve;
59 for {i in I}
60 { for {0..0: i = 1 or i = 4 or i = 7}
61 printf " +----------+----------+----------+\n";
62 for {j in J}
63 { for {0..0: j = 1 or j = 4 or j = 7} printf(" |");
64 printf " %2d", sum{k in VALS} x[i,j,k] * k;
65 for {0..0: j = 9} printf(" |\n");
66 }
67 for {0..0: i = 9}
68 printf " +----------+----------+----------+\n";
69 }
71 data;
73 param givens : 1 2 3 4 5 6 7 8 9 :=
74 1 . . . . . . . . .
75 2 . 11 12 15 18 21 62 61 .
76 3 . 6 . . . . . 60 .
77 4 . 33 . . . . . 57 .
78 5 . 32 . . . . . 56 .
79 6 . 37 . . . . . 73 .
80 7 . 38 . . . . . 72 .
81 8 . 43 44 47 48 51 76 77 .
82 9 . . . . . . . . . ;
84 end;