|
1 /* SUDOKU, Number Placement Puzzle */ |
|
2 |
|
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ |
|
4 |
|
5 /* Sudoku, also known as Number Place, is a logic-based placement |
|
6 puzzle. The aim of the canonical puzzle is to enter a numerical |
|
7 digit from 1 through 9 in each cell of a 9x9 grid made up of 3x3 |
|
8 subgrids (called "regions"), starting with various digits given in |
|
9 some cells (the "givens"). Each row, column, and region must contain |
|
10 only one instance of each numeral. |
|
11 |
|
12 Example: |
|
13 |
|
14 +-------+-------+-------+ |
|
15 | 5 3 . | . 7 . | . . . | |
|
16 | 6 . . | 1 9 5 | . . . | |
|
17 | . 9 8 | . . . | . 6 . | |
|
18 +-------+-------+-------+ |
|
19 | 8 . . | . 6 . | . . 3 | |
|
20 | 4 . . | 8 . 3 | . . 1 | |
|
21 | 7 . . | . 2 . | . . 6 | |
|
22 +-------+-------+-------+ |
|
23 | . 6 . | . . . | 2 8 . | |
|
24 | . . . | 4 1 9 | . . 5 | |
|
25 | . . . | . 8 . | . 7 9 | |
|
26 +-------+-------+-------+ |
|
27 |
|
28 (From Wikipedia, the free encyclopedia.) */ |
|
29 |
|
30 param givens{1..9, 1..9}, integer, >= 0, <= 9, default 0; |
|
31 /* the "givens" */ |
|
32 |
|
33 var x{i in 1..9, j in 1..9, k in 1..9}, binary; |
|
34 /* x[i,j,k] = 1 means cell [i,j] is assigned number k */ |
|
35 |
|
36 s.t. fa{i in 1..9, j in 1..9, k in 1..9: givens[i,j] != 0}: |
|
37 x[i,j,k] = (if givens[i,j] = k then 1 else 0); |
|
38 /* assign pre-defined numbers using the "givens" */ |
|
39 |
|
40 s.t. fb{i in 1..9, j in 1..9}: sum{k in 1..9} x[i,j,k] = 1; |
|
41 /* each cell must be assigned exactly one number */ |
|
42 |
|
43 s.t. fc{i in 1..9, k in 1..9}: sum{j in 1..9} x[i,j,k] = 1; |
|
44 /* cells in the same row must be assigned distinct numbers */ |
|
45 |
|
46 s.t. fd{j in 1..9, k in 1..9}: sum{i in 1..9} x[i,j,k] = 1; |
|
47 /* cells in the same column must be assigned distinct numbers */ |
|
48 |
|
49 s.t. fe{I in 1..9 by 3, J in 1..9 by 3, k in 1..9}: |
|
50 sum{i in I..I+2, j in J..J+2} x[i,j,k] = 1; |
|
51 /* cells in the same region must be assigned distinct numbers */ |
|
52 |
|
53 /* there is no need for an objective function here */ |
|
54 |
|
55 solve; |
|
56 |
|
57 for {i in 1..9} |
|
58 { for {0..0: i = 1 or i = 4 or i = 7} |
|
59 printf " +-------+-------+-------+\n"; |
|
60 for {j in 1..9} |
|
61 { for {0..0: j = 1 or j = 4 or j = 7} printf(" |"); |
|
62 printf " %d", sum{k in 1..9} x[i,j,k] * k; |
|
63 for {0..0: j = 9} printf(" |\n"); |
|
64 } |
|
65 for {0..0: i = 9} |
|
66 printf " +-------+-------+-------+\n"; |
|
67 } |
|
68 |
|
69 data; |
|
70 |
|
71 /* These data correspond to the example above. */ |
|
72 |
|
73 param givens : 1 2 3 4 5 6 7 8 9 := |
|
74 1 5 3 . . 7 . . . . |
|
75 2 6 . . 1 9 5 . . . |
|
76 3 . 9 8 . . . . 6 . |
|
77 4 8 . . . 6 . . . 3 |
|
78 5 4 . . 8 . 3 . . 1 |
|
79 6 7 . . . 2 . . . 6 |
|
80 7 . 6 . . . . 2 8 . |
|
81 8 . . . 4 1 9 . . 5 |
|
82 9 . . . . 8 . . 7 9 ; |
|
83 |
|
84 end; |