|
1 /* Numbrix, Number Placement Puzzle */ |
|
2 |
|
3 /* Written in GNU MathProg by Robert Wood <rwood@targus.com> */ |
|
4 |
|
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 */ |
|
20 |
|
21 set I := {1..9}; |
|
22 set J := {1..9}; |
|
23 set VALS := {1..81}; |
|
24 |
|
25 param givens{I, J}, integer, >= 0, <= 81, default 0; |
|
26 /* the "givens" */ |
|
27 |
|
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 */ |
|
35 |
|
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 */ |
|
38 |
|
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" */ |
|
42 |
|
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 */ |
|
45 |
|
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 */ |
|
48 |
|
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 */ |
|
52 |
|
53 |
|
54 /* there is no need for an objective function here */ |
|
55 |
|
56 |
|
57 solve; |
|
58 |
|
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 } |
|
70 |
|
71 data; |
|
72 |
|
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 . . . . . . . . . ; |
|
83 |
|
84 end; |