alpar@1: /* SUDOKU, Number Placement Puzzle */
alpar@1: 
alpar@1: /* Written in GNU MathProg by Andrew Makhorin <mao@mai2.rcnet.ru> */
alpar@1: 
alpar@1: /* This example shows how to use the table statement.
alpar@1:    The sudoku to be solves is read from file sudoku_in.csv.
alpar@1:    The solution is written to sudoku_out.csv.
alpar@1:    The file format is CSV as defined in
alpar@1:      RFC 4180 - Common Format and MIME Type for
alpar@1:      Comma-Separated Values (CSV) Files */
alpar@1: 
alpar@1: /* Sudoku, also known as Number Place, is a logic-based placement
alpar@1:    puzzle. The aim of the canonical puzzle is to enter a numerical
alpar@1:    digit from 1 through 9 in each cell of a 9x9 grid made up of 3x3
alpar@1:    subgrids (called "regions"), starting with various digits given in
alpar@1:    some cells (the "givens"). Each row, column, and region must contain
alpar@1:    only one instance of each numeral.
alpar@1: 
alpar@1:    Example:
alpar@1: 
alpar@1:    +-------+-------+-------+
alpar@1:    | 5 3 . | . 7 . | . . . |
alpar@1:    | 6 . . | 1 9 5 | . . . |
alpar@1:    | . 9 8 | . . . | . 6 . |
alpar@1:    +-------+-------+-------+
alpar@1:    | 8 . . | . 6 . | . . 3 |
alpar@1:    | 4 . . | 8 . 3 | . . 1 |
alpar@1:    | 7 . . | . 2 . | . . 6 |
alpar@1:    +-------+-------+-------+
alpar@1:    | . 6 . | . . . | 2 8 . |
alpar@1:    | . . . | 4 1 9 | . . 5 |
alpar@1:    | . . . | . 8 . | . 7 9 |
alpar@1:    +-------+-------+-------+
alpar@1: 
alpar@1:    (From Wikipedia, the free encyclopedia.) */
alpar@1: set fields dimen 2;
alpar@1: 
alpar@1: param id;
alpar@1: 
alpar@1: param givens{1..9, 1..9}, integer, >= 0, <= 9, default 0;
alpar@1: /* the "givens" */
alpar@1: 
alpar@1: /*
alpar@1: table ti IN 'MySQL' 'Database=glpk;UID=glpk;PWD=gnu'
alpar@1:   'sudoku' :
alpar@1:   fields <- [COL, LIN], givens ~ VAL;
alpar@1: */
alpar@1: table ti IN 'MySQL' 'Database=glpk;UID=glpk;PWD=gnu'
alpar@1:   'SELECT * FROM sudoku WHERE ID = ' & id :
alpar@1:   fields <- [COL, LIN], givens ~ VAL;
alpar@1: 
alpar@1: var x{i in 1..9, j in 1..9, k in 1..9}, binary;
alpar@1: /* x[i,j,k] = 1 means cell [i,j] is assigned number k */
alpar@1: 
alpar@1: s.t. fa{i in 1..9, j in 1..9, k in 1..9: givens[i,j] != 0}:
alpar@1:      x[i,j,k] = (if givens[i,j] = k then 1 else 0);
alpar@1: /* assign pre-defined numbers using the "givens" */
alpar@1: 
alpar@1: s.t. fb{i in 1..9, j in 1..9}: sum{k in 1..9} x[i,j,k] = 1;
alpar@1: /* each cell must be assigned exactly one number */
alpar@1: 
alpar@1: s.t. fc{i in 1..9, k in 1..9}: sum{j in 1..9} x[i,j,k] = 1;
alpar@1: /* cells in the same row must be assigned distinct numbers */
alpar@1: 
alpar@1: s.t. fd{j in 1..9, k in 1..9}: sum{i in 1..9} x[i,j,k] = 1;
alpar@1: /* cells in the same column must be assigned distinct numbers */
alpar@1: 
alpar@1: s.t. fe{I in 1..9 by 3, J in 1..9 by 3, k in 1..9}:
alpar@1:      sum{i in I..I+2, j in J..J+2} x[i,j,k] = 1;
alpar@1: /* cells in the same region must be assigned distinct numbers */
alpar@1: 
alpar@1: /* there is no need for an objective function here */
alpar@1: 
alpar@1: solve;
alpar@1: 
alpar@1: table ta{(i,j) in fields} OUT
alpar@1:   'MySQL' 'Database=glpk;UID=glpk;PWD=gnu'
alpar@1:   'DELETE FROM sudoku_solution'
alpar@1:   'WHERE ID = ' & id & ';'
alpar@1:   'INSERT INTO sudoku_solution'
alpar@1:   '(ID, COL, LIN, VAL)'
alpar@1:   'VALUES(?, ?, ?, ?);' :
alpar@1:   id ~ ID, i ~ COL, j ~ LIN, (sum{k in 1..9} x[i,j,k] * k) ~ VAL;
alpar@1: 
alpar@1: printf "\nSudoku to be solved\n";
alpar@1: for {i in 1..9}
alpar@1: {  for {0..0: i = 1 or i = 4 or i = 7}
alpar@1:      printf " +-------+-------+-------+\n";
alpar@1:    for {j in 1..9}
alpar@1:    {  for {0..0: j = 1 or j = 4 or j = 7} printf(" |");
alpar@1:       printf " %d", givens[i,j];
alpar@1:       for {0..0: j = 9} printf(" |\n");
alpar@1:    }
alpar@1:    for {0..0: i = 9}
alpar@1:    printf " +-------+-------+-------+\n";
alpar@1:    }
alpar@1: printf "\nSolution\n";
alpar@1: for {i in 1..9}
alpar@1: {  for {0..0: i = 1 or i = 4 or i = 7}
alpar@1:       printf " +-------+-------+-------+\n";
alpar@1:    for {j in 1..9}
alpar@1:    {  for {0..0: j = 1 or j = 4 or j = 7} printf(" |");
alpar@1:       printf " %d", sum{k in 1..9} x[i,j,k] * k;
alpar@1:       for {0..0: j = 9} printf(" |\n");
alpar@1:    }
alpar@1:    for {0..0: i = 9}
alpar@1:       printf " +-------+-------+-------+\n";
alpar@1: }
alpar@1: 
alpar@1: data;
alpar@1: 
alpar@1: param id := 1;
alpar@1: end;