lemon-project-template-glpk

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