6
$\begingroup$

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?

  • 0
    @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$.2012-04-25

4 Answers 4

0

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)

2

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.

  • 0
    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) program2012-03-18
1

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)

  • 1
    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$.2012-06-05
1

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