Resuelve Sudoku con Algoritmo X

En este artículo, consideramos el "Algoritmo X" de Knuth y su aplicación para resolver sudoku. La belleza del algoritmo es que Sudoku se resuelve rápidamente sin programar ninguna técnica de solución avanzada.

Todo comenzó, de hecho, con los rompecabezas del Proyecto Euler , donde para obtener la respuesta, debes resolver 50 sudoku. Y parece que recibió una respuesta al escribir un programa para resolver una búsqueda bastante estúpida, pero de alguna manera quedó insatisfecho con la velocidad de la solución. Después de ver cómo las personas normales resuelven el sudoku, descubrí que el Algoritmo X, inventado por Donald Knut, se está utilizando para esto.

Algoritmo X

Este algoritmo resuelve el problema de cubrir con precisión el conjunto. O, si lo desea, recopila un "rompecabezas discreto", que tiene información sobre la forma de las piezas disponibles disponibles. Más formalmente:

• Hay muchos s
• Hay un conjunto de subconjuntos Y de este conjunto
• La tarea es elegir entre Y tales elementos Y * que cada elemento de S esté contenido en solo uno de los conjuntos incluidos en Y *
• Es decir, la unión de todos los conjuntos en Y * constituye (cubre) el conjunto S , y al mismo tiempo en Y * no hay conjuntos que se crucen en pares

Por ejemplo, considere los conjuntos
S = {1, 2, 3, 4, 5} y
Y = { A = {1, 2},
B = {2, 3},
C = {1, 5},
D = {1, 4},
E = {5}}
Los conjuntos B , D y E forman una cobertura exacta del conjunto S.

Para el algoritmo X Knuth, el conjunto Y se representa como una matriz binaria, donde las filas corresponden a los elementos Y , y A _{i, j} = 1, si S _j está en Y _i . Es decir para el ejemplo anterior:

El algoritmo exacto de búsqueda de cobertura es el siguiente:

• Datos de entrada: establece S e Y ; Stack conjuntos potencialmente incluidos en la cobertura (inicialmente puede estar vacía o ya tener algunos elementos)
  
  1. Si el conjunto S está vacío, la cubierta deseada está en la pila.
  2. Si el conjunto Y está vacío, no se encontró la cubierta.
  3. Estamos buscando el elemento s en el conjunto S que está incluido en el número mínimo de conjuntos en Y.
  4. Elija de Y todas las líneas X que contengan s .
  5. Para cada conjunto X, repita 6-9.
  6. Agregue X a la pila como un elemento de cobertura potencial.
  7. Formamos los conjuntos S ' e Y' : S ' es S , del cual se eliminan todos los elementos contenidos en X , Y' son los conjuntos de Y que no se cruzan con X.
  8. Llamamos al algoritmo X para S ' , Y' y Stack .
  9. Si se encontró en el paso 7 que la cobertura es imposible, retire el elemento de la parte superior de la Stack y continúe con la siguiente X. Si se encuentra una solución, la devolvemos.
  10. Si no hay solución para ninguna X , la tarea no se resuelve para esta entrada.

En general, nada particularmente complicado. Esencialmente, la búsqueda habitual en profundidad. Por cierto, notamos que si inicialmente configura la pila para que no esté vacía, entonces el problema puede formularse como "encontrar la cobertura exacta que incluye elementos que ya se encuentran en la pila".

La sutileza es que en la práctica este algoritmo se usa para problemas donde los conjuntos en Y son "pequeños", es decir la matriz es muy escasa, por lo que, por ejemplo, la búsqueda de intersecciones entre columnas durante el almacenamiento estándar en forma de matriz lleva un tiempo inaceptablemente largo.
Por lo tanto, Knut complementa este algoritmo con un mecanismo de "enlace de baile" . La matriz se representa en forma de una lista bidimensional de doble enlace: para cada fila de la lista solo se almacenan los números de columna, donde esta fila contiene unidades. La lista también contiene enlaces al elemento siguiente y anterior en una fila y columna. Dicha organización le permite eliminar columnas y filas de una matriz dispersa durante el tiempo O (1) en comparación con O ( m * n ) cuando se almacena en una matriz bidimensional.

Es interesante que Ali Assaf ofrezca una alternativa al mecanismo de enlaces de baile utilizando listas asociativas, que le permite implementar el algoritmo X en literalmente varias docenas de líneas en lenguajes de alto nivel.

La idea es almacenar columnas y filas de matriz en listas asociativas. En las columnas almacenamos índices de fila, en la intersección con la que hay elementos distintos de cero, en filas, respectivamente, índices de columna. Además, almacenaremos índices en filas de manera ordenada, en una matriz, notamos que en el algoritmo de Knuth, esencialmente no es necesario modificar filas, por lo tanto, no es necesaria la optimización para eliminar rápidamente un elemento de una fila. Pero las columnas se establecerán en forma de conjuntos, porque al eliminar una fila de una matriz, es necesario eliminar su identificador de todas las columnas (y al eliminarlo de todas las columnas, la fila desaparece "por sí misma").

Considere la implementación del algoritmo en Julia.
La matriz del ejemplo ahora se verá así:

 Y = Dict( 'A' => [1, 2], 'B' => [2, 3], 'C' => [1, 5], 'D' => [1, 4], 'E' => [5] ) S = Dict( 1 => Set(['A', 'C', 'D']), 2 => Set(['A', 'B']), 3 => Set(['B']), 4 => Set(['D']), 5 => Set(['C', 'E']) ) 

Para que el algoritmo funcione, necesita una función que extraiga líneas de la matriz que se cruzan con la dada, y una función que devuelva estas líneas a su lugar.

 function extract_intersects!(rows, columns, base_row) buf = [] for elt in rows[base_row] #        push!(buf, pop!(columns, elt)) #         for intersecting_row in buf[end] for other_elt in rows[intersecting_row] if other_elt != elt delete!(columns[other_elt], intersecting_row) end end end end return buf end function restore_intersects!(rows, columns, base_row, buf) #       base_row  ,      for elt in Iterators.reverse(rows[base_row]) columns[elt] = pop!(buf) for added_row in columns[elt] for col in rows[added_row] push!(columns[col], added_row) end end end end 

Para que estas dos funciones funcionen como deberían, solo se requiere el almacenamiento ordenado de los elementos en las filas de la matriz. En la función extract_intersects!() , En cada iteración del bucle externo, las filas que se cruzan con base_row pero que no contienen elementos vistos en iteraciones anteriores se eliminan de la matriz. ¡Esto asegura que cuando insertemos las columnas en restore_intersects!() En el orden inverso, en el bucle más interno en el momento del push!(columns[col], added_row) llamada push!(columns[col], added_row) la columns[col] ya se devolverá a la matriz, y todo se eliminará en extract_intersects!() elementos de las columnas serán devueltos a su lugar original.

Ahora algoritmo X en sí mismo:

 function algorithm_x(rows, columns, cover = []) if isempty(columns) return cover else #       m, c = findmin(Dict(k => length(v) for (k, v) in columns)) for subset in collect(columns[c]) push!(cover, subset) #     #   subset  buf_cols = extract_intersects!(rows, columns, subset) s = algorithm_x(rows, columns, cover) #     - ,  s == nothing || return s restore_intersects!(rows, columns, subset, buf_cols) pop!(cover) end #      columns[c] , #        return nothing end end 

Sudoku

Hay un algoritmo, el asunto es pequeño: presentar el Sudoku como una tarea para encontrar la cobertura exacta.

Formulamos los requisitos que debe cumplir un sudoku resuelto:

1. En cada celda hay un número del 1 al 9 (o hasta n ² si se resuelven cuadrados de diferente tamaño).
2. En cada línea, cada número aparece una vez.
3. En cada columna, cada número aparece una vez.
4. En cada cuadrante, cada número aparece una vez.

Cada uno de estos requisitos debe cumplirse exactamente 1 vez, es decir forman el conjunto que necesita ser cubierto. Tiene exactamente 4 n ² elementos (columnas en la matriz).

Los subconjuntos que consideramos se forman al sustituir un número específico en una celda específica. Por ejemplo, el número 9 en la intersección de 1 fila y 4 columnas "cubre" un subconjunto "en la celda (1,4) es un número, en 1 fila hay un número 9, en 4 columnas hay un número 9, en 2 cuadrantes hay un número 9" (lo que implica lo habitual) Sudoku 9 × 9).

Después de eso, el algoritmo de solución se escribe trivialmente.

 #    9×9,      #   -   (row, col, num) #  : # (0, row, col) -   row  col   # (1, row, num) -   row   num # (2, col, num) -   col   num # (3, q, num) -   q   num function xsudoku(puzzle::AbstractMatrix{Int}) rows = Dict() cols = Dict() #   for row in 1:9, col in 1:9, num in 1:9 r = [] quad = ((row-1)÷3)*3 + (col-1)÷3 + 1 push!(r, (0, row, col), (1, row, num), (2, col, num), (3, quad, num)) rows[(row, col, num)] = r end #   for type in 0:3, n1 in 1:9, n2 in 1:9 cols[(type, n1, n2)] = Set() end for (rk, rv) in rows for v in rv push!(cols[v], rk) end end # s -    #  ,     ,    s = [] for i in 1:9, j in 1:9 if puzzle[i, j] > 0 elt = (i, j, puzzle[i,j]) push!(s, elt) #    ,       extract_intersects!(rows, cols, elt) end end # ,   -   success = algorithm_x(rows, cols, s) success != nothing || return nothing #      ret = similar(puzzle) for (i, j, num) in s ret[i,j] = num end return ret end 

Veamos algún ejemplo:

  julia> @time xsudoku([0 0 0 0 0 0 4 0 0; 3 0 6 0 0 0 0 0 0; 0 0 0 1 9 6 0 3 0; 0 7 0 0 0 0 0 1 0; 8 0 0 2 5 0 0 9 0; 0 4 0 0 0 0 8 0 0; 0 6 0 4 0 9 0 0 8; 0 0 5 0 0 0 0 2 0; 0 0 0 5 0 0 0 0 7]) 0.006326 seconds (54.91 k allocations: 3.321 MiB) 9×9 Array{Int64,2}: 1 5 7 8 3 2 4 6 9 3 9 6 7 4 5 2 8 1 2 8 4 1 9 6 7 3 5 6 7 2 9 8 4 5 1 3 8 3 1 2 5 7 6 9 4 5 4 9 6 1 3 8 7 2 7 6 3 4 2 9 1 5 8 4 1 5 3 7 8 9 2 6 9 2 8 5 6 1 3 4 7 

Parece funcionar, y la velocidad es aceptable.

Cabe señalar que no se establecieron técnicas específicas para el sudoku (como aquí o aquí ) en el algoritmo, excepto una representación específica del conjunto deseado y los elementos de cobertura.