# 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) –  Mariano Suárez-Alvarez Mar 17 '12 at 16:56
maple just gives up after an hour or so with an error message about the size of the computation –  Ingdas Mar 17 '12 at 17:00
Well, that's the memory part :) You should try Macaulay2, too. –  Mariano Suárez-Alvarez Mar 17 '12 at 17:05
You might want to CC Maple primes –  user2468 Mar 17 '12 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 Apr 25 '12 at 14:31

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 –  Ingdas Mar 18 '12 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. –  Paxinum Mar 18 '12 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 –  Ingdas Mar 18 '12 at 11:07

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? –  Greg Martin Jun 4 '12 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. –  anomalocaris Jun 5 '12 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$. –  Greg Martin Jun 5 '12 at 19:02

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

-
$$(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.