lemon-project-template-glpk

comparison deps/glpk/examples/sql/sudoku_odbc.mod @ 9:33de93886c88

find changesets by author, revision, files, or words in the commit message
Import GLPK 4.47
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 20:59:10 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:a579835194b6
1 /* SUDOKU, Number Placement Puzzle */
2
3 /* Written in GNU MathProg by Andrew Makhorin <mao@mai2.rcnet.ru> */
4
5 /* This example shows how to use the table statement.
6 The sudoku to be solves is read from file sudoku_in.csv.
7 The solution is written to sudoku_out.csv.
8 The file format is CSV as defined in
9 RFC 4180 - Common Format and MIME Type for
10 Comma-Separated Values (CSV) Files */
11
12 /* Sudoku, also known as Number Place, is a logic-based placement
13 puzzle. The aim of the canonical puzzle is to enter a numerical
14 digit from 1 through 9 in each cell of a 9x9 grid made up of 3x3
15 subgrids (called "regions"), starting with various digits given in
16 some cells (the "givens"). Each row, column, and region must contain
17 only one instance of each numeral.
18
19 Example:
20
21 +-------+-------+-------+
22 | 5 3 . | . 7 . | . . . |
23 | 6 . . | 1 9 5 | . . . |
24 | . 9 8 | . . . | . 6 . |
25 +-------+-------+-------+
26 | 8 . . | . 6 . | . . 3 |
27 | 4 . . | 8 . 3 | . . 1 |
28 | 7 . . | . 2 . | . . 6 |
29 +-------+-------+-------+
30 | . 6 . | . . . | 2 8 . |
31 | . . . | 4 1 9 | . . 5 |
32 | . . . | . 8 . | . 7 9 |
33 +-------+-------+-------+
34
35 (From Wikipedia, the free encyclopedia.) */
36 set fields dimen 2;
37
38 param id;
39
40 param givens{1..9, 1..9}, integer, >= 0, <= 9, default 0;
41 /* the "givens" */
42
43 table ti IN 'iODBC'
44 'DSN=glpk;UID=glpk;PWD=gnu'
45 'SELECT * FROM sudoku'
46 'WHERE ID = ' & id :
47 fields <- [COL, LIN], givens ~ VAL;
48
49 var x{i in 1..9, j in 1..9, k in 1..9}, binary;
50 /* x[i,j,k] = 1 means cell [i,j] is assigned number k */
51
52 s.t. fa{i in 1..9, j in 1..9, k in 1..9: givens[i,j] != 0}:
53 x[i,j,k] = (if givens[i,j] = k then 1 else 0);
54 /* assign pre-defined numbers using the "givens" */
55
56 s.t. fb{i in 1..9, j in 1..9}: sum{k in 1..9} x[i,j,k] = 1;
57 /* each cell must be assigned exactly one number */
58
59 s.t. fc{i in 1..9, k in 1..9}: sum{j in 1..9} x[i,j,k] = 1;
60 /* cells in the same row must be assigned distinct numbers */
61
62 s.t. fd{j in 1..9, k in 1..9}: sum{i in 1..9} x[i,j,k] = 1;
63 /* cells in the same column must be assigned distinct numbers */
64
65 s.t. fe{I in 1..9 by 3, J in 1..9 by 3, k in 1..9}:
66 sum{i in I..I+2, j in J..J+2} x[i,j,k] = 1;
67 /* cells in the same region must be assigned distinct numbers */
68
69 /* there is no need for an objective function here */
70
71
72 solve;
73
74 table ta {(i, j) in {i1 in 1..9} cross {i2 in 1..9}} OUT
75 'iODBC' 'DSN=glpk;UID=glpk;PWD=gnu'
76 'DELETE FROM sudoku_solution'
77 'WHERE ID = ' & id & ';'
78 'INSERT INTO sudoku_solution'
79 '(ID, COL, LIN, VAL)'
80 'VALUES(?, ?, ?, ?);' :
81 id ~ ID, i ~ COL, j ~ LIN, (sum{k in 1..9} x[i,j,k] * k) ~ VAL;
82
83 printf "\nSudoku to be solved\n";
84 for {i in 1..9}
85 { for {0..0: i = 1 or i = 4 or i = 7}
86 printf " +-------+-------+-------+\n";
87 for {j in 1..9}
88 { for {0..0: j = 1 or j = 4 or j = 7} printf(" |");
89 printf " %d", givens[i,j];
90 for {0..0: j = 9} printf(" |\n");
91 }
92 for {0..0: i = 9}
93 printf " +-------+-------+-------+\n";
94 }
95 printf "\nSolution\n";
96 for {i in 1..9}
97 { for {0..0: i = 1 or i = 4 or i = 7}
98 printf " +-------+-------+-------+\n";
99 for {j in 1..9}
100 { for {0..0: j = 1 or j = 4 or j = 7} printf(" |");
101 printf " %d", sum{k in 1..9} x[i,j,k] * k;
102 for {0..0: j = 9} printf(" |\n");
103 }
104 for {0..0: i = 9}
105 printf " +-------+-------+-------+\n";
106 }
107
108 data;
109
110 param id := 1;
111 end;