Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm trying to write a program that solves sudoku's using a Groebner basis. I introduced 81 variables $x_1$ to $x_{81}$, this is a linearisation of the sudoku board.

The space of valid sudokus is defined by:

for $i=1,\ldots,81$ : $F_i = (x_i - 1)(x_i - 2)\cdots(x_i - 9)$ This represents the fact that all squares have integer values between 1 and 9.

for all $x_i$ and $x_j$ which are not equal but in the same row, column or block: $G_{ij} = (F_i - F_j)/(x_i - x_j)$ This represents that the variables $x_i$ and $x_j$ can not be equal.

All these $F_i$ and $G_{ij}$ together define the space of valid sudokus. This conists of 891 polynomials.

Now to solve a sudoku we can add the clues to the space, so by example if the clue of a sudoku is the first square is a 5, then we add $(x_1 - 5)$ to the space. If we now take the groebner basis of this space we can directly see the solution for it.

I understand what I am doing this far. But I have trouble finding a computable manner for finding the groebner bases. I have succesfully done everything for 4*4 sudokus (or so-called shidokus). But Maple nor Singular are giving me a result for the groebner basis of the 9*9 sudoku space. You can see the commands I gave to Maple here: http://dl.dropbox.com/u/16797591/mapleSudoku.txt. (First I define the 891 polynomials, then I ask for a basis of it) I read papers saying it's feasible although imperformant to do what I strive for but I don't see how to find the solution, as they don't include many implementation details. Can anyone point me to a direction, making this problem easier for Maple or other software?

share|improve this question
    
Are you just looking for something like Buchberger's algorithm? en.wikipedia.org/wiki/Buchberger%27s_algorithm –  Sean Eberhard Mar 19 '12 at 20:58
15  
Just a thought - maybe you should try doing the calculations over a finite field with 9 elements? That would probably make the coefficients occurring in your polynomials much easier to store. (For instance, the polynomial F_i simply becomes x_i^9-x_i.) –  zeb Mar 19 '12 at 21:10
1  
You might try using Magma, which has a really great implementation of the Faugère F4 algorithm in its Gröbner basis routines (much better than any other system I've used, although I can't claim to be an expert). Zeb's comment about finite fields is also important: Gröbner bases over the rationals can have extremely complicated coefficients, which should be avoided when possible. –  Henry Cohn Mar 19 '12 at 21:16
1  
also posted math.stackexchange.com/questions/121387/… –  Will Jagy Mar 19 '12 at 21:27
1  
@Henry: Maple uses F4 as implemented by Faugère himself, so assuming the GB problem is posed properly, it should make not difference if Maple or Magma is used. The proposal to use a finite field is probably a much better idea. –  Jacques Carette Mar 19 '12 at 23:27

1 Answer 1

Here is a Singular Code that works quite well:

ring A = 0,(t,x(1..9)),lp;
/* Characteristic 0 works suprisingly well for this problem. */
/* We choose a lexicographic ordering since we will compute an
   elimination ideal. */

poly p = (t-x(1))*(t-x(2))*(t-x(3))*(t-x(4))*(t-x(5))*(t-x(6))*(t-x(7))*(t-x(8))*(t-x(9))-(t-1)*(t-2)*(t-3)*(t-4)*(t-5)*(t-6)*(t-7)*(t-8)*(t-9);
/* p(x)=0 in Q[t] implies that x is a permutation of the numbers 1 to 9. */

matrix c = coeffs(p,t);
ideal J = (c[1..9,1]);
/* J expresses that x is a permutation of the numbers 1 to 9. However,
   surprisingly, it is better to use only constraints saying that x(8)
   and x(9) are distinct integers between 1 and 9. This is done by
   computing an elimination ideal. */
ideal JG = groebner(J);
ideal J2 = (JG[1],JG[2]);
/* J2 is the ideal expressing that x(1) and x(2) are distinct integers
   between 1 and 9. */

ring R=0,(x(1..81)),dp;
ideal I;
map psi;
proc f(k,l,m,n,o,p,q,r,s)
{intvec v = k,l,m,n,o,p,q,r,s;
 int i,j;
 for (i=1; i<=8; i++) {for (j=i+1; j<=9; j++)
 {psi = A,0,1,2,3,4,5,6,7,x(v[i]),x(v[j]); I = I + psi(J2);}}}

/* Code the rules into the ideal. */
f(1,2,3,4,5,6,7,8,9);
f(10,11,12,13,14,15,16,17,18);
f(19,20,21,22,23,24,25,26,27);
f(28,29,30,31,32,33,34,35,36);
f(37,38,39,40,41,42,43,44,45);
f(46,47,48,49,50,51,52,53,54);
f(55,56,57,58,59,60,61,62,63);
f(64,65,66,67,68,69,70,71,72);
f(73,74,75,76,77,78,79,80,81);
f(1,10,19,28,37,46,55,64,73);
f(2,11,20,29,38,47,56,65,74);
f(3,12,21,30,39,48,57,66,75);
f(4,13,22,31,40,49,58,67,76);
f(5,14,23,32,41,50,59,68,77);
f(6,15,24,33,42,51,60,69,78);
f(7,16,25,34,43,52,61,70,79);
f(8,17,26,35,44,53,62,71,80);
f(9,18,27,36,45,54,63,72,81);
f(1,2,3,10,11,12,19,20,21);
f(4,5,6,13,14,15,22,23,24);
f(7,8,9,16,17,18,25,26,27);
f(28,29,30,37,38,39,46,47,48);
f(31,32,33,40,41,42,49,50,51);
f(34,35,36,43,44,45,52,53,54);
f(55,56,57,64,65,66,73,74,75);
f(58,59,60,67,68,69,76,77,78);
f(61,62,63,70,71,72,79,80,81);

/* Code a uniquely solvable Sudoku problem into the ideal.  */
I=I+(x(3)-4);
I=I+(x(6)-3);
I=I+(x(7)-6);
I=I+(x(9)-9);
I=I+(x(12)-8);
I=I+(x(13)-9);
I=I+(x(16)-2);
I=I+(x(18)-1);
I=I+(x(22)-8);
I=I+(x(23)-1);
I=I+(x(27)-7);
I=I+(x(28)-6);
I=I+(x(33)-7);
I=I+(x(37)-8);
I=I+(x(40)-3);
I=I+(x(42)-9);
I=I+(x(45)-5);
I=I+(x(49)-6);
I=I+(x(54)-3);
I=I+(x(55)-4);
I=I+(x(59)-7);
I=I+(x(60)-6);
I=I+(x(64)-2);
I=I+(x(66)-7);
I=I+(x(69)-5);
I=I+(x(70)-1);
I=I+(x(73)-9);
I=I+(x(75)-1);
I=I+(x(76)-2);
I=I+(x(79)-4);

option(redSB);
groebner(I,30);
/* You get the solution quickly. */
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.