Calcular bases de Gröbner para Sudoku

Question

Estoy tratando de escribir un programa que resuelve sudokus el uso de una base de Gröbner. Me introdujo 81 variables $x_1$$x_{81}$, esta es una linealización de la sudoku de la junta.

El espacio de validez sudokus se define por:

para $i=1,\ldots,81$ : $F_i = (x_i - 1)(x_i - 2)\cdots(x_i - 9)$ Esto representa el hecho de que todos los cuadrados tienen valores enteros entre 1 y 9.

para todos los $x_i$ $x_j$ que no son iguales, pero en la misma fila, columna o bloque: $G_{ij} = (F_i - F_j)/(x_i - x_j)$ Esto representa que las variables $x_i$ $x_j$ no puede ser igual.

Todos estos $F_i$ $G_{ij}$ juntos definen el espacio de validez sudokus. Este consta de 891 polinomios.

Ahora para resolver un sudoku, podemos añadir las pistas para el espacio, así por ejemplo si la idea de un sudoku es el primer cuadrado es 5, luego añadimos $(x_1 - 5)$ a el espacio. Si aprovechamos la base de Gröbner de este espacio podemos ver directamente la solución para ello.

Entiendo lo que estoy haciendo en este momento. Pero tengo problemas para encontrar una computable forma para encontrar las bases de Gröbner. Me ha hecho todo por $4\times4$ sudokus (o los llamados shidokus). Pero Arce ni Singular me están dando un resultado de la base de Gröbner de la $9\times9$ sudoku espacio. Usted puede ver los comandos que me dio a Arce aquí (Primero debo definir los 891 polinomios, entonces pido una base de esto) He leído los papeles diciendo que es factible aunque ineficaz para hacer lo que me esfuerzo, pero no veo la manera de encontrar la solución, ya que no incluyen muchos de los detalles de implementación. Puede alguien me apunte a una dirección, haciendo de este problema más fácil de Arce o de otro software?

Answer 1

Trato con bases de groebner regularmente en Mathematica, y 81 variables, y que muchos polinomios es más probablemente demasiado, incluso para el software que es mejor tratar con bases de groebner. Es muy difícil estimar el consumo de tiempo y memoria para estos cálculos (orden monomio también desempeña un papel enorme), pero mi reacción inicial es que su problema es demasiado difícil de resolver en una computadora de escritorio regular.

Answer 2

Como Greg Martin señaló, hubo un error en mi respuesta anterior. Consideramos, sin embargo, esta pequeña modificación, que resuelve el problema, de nuevo, con 108 polinomios:

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

las 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)

en la plaza de restricciones:
x11+x12+x13+x21+x22+x23+x31+x32+x33+s
. . .
(9 polinomios)

las restricciones sobre las variables de sí mismos:
x11^p-1, x12^p-1 . . .
(81 polinomios)

Answer 3

Yo estaba casi olvidado, sobre esta cuestión, pero para mayor referencia: Yo estaba un poco equivocado en el hecho de que la base de groebner de Sudoku en general debe ser computable. Pero la solución de un hormigón de Sudoku a través de una base de Groebner es factible (dado el tiempo suficiente).

La teoría detrás de esto puede ser encontrado en este trabajo: http://www.risc.jku.at/Groebner-Bases-Bibliography/gbbib_files/publication_1180.pdf

Aquí está mi Singular código para la resolución de un hormigón de 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

Answer 4

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

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

Por igualando los coeficientes de $T$, se obtiene 9 ecuaciones que asegurarse de que los conjuntos de $\{ 1, 2, \cdots, 9\}$ $\{x_1, x_2, \cdots, x_9\}$ son los mismos.

Así que el Sudoku condición es de 27 conjuntos de 9 ecuaciones en todos.

Usted probablemente podría obtener algún beneficio por tener el Sudoku entradas de ser 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, de modo que usted está en el carácter 2. O tal vez el trabajo en el campo finito de 19 elementos, de forma que puede utilizar el 9 ° raíces de la unidad, como los otros de la comunidad sugiere. (o el campo finito de 64 elementos si desea utilizar 9-th raíces de la unidad en la característica 2)