lemon-project-template-glpk
diff deps/glpk/examples/sudoku.mod @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/deps/glpk/examples/sudoku.mod Sun Nov 06 20:59:10 2011 +0100 1.3 @@ -0,0 +1,84 @@ 1.4 +/* SUDOKU, Number Placement Puzzle */ 1.5 + 1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ 1.7 + 1.8 +/* Sudoku, also known as Number Place, is a logic-based placement 1.9 + puzzle. The aim of the canonical puzzle is to enter a numerical 1.10 + digit from 1 through 9 in each cell of a 9x9 grid made up of 3x3 1.11 + subgrids (called "regions"), starting with various digits given in 1.12 + some cells (the "givens"). Each row, column, and region must contain 1.13 + only one instance of each numeral. 1.14 + 1.15 + Example: 1.16 + 1.17 + +-------+-------+-------+ 1.18 + | 5 3 . | . 7 . | . . . | 1.19 + | 6 . . | 1 9 5 | . . . | 1.20 + | . 9 8 | . . . | . 6 . | 1.21 + +-------+-------+-------+ 1.22 + | 8 . . | . 6 . | . . 3 | 1.23 + | 4 . . | 8 . 3 | . . 1 | 1.24 + | 7 . . | . 2 . | . . 6 | 1.25 + +-------+-------+-------+ 1.26 + | . 6 . | . . . | 2 8 . | 1.27 + | . . . | 4 1 9 | . . 5 | 1.28 + | . . . | . 8 . | . 7 9 | 1.29 + +-------+-------+-------+ 1.30 + 1.31 + (From Wikipedia, the free encyclopedia.) */ 1.32 + 1.33 +param givens{1..9, 1..9}, integer, >= 0, <= 9, default 0; 1.34 +/* the "givens" */ 1.35 + 1.36 +var x{i in 1..9, j in 1..9, k in 1..9}, binary; 1.37 +/* x[i,j,k] = 1 means cell [i,j] is assigned number k */ 1.38 + 1.39 +s.t. fa{i in 1..9, j in 1..9, k in 1..9: givens[i,j] != 0}: 1.40 + x[i,j,k] = (if givens[i,j] = k then 1 else 0); 1.41 +/* assign pre-defined numbers using the "givens" */ 1.42 + 1.43 +s.t. fb{i in 1..9, j in 1..9}: sum{k in 1..9} x[i,j,k] = 1; 1.44 +/* each cell must be assigned exactly one number */ 1.45 + 1.46 +s.t. fc{i in 1..9, k in 1..9}: sum{j in 1..9} x[i,j,k] = 1; 1.47 +/* cells in the same row must be assigned distinct numbers */ 1.48 + 1.49 +s.t. fd{j in 1..9, k in 1..9}: sum{i in 1..9} x[i,j,k] = 1; 1.50 +/* cells in the same column must be assigned distinct numbers */ 1.51 + 1.52 +s.t. fe{I in 1..9 by 3, J in 1..9 by 3, k in 1..9}: 1.53 + sum{i in I..I+2, j in J..J+2} x[i,j,k] = 1; 1.54 +/* cells in the same region must be assigned distinct numbers */ 1.55 + 1.56 +/* there is no need for an objective function here */ 1.57 + 1.58 +solve; 1.59 + 1.60 +for {i in 1..9} 1.61 +{ for {0..0: i = 1 or i = 4 or i = 7} 1.62 + printf " +-------+-------+-------+\n"; 1.63 + for {j in 1..9} 1.64 + { for {0..0: j = 1 or j = 4 or j = 7} printf(" |"); 1.65 + printf " %d", sum{k in 1..9} x[i,j,k] * k; 1.66 + for {0..0: j = 9} printf(" |\n"); 1.67 + } 1.68 + for {0..0: i = 9} 1.69 + printf " +-------+-------+-------+\n"; 1.70 +} 1.71 + 1.72 +data; 1.73 + 1.74 +/* These data correspond to the example above. */ 1.75 + 1.76 +param givens : 1 2 3 4 5 6 7 8 9 := 1.77 + 1 5 3 . . 7 . . . . 1.78 + 2 6 . . 1 9 5 . . . 1.79 + 3 . 9 8 . . . . 6 . 1.80 + 4 8 . . . 6 . . . 3 1.81 + 5 4 . . 8 . 3 . . 1 1.82 + 6 7 . . . 2 . . . 6 1.83 + 7 . 6 . . . . 2 8 . 1.84 + 8 . . . 4 1 9 . . 5 1.85 + 9 . . . . 8 . . 7 9 ; 1.86 + 1.87 +end;