Re: [Help-glpk] extremely difficult sudoku puzzle

[Diamantini Maurice]

Le 7 févr. 2010 à 04:14, Andrew Makhorin a écrit :

> 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 . . . . . ;

Just some remarks about complexity of sudoku
1 - The difficulty of a sudoku grid is just for a human which has
    to build cell by cell the missing elements **without**
    enumerate (backtracking in difficult for an human :-).
2 - A valid grid sudoku probleme has to had one and only once
    solution.
3 - The difficulty of a grid is mesured from the rules the human
    has to use for filling the missing elements (without enumeration)
4 - this grid is false because it has many solutions!

=> with choco (free java constraint programming library)
   http://www.emn.fr/z-info/choco-solver

The result of initial problem is:
...
1441 solutions trouvées en 2898 noeuds, 1967 ms

The result of another probleme obtained by filling the free element is:
 
----- Problème initiale ----
1 . .   . . 8   2 . 9   
. 5 .   . 9 .   7 1 .   
. . 9   . . 4   8 . .   

. . 2   1 4 .   6 . 3   
. . 6   . . .   9 . .   
4 . .   . 6 7   1 . 2   

. . 5   9 . .   3 . .   
. . .   . 3 .   . 7 .   
8 . .   4 . .   . . .   

----- Apres une seule propagation (first propagation with alldiffs) ----
1 . 4   . 5 8   2 . 9   
. 5 8   6 9 .   7 1 4   
. . 9   . 1 4   8 . 5   

7 8 2   1 4 9   6 5 3   
5 1 6   . 8 .   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   

---- Solution 1 ---
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   

---- Solution 2 ---
1 6 4   7 5 8   2 3 9   
3 5 8   6 9 2   7 1 4   
2 7 9   3 1 4   8 6 5   

7 8 2   1 4 9   6 5 3   
5 1 6   2 8 3   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   

---- Solution 3 ---
1 7 4   3 5 8   2 6 9   
3 5 8   6 9 2   7 1 4   
2 6 9   7 1 4   8 3 5   

7 8 2   1 4 9   6 5 3   
5 1 6   2 8 3   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   

3 solutions trouvées en 5 noeuds, 40 ms.


-- Maurice

> 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