You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
84 lines
2.5 KiB
84 lines
2.5 KiB
/* Numbrix, Number Placement Puzzle */
|
|
|
|
/* Written in GNU MathProg by Robert Wood <rwood@targus.com> */
|
|
|
|
/* Numbrix is a logic-based number-placement puzzle.[1]
|
|
* The objective is to fill the grid so that each cell contains
|
|
* digits in sequential order taking a horizontal or vertical
|
|
* path; diagonal paths are not allowed. The puzzle setter
|
|
* provides a grid often with the outer most cells completed.
|
|
*
|
|
* Completed Numbrix puzzles are usually a square of numbers
|
|
* in order from 1 to 64 (8x8 grid) or from 1 to 81 (9x9 grid),
|
|
* following a continuous path in sequence.
|
|
*
|
|
* The modern puzzle was invented by Marilyn vos Savant in 2008
|
|
* and published by Parade Magazine under the name "Numbrix",
|
|
* near her weekly Ask Marilyn article.
|
|
*
|
|
* http://en.wikipedia.org/wiki/Numbrix */
|
|
|
|
set I := {1..9};
|
|
set J := {1..9};
|
|
set VALS := {1..81};
|
|
|
|
param givens{I, J}, integer, >= 0, <= 81, default 0;
|
|
/* the "givens" */
|
|
|
|
param neighbors{i in I,j in J, i2 in I, j2 in J} , binary :=
|
|
(if abs(i - i2) + abs(j -j2) == 1 then
|
|
1
|
|
else
|
|
0
|
|
);
|
|
/* defines which spots are the boards are neighbors */
|
|
|
|
var x{i in I, j in J, k in VALS}, binary;
|
|
/* x[i,j,k] = 1 means cell [i,j] is assigned number k */
|
|
|
|
s.t. fa{i in I, j in J, k in VALS: givens[i,j] != 0}:
|
|
x[i,j,k] = (if givens[i,j] = k then 1 else 0);
|
|
/* assign pre-defined numbers using the "givens" */
|
|
|
|
s.t. fb{i in I, j in J}: sum{k in VALS} x[i,j,k] = 1;
|
|
/* each cell must be assigned exactly one number */
|
|
|
|
s.t. singleNum {k in VALS}: sum{i in I, j in J} x[i,j,k] = 1;
|
|
/* a value can only occur once */
|
|
|
|
s.t. neighborContraint {i in I, j in J, k in 1..80}:
|
|
x[i,j,k] <= sum{i2 in I, j2 in J} x[i2,j2,k+1] * neighbors[i,j,i2,j2];
|
|
/* each cell must have a neighbor with the next higher value */
|
|
|
|
|
|
/* there is no need for an objective function here */
|
|
|
|
|
|
solve;
|
|
|
|
for {i in I}
|
|
{ for {0..0: i = 1 or i = 4 or i = 7}
|
|
printf " +----------+----------+----------+\n";
|
|
for {j in J}
|
|
{ for {0..0: j = 1 or j = 4 or j = 7} printf(" |");
|
|
printf " %2d", sum{k in VALS} x[i,j,k] * k;
|
|
for {0..0: j = 9} printf(" |\n");
|
|
}
|
|
for {0..0: i = 9}
|
|
printf " +----------+----------+----------+\n";
|
|
}
|
|
|
|
data;
|
|
|
|
param givens : 1 2 3 4 5 6 7 8 9 :=
|
|
1 . . . . . . . . .
|
|
2 . 11 12 15 18 21 62 61 .
|
|
3 . 6 . . . . . 60 .
|
|
4 . 33 . . . . . 57 .
|
|
5 . 32 . . . . . 56 .
|
|
6 . 37 . . . . . 73 .
|
|
7 . 38 . . . . . 72 .
|
|
8 . 43 44 47 48 51 76 77 .
|
|
9 . . . . . . . . . ;
|
|
|
|
end;
|