[Help-glpk] Re: Sudoku puzzle

[Andrew Makhorin]

> Interesting to note that in many cases (even in the cases when the
> puzzle is classified as very hard) the lp relaxation is yet integer
> feasible and therefore branching is not needed, though Sudoku is
> proven to be np-hard. Moreover, many instances can be solved by the
> mip presolver (--intopt in glpsol 4.9).

The following data section describes a hard Sudoku puzzle and being
used with the model sudoku.mod
http://lists.gnu.org/archive/html/help-glpk/2006-03/msg00013.html
causes branching:

/* sudoku.dat, a hard Sudoku puzzle which causes branching */

data;

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

end;