[Help-glpk] Re: Sudoku - can anyone make this work?

[Andrew Makhorin]

> The following is a mathprog model to solve Sudoku puzzles. It works
> OK on 3x3 and 4x4 but I found a 5x5 at
> http://www.news.cornell.edu/stories/Feb06/Elser.sudoku.lg.html that
> it can't solve - I get the error message PROBLEM HAS NO PRIMAL
> FEASIBLE SOLUTION. I've obtained a solution quite quickly using OPL
> so there must be such a solution. I've included the mathprog model
> withe two 3x3 puzzles so you can see the thing works and also the
> 5x5 data as a separate mathprog data file..

> Any help will be truly appreciated.

> param y{i in I,j in J,k in K,m in M,n in N} binary :=
>    if P[3*(m-1)+i,3*(n-1)+j] = k then 1 else 0;

I think for the second puzzle here must be 5, not 3.

INTEGER OPTIMAL SOLUTION FOUND
Time used:   45.0 secs
Memory used: 23.5M
10 14 8 12 7  3 15 19 17 13  23 2 16 5 21  11 25 1 24 6  20 4 18 9 22  
9 18 23 15 21  12 4 24 16 11  8 13 22 6 14  17 20 10 2 5  1 3 19 7 25  
1 3 4 5 19  9 7 14 22 8  25 15 20 17 10  18 16 12 13 21  24 6 11 2 23  
20 25 24 16 11  21 6 10 1 2  7 18 9 4 19  3 22 8 23 15  12 17 5 13 14  
13 2 6 22 17  18 25 23 5 20  24 12 1 3 11  9 14 7 19 4  16 15 8 10 21  

6 10 18 23 15  25 11 13 24 14  2 22 17 7 8  4 21 16 12 9  3 1 20 5 19  
12 7 9 14 25  5 1 3 8 4  19 6 23 21 20  15 24 2 10 13  17 11 22 18 16  
19 11 20 21 13  16 18 15 23 6  12 10 25 9 5  1 8 3 17 22  14 7 2 4 24  
8 16 1 4 22  20 19 17 2 12  15 3 11 18 24  5 7 6 25 14  13 21 10 23 9  
5 17 3 24 2  7 21 22 10 9  1 14 4 16 13  19 23 20 18 11  6 12 25 8 15  

22 23 10 7 20  19 2 6 18 24  16 4 3 15 12  21 13 14 1 25  9 5 17 11 8  
18 24 2 19 6  4 16 11 14 10  21 9 5 8 25  22 12 17 20 7  15 13 23 1 3  
25 1 21 11 4  15 17 9 12 3  13 23 18 14 2  6 10 5 8 19  22 16 7 24 20  
17 15 16 3 12  8 13 5 7 25  20 11 6 1 22  23 2 9 4 24  21 10 14 19 18  
14 8 13 9 5  22 23 1 20 21  17 24 10 19 7  16 15 11 3 18  25 2 6 12 4  

3 19 12 13 8  10 14 4 9 16  11 7 21 20 18  24 6 15 22 2  5 23 1 25 17  
23 20 7 18 14  24 22 21 13 15  5 16 2 10 4  8 1 25 11 17  19 9 3 6 12  
16 4 17 1 24  23 5 20 6 18  22 25 8 12 3  7 9 19 21 10  2 14 13 15 11  
21 5 25 2 9  11 8 7 19 1  14 17 15 23 6  20 3 13 16 12  18 24 4 22 10  
15 22 11 6 10  2 12 25 3 17  9 19 24 13 1  14 4 18 5 23  8 20 21 16 7  

7 12 22 10 16  6 20 2 21 5  18 8 13 24 23  25 17 4 9 3  11 19 15 14 1  
4 13 14 17 3  1 24 12 11 7  10 21 19 25 15  2 18 22 6 16  23 8 9 20 5  
2 21 15 20 18  17 9 8 4 19  6 5 14 22 16  12 11 23 7 1  10 25 24 3 13  
24 6 5 25 1  13 3 18 15 23  4 20 12 11 9  10 19 21 14 8  7 22 16 17 2  
11 9 19 8 23  14 10 16 25 22  3 1 7 2 17  13 5 24 15 20  4 18 12 21 6  


Andrew Makhorin