[9] | 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 | |
---|
| 30 | param givens{1..9, 1..9}, integer, >= 0, <= 9, default 0; |
---|
| 31 | /* the "givens" */ |
---|
| 32 | |
---|
| 33 | var 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 | |
---|
| 36 | s.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 | |
---|
| 40 | s.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 | |
---|
| 43 | s.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 | |
---|
| 46 | s.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 | |
---|
| 49 | s.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 | |
---|
| 55 | solve; |
---|
| 56 | |
---|
| 57 | for {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 | |
---|
| 69 | data; |
---|
| 70 | |
---|
| 71 | /* These data correspond to the example above. */ |
---|
| 72 | |
---|
| 73 | param 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 | |
---|
| 84 | end; |
---|