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

[Martin]

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.

Martin Chlond

---------------------------------------------------------------------------------

# File name    : sudoku.mod
# Written by   : Martin J Chlond
# Date written : 20-February-2005
# Source       : www.sudoku.com

param d, integer > 0;
param s, integer > 0;

set I := 1..d;
set J := 1..d;
set K := 1..s;
set M := 1..d;
set N := 1..d;

param P{k in K,l in K};
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;

var x{i in I,j in J,k in K,m in M, n in N} binary;

subject to

# force known cells
kc{i in I,j in J,k in K,m in M,n in N}: x[i,j,k,m,n] >= y[i,j,k,m,n];

# each cell contains a single integer
si{i in I,j in J,m in M,n in N}: sum{k in K} x[i,j,k,m,n] = 1;

# each integer appears once only in each grid
gs{k in K,m in M,n in N}: sum{i in I,j in J} x[i,j,k,m,n] = 1;

# each integer appears once only in each row
rs{i in I,k in K,m in M}: sum{j in J,n in N} x[i,j,k,m,n] = 1;

# each integer appears once only in each column
cs{j in J,k in K,n in N}: sum{i in I,m in M} x[i,j,k,m,n] = 1;

solve;

# display results
for {m in M} {
 for {i in I} {
   for {n in N} {
     for{j in J} {
       printf sum{k in K} k*x[i,j,k,m,n];
       printf " ";
     }
     printf " ";
   }
   printf "\n";
 }
 printf "\n";
}

data;

param d := 3;
param s := 9;

# input known cells (Times 14/1/2005)
#param P : 1 2 3 4 5 6 7 8 9 :=
#      1   9 0 0 8 0 0 4 0 0
#      2   0 0 8 0 0 4 0 1 5
#      3   0 0 0 0 7 0 0 0 3
#      4   0 0 6 0 0 7 0 0 0
#      5   0 7 1 0 0 0 8 6 0
#      6   0 0 0 3 0 0 5 0 0
#      7   6 0 0 0 5 0 0 0 0
#      8   7 4 0 2 0 0 3 0 0
#      9   0 0 5 0 0 3 0 0 7;

# found on rec.puzzles
param P : 1 2 3 4 5 6 7 8 9 :=
     1   0 0 0 5 0 1 0 0 0
     2   0 9 0 0 0 0 8 0 0
     3   0 6 0 0 0 0 0 0 0
     4   4 0 1 0 0 0 0 0 0
     5   0 0 0 0 7 0 0 9 0
     6   0 0 0 0 0 0 0 3 0
     7   8 0 0 0 0 0 1 0 5
     8   0 0 0 2 0 0 4 0 0
     9   0 0 0 3 6 0 0 0 0;

end;


---------------------------------------------------------------------------------

# File name    : sd5x5.dat
# Written by   : Martin J Chlond
# Date written : 11-March-2006
# Source       : 
http://www.news.cornell.edu/stories/Feb06/Elser.sudoku.lg.html

param d := 5;
param s := 25;

# input known cells
param P :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 :=
1 0 0 0 0 0 0 0 0 0 13 23 2 16 5 21 11 25 1 24 6 20 4 18 9 22
2 9 0 23 15 21 12 4 0 0 0 8 13 22 6 14 17 20 10 2 5 1 3 19 7 25
3 0 0 4 5 19 9 7 14 0 0 0 0 0 0 0 0 16 12 13 21 24 6 11 2 23
4 0 0 0 0 0 0 0 0 1 0 7 18 9 4 0 0 0 0 0 0 12 17 5 13 14
5 0 0 0 0 0 0 0 0 0 0 0 12 1 3 11 9 14 7 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 21 16 12 9 3 1 20 5 19
7 0 0 9 14 0 5 1 3 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 19 0 0 0 0 0 18 15 23 0 0 0 0 0 5 1 8 3 17 22 14 7 2 4 24
9 8 16 1 4 0 0 0 0 2 12 15 3 11 0 0 5 7 6 25 14 13 21 10 23 9
10 5 17 3 24 2 7 0 0 0 0 1 14 4 0 0 0 0 0 0 0 6 12 25 8 15
11 22 23 10 7 20 19 2 6 0 0 0 0 3 15 12 21 13 14 0 0 9 5 17 11 8
12 18 24 2 19 6 4 16 11 14 10 0 0 0 0 0 0 0 0 0 0 15 13 23 1 3
13 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
14 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
15 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
16 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
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
18 16 4 0 0 24 23 5 20 6 0 0 0 0 12 3 7 9 0 0 0 0 14 0 0 0
19 21 0 0 0 0 0 0 0 0 0 0 17 0 23 0 20 0 0 0 0 18 0 0 0 0
20 15 22 0 0 0 2 0 0 0 0 9 0 0 0 0 0 0 0 0 0 8 0 21 0 0
21 7 12 22 0 16 6 20 0 21 0 18 8 0 24 23 25 17 0 0 0 0 0 0 0 0
22 0 13 0 17 0 0 0 12 11 7 10 21 0 0 15 0 18 22 0 0 0 0 0 0 0
23 0 21 0 0 18 17 9 0 0 19 0 0 14 0 0 0 0 0 0 0 0 0 0 0 0
24 24 0 5 25 0 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;

end;