COIN-OR::LEMON - Graph Library

source: lemon-project-template-glpk/deps/glpk/examples/sudoku.mod @ 9:33de93886c88

subpack-glpk
Last change on this file since 9:33de93886c88 was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import GLPK 4.47

File size: 2.5 KB
Line 
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
30param givens{1..9, 1..9}, integer, >= 0, <= 9, default 0;
31/* the "givens" */
32
33var 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
36s.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
40s.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
43s.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
46s.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
49s.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
55solve;
56
57for {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
69data;
70
71/* These data correspond to the example above. */
72
73param 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
84end;
Note: See TracBrowser for help on using the repository browser.