[Help-glpk] extremely difficult sudoku puzzle

[Andrew Makhorin]

Just for fun:

/* sudoku.dat, "extremely difficult" Sudoku puzzle */

/* This Sudoku puzzle is taken from the book:
   Wei-Meng Lee, "Programming Sudoku", Apress, 2006, p.169,
   where it is rated as Extremely Difficult. Nevertheless glpsol solves
   it for less than a second with default settings. (It is interesting
   to note that the book mentioned above has more than 200 pages and is
   entirely dedicated to heuristics for solving Sudoku puzzles.) */

data;

param givens : 1 2 3 4 5 6 7 8 9 :=
           1   . . . . . 8 . . 9
           2   . 5 . . 9 . . . .
           3   . . 9 . . 4 8 . .
           4   . . 2 1 4 . . . 3
           5   . . 6 . . . 9 . .
           6   4 . . . 6 7 1 . .
           7   . . 5 9 . . 3 . .
           8   . . . . 3 . . 7 .
           9   8 . . 4 . . . . . ;

end;

GLPSOL: GLPK LP/MIP Solver, v4.43
Parameter(s) specified in the command line:
 -m sudoku.mod -d sudoku.dat --log log
Reading model section from sudoku.mod...
sudoku.mod:69: warning: data section ignored
69 lines were read
Reading data section from sudoku.dat...
23 lines were read
Generating fa...
Generating fb...
Generating fc...
Generating fd...
Generating fe...
Model has been successfully generated
GLPK Integer Optimizer, v4.43
540 rows, 729 columns, 3132 non-zeros
729 integer variables, all of which are binary
Preprocessing...
200 rows, 199 columns, 796 non-zeros
199 integer variables, all of which are binary
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 134
Solving LP relaxation...
GLPK Simplex Optimizer, v4.43
200 rows, 199 columns, 796 non-zeros
      0: obj =   0.000000000e+00  infeas =  7.000e+01 (66)
*    80: obj =   0.000000000e+00  infeas =  2.005e-14 (66)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+    80: mip =     not found yet >=              -inf        (1; 0)
+   109: >>>>>   0.000000000e+00 >=   0.000000000e+00   0.0% (5; 0)
+   109: mip =   0.000000000e+00 >=     tree is empty   0.0% (0; 9)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.1 secs
Memory used: 0.9 Mb (935563 bytes)
 +-------+-------+-------+
 | 1 6 4 | 7 5 8 | 2 3 9 |
 | 2 5 8 | 6 9 3 | 7 1 4 |
 | 3 7 9 | 2 1 4 | 8 6 5 |
 +-------+-------+-------+
 | 7 8 2 | 1 4 9 | 6 5 3 |
 | 5 1 6 | 3 8 2 | 9 4 7 |
 | 4 9 3 | 5 6 7 | 1 8 2 |
 +-------+-------+-------+
 | 6 4 5 | 9 7 1 | 3 2 8 |
 | 9 2 1 | 8 3 5 | 4 7 6 |
 | 8 3 7 | 4 2 6 | 5 9 1 |
 +-------+-------+-------+
Model has been successfully processed