Cálculo de la base de Gröbner para Sudoku

Trato con bases de Groebner regularmente en Mathematica, y 81 variables, y que muchos polinomios probablemente sean demasiado, incluso para un software que es mejor para tratar con bases de Groebner. Es bastante difícil estimar el tiempo y el consumo de memoria para tales cálculos (el orden de los monomios también juega un papel muy importante), pero mi reacción inicial es que su problema es demasiado difícil de resolver en una computadora de escritorio normal.

Casi me olvidé de esta pregunta, pero para mayor referencia: estaba algo equivocado en el hecho de que la base groebner de Sudoku en general debería ser computable. Pero resolver un Sudoku concreto a través de una base de Groebner es factible (con el tiempo suficiente).

La teoría detrás de esto se puede encontrar en este artículo: http://www.risc.jku.at/Groebner-Bases-Bibliography/gbbib_files/publication_1180.pdf

Aquí está mi código Singular para resolver un sudoku concreto:

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

Como señaló Greg Martin, había una falla en mi respuesta anterior. Considere, sin embargo, esta pequeña modificación, que resuelve el problema, nuevamente con 108 polinomios:

Tome un primo p>9 y r=1^(1/p), una raíz p-ésima primitiva de la unidad. Ahora define s la suma de p-9 diferentes potencias de r. El siguiente sistema de variables codifica su problema:

restricciones de fila:
x11 + x12 + ... + x19 + s
x21 + x22 + ... + x29 + s
. . .
(9 polinomios)

restricciones de columna:
x11 + x21 + ... + x91 + s
x12 + x22 + ... + x92 + s
. . .
(9 polinomios)

Restricciones en cuadrado:
x11+x12+x13+x21+x22+x23+x31+x32+x33+s
. . .
(9 polinomios)

las restricciones sobre las propias variables:
x11^p-1, x12^p-1, . . .
(81 polinomios)

Mi primer pensamiento sería codificar las condiciones de que 9 variables tienen que ser los números del 1 al 9 por la ecuación

Igualando los coeficientes de$T$, obtienes 9 ecuaciones que aseguran que los conjuntos$\{ 1, 2, \cdots, 9\}$y$\{x_1, x_2, \cdots, x_9\}$son lo mismo.

Entonces, la condición de Sudoku es 27 conjuntos de 9 ecuaciones en total.

Probablemente podría obtener algún beneficio al hacer que las entradas de Sudoku sean elementos del campo finito con 9 elementos en lugar de números enteros. O tal vez como 9 de los elementos en el campo finito con 16 elementos, para que esté en la característica 2. O tal vez trabaje en el campo finito de 19 elementos para que pueda usar las raíces 9-th de la unidad como el otro respondedor sugiere. (o el campo finito de 64 elementos si desea usar raíces 9-ésimas de la unidad en la característica 2)