Calculating Gröbner basis for Sudoku

I'm trying to write a program that solves sudokus using a Gröbner 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 consists 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 Gröbner 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 Gröbner bases. I have successfully done everything for $4\times4$ sudokus (or so-called shidokus). But Maple nor Singular are giving me a result for the Gröbner basis of the $9\times9$ sudoku space. You can see the commands I gave to Maple here (First I define the 891 polynomials, then I ask for a basis of it) I read papers saying it's feasible although inefficient 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?

• What do you mean by "maple nor singular give me results?" It is just a matter of time... (and memory) Commented Mar 17, 2012 at 16:56
• maple just gives up after an hour or so with an error message about the size of the computation Commented Mar 17, 2012 at 17:00
• Well, that's the memory part :) You should try Macaulay2, too. Commented Mar 17, 2012 at 17:05
• You might want to CC Maple primes
– user2468
Commented Mar 17, 2012 at 17:06
• @Ingdas Is it still of interest? Or did you solve it? If yes, I'd be interested in the solution. In any case I'm interested in the proof about how the inequality can be represented by the set of all $G_{ij}$. Moreover why $G_{ij}$ will always be a polynomial. And if $G_{ij}$ covers all possibilities of $a_i$ ≠ $a_j$.
– Kai
Commented Apr 25, 2012 at 14:31

4 Answers

I deal with groebner bases on regular basis in Mathematica, and 81 variables, and that many polynomials is most probably way too much, even for software that is better with dealing with groebner bases. It is quite hard to estimate the time and memory consumption for such calculations (monomial order also plays a huge role), but my initial reaction is that your problem is way too hard to solve on a regular desktop computer.

• I found this pdf: math.ipm.ac.ir/conferences/2011/cca2011/Exercises-Steenpass.pdf pages 3 and 4 suggest it's really possible Commented Mar 18, 2012 at 10:04
• Ah, I guess Singular is probably much more efficient than Mathmatica then, or there is something more to the problem I am not aware of. Commented Mar 18, 2012 at 10:33
• But if I naively implement it in Singular it doesn't work either so I was hoping someone here could point me to a working Singular (or other language) program Commented Mar 18, 2012 at 11:07

I was almost forgotten about this question, but for further reference: I was somewhat mistaken in the fact that the groebner basis of Sudoku in general should be computable. But solving a concrete Sudoku through a Groebner basis is doable (given enough time).

The theory behind this can be found in this paper: http://www.risc.jku.at/Groebner-Bases-Bibliography/gbbib_files/publication_1180.pdf

Here is my Singular code for solving a concrete sudoku:

ring r0=0,x(1..81),dp;  //defines the ring we're working on
option(redSB); //sets groebner as the standard representation of an ideal
option(intStrategy); //constrains our values to integers (speedup)

proc F (int i) { //generates the F-polynomials, restricting the domain of a single variable
return((x(i)-1)*(x(i)-2)*(x(i)-3)*(x(i)-4)*(x(i)-5)*(x(i)-6)*(x(i)-7)*(x(i)-8)*(x(i)-9));
};

proc G (int i, int j){ //generates the G-polynomials asserting two variables to be different
return ((F(i)-F(j))/(x(i)-x(j)));
};

int i = 1;
int b;
ideal I;

for (int a = 0 ; a < 81 ; a++ ){
for (b = a+1 ; b < 81 ; b++){ //if
if(a mod 9 == b mod 9 ||  //two variables are in the same column
a div 9 == b div 9 ||  //or same row
(a div 27 == b div 27 && ((a mod 9) div 3) == ((b mod 9) div 3))) { //or same block
I[i] = G(a+1,b+1);  //they must be different
i++;
}
}
}

int c;
for (c = 1; c<=81; c++) {I[i]=F(c);i++;}; //restricting the domain of all variables

intmat A[9][9] =  //the input sudoku
1,0,0, 0,0,0, 0,0,0,
0,0,2, 7,4,0, 0,0,0,
0,0,0, 5,0,0, 0,0,4,

0,3,0, 0,0,0, 0,0,0,
7,5,0, 0,0,0, 0,0,0,
0,0,0, 0,0,9, 6,0,0,

0,4,0, 0,0,6, 0,0,0,
0,0,0, 0,0,0, 0,7,1,
0,0,0, 0,0,1, 0,3,0

;

int x;
int y;
for (x = 1 ; x <= 9 ; x++ ){
for (y = 1 ; y <= 9 ; y++){
if(A[y,x] >0) {
I = I,(x(x+9*(y-1)) - A[y,x]); //adding the known values to the system of equations
}
}
};

groebner(I); //computes the groebner basis of our system


As Greg Martin pointed out, there was a flaw in my previous answer. Consider, however, this small modification, which solves the problem, again with 108 polynomials:

Take a prime p>9 and r=1^(1/p), a primitive p-th root of unity. Now define s the sum of p-9 different powers of r. The following system of variables encodes your problem:

row restrictions:
x11 + x12 + ... + x19 + s
x21 + x22 + ... + x29 + s
. . .
(9 polynomials)

column restrictions:
x11 + x21 + ... + x91 + s
x12 + x22 + ... + x92 + s
. . .
(9 polynomials)

in-square restrictions:
x11+x12+x13+x21+x22+x23+x31+x32+x33+s
. . .
(9 polynomials)

the restrictions on the variables themselves:
x11^p-1, x12^p-1, . . .
(81 polynomials)

• Won't your restriction equations admit spurious solutions such as x11=x12=x13=3, x14=x15=x16=6, x17=x18=x19=9? Commented Jun 4, 2012 at 18:03
• The variables are restricted to be ninth roots of 1. There is only one way, up to permutation, to add n n-th roots of 1 and obtain 0, that is by adding n different roots. Commented Jun 5, 2012 at 14:37
• That statement is incorrect if $n$ is composite. Let $\zeta$ be a cube root of unity (which is also a ninth root of unity), and set $x_{1j} = \zeta^j$ for $1\le j\le 9$. In other words, add three copies of $\zeta$, three copies of $\zeta^2$, and three copies of $1$: the answer is $0$. Commented Jun 5, 2012 at 19:02

My first thought would be to encode the conditions that 9 variables have to be the numbers 1 through 9 by the equation

$$(T-1)(T-2)\cdots(T-9) = (T-x_1)(T-x_2)\cdots(T-x_9)$$

By equating the coefficients of $T$, you get 9 equations that ensure that the sets $\{ 1, 2, \cdots, 9\}$ and $\{x_1, x_2, \cdots, x_9\}$ are the same.

So the Sudoku condition is 27 sets of 9 equations in all.

You could probably get some benefit by having the Sudoku entries be elements of the finite field with 9 elements rather than integers. Or maybe as 9 of the elements in the finite field with 16 elements, so that you're in characteristic 2. Or maybe work in the finite field of 19 elements so that you can use the 9-th roots of unity as the other answerer suggests. (or the finite field of 64 elements if you want to use 9-th roots of unity in characteristic 2)