[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] Re: Sudoku puzzle
From: |
Andrew Makhorin |
Subject: |
[Help-glpk] Re: Sudoku puzzle |
Date: |
Thu, 30 Mar 2006 17:36:00 +0400 |
> 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;
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Help-glpk] Re: Sudoku puzzle,
Andrew Makhorin <=