El solucionador de sudoku más corto en Python: ¿cómo funciona?

Estaba jugando con mi propio solucionador de Sudoku y estaba buscando algunos consejos para un diseño bueno y rápido cuando me encontré con esto:

def r(a):i=a.find('0');~i or exit(a);[m
in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import*;r(argv[1])

Mi propia implementación resuelve Sudokus de la misma manera que los resuelvo en mi cabeza, pero ¿cómo funciona este algoritmo críptico?

http://scottkirkwood.blogspot.com/2006/07/shortest-sudoku-solver-in-python.html

Bueno, puedes hacer las cosas un poco más fáciles arreglando la sintaxis:

def r(a):
  i = a.find('0')
  ~i or exit(a)
  [m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)] or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import *
r(argv[1])

Limpiar un poco:

from sys import exit, argv
def r(a):
  i = a.find('0')
  if i == -1:
    exit(a)
  for m in '%d' % 5**18:
    m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) or a[j] for j in range(81)] or r(a[:i]+m+a[i+1:])

r(argv[1])

Bien, entonces este script espera un argumento de línea de comando y llama a la función r en él. Si no hay ceros en esa cadena, r sale e imprime su argumento.

(Si se pasa otro tipo de objeto, None equivale a pasar cero, y cualquier otro objeto se imprime en sys.stderr y da como resultado un código de salida de 1. En particular, sys.exit ("algún mensaje de error") es un forma rápida de salir de un programa cuando se produce un error. Consulte http://www.python.org/doc/2.5.2/lib/module-sys.html )

Supongo que esto significa que los ceros corresponden a espacios abiertos, y se resuelve un rompecabezas sin ceros. Luego está esa desagradable expresión recursiva.

El bucle es interesante: for m in'%d'%5**18

¿Por qué 5 ** 18? Resulta que se '%d'%5**18evalúa en '3814697265625'. Esta es una cadena que tiene cada dígito del 1 al 9 al menos una vez, por lo que quizás esté tratando de colocar cada uno de ellos. De hecho, parece que esto es lo que r(a[:i]+m+a[i+1:])está haciendo: llamar de forma recursiva r, con el primer espacio en blanco rellenado con un dígito de esa cadena. Pero esto solo sucede si la expresión anterior es falsa. Veamos eso:

m in [(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) or a[j] for j in range(81)]

Entonces, la ubicación se realiza solo si m no está en esa lista de monstruos. Cada elemento es un número (si la primera expresión es distinta de cero) o un carácter (si la primera expresión es cero). m se descarta como posible sustitución si aparece como carácter, lo que solo puede suceder si la primera expresión es cero. ¿Cuándo es cero la expresión?

Tiene tres partes que se multiplican:

• (i-j)%9 que es cero si i y j son múltiplos de 9, es decir, la misma columna.
• (i/9^j/9) que es cero si i / 9 == j / 9, es decir, la misma fila.
• (i/27^j/27|i%9/3^j%9/3) que es cero si ambos son cero:
• • i/27^j^27 que es cero si i / 27 == j / 27, es decir, el mismo bloque de tres filas
• • i%9/3^j%9/3 que es cero si i% 9/3 == j% 9/3, es decir, el mismo bloque de tres columnas

Si alguna de estas tres partes es cero, la expresión completa es cero. En otras palabras, si i y j comparten una fila, columna o bloque 3x3, entonces el valor de j no se puede usar como candidato para el espacio en blanco en i. ¡Ajá!

from sys import exit, argv
def r(a):
  i = a.find('0')
  if i == -1:
    exit(a)
  for m in '3814697265625':
    okay = True
    for j in range(81):
      if (i-j)%9 == 0 or (i/9 == j/9) or (i/27 == j/27 and i%9/3 == j%9/3):
        if a[j] == m:
          okay = False
          break
    if okay:
      # At this point, m is not excluded by any row, column, or block, so let's place it and recurse
      r(a[:i]+m+a[i+1:])

r(argv[1])

Tenga en cuenta que si ninguna de las ubicaciones funciona, r regresará y retrocederá hasta el punto en el que se pueda elegir otra cosa, por lo que es un primer algoritmo básico de profundidad.

Al no usar heurística, no es particularmente eficiente. Tomé este rompecabezas de Wikipedia ( http://en.wikipedia.org/wiki/Sudoku ):

$ time python sudoku.py 530070000600195000098000060800060003400803001700020006060000280000419005000080079
534678912672195348198342567859761423426853791713924856961537284287419635345286179

real    0m47.881s
user    0m47.223s
sys 0m0.137s

Anexo: Cómo lo reescribiría como programador de mantenimiento (esta versión tiene una aceleración de 93x :)

import sys

def same_row(i,j): return (i/9 == j/9)
def same_col(i,j): return (i-j) % 9 == 0
def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)

def r(a):
  i = a.find('0')
  if i == -1:
    sys.exit(a)

  excluded_numbers = set()
  for j in range(81):
    if same_row(i,j) or same_col(i,j) or same_block(i,j):
      excluded_numbers.add(a[j])

  for m in '123456789':
    if m not in excluded_numbers:
      # At this point, m is not excluded by any row, column, or block, so let's place it and recurse
      r(a[:i]+m+a[i+1:])

if __name__ == '__main__':
  if len(sys.argv) == 2 and len(sys.argv[1]) == 81:
    r(sys.argv[1])
  else:
    print 'Usage: python sudoku.py puzzle'
    print '  where puzzle is an 81 character string representing the puzzle read left-to-right, top-to-bottom, and 0 is a blank'

desenmascararlo:

def r(a):
    i = a.find('0') # returns -1 on fail, index otherwise
    ~i or exit(a) # ~(-1) == 0, anthing else is not 0
                  # thus: if i == -1: exit(a)
    inner_lexp = [ (i-j)%9*(i/9 ^ j/9)*(i/27 ^ j/27 | i%9/3 ^ j%9/3) or a[j] 
                   for j in range(81)]  # r appears to be a string of 81 
                                        # characters with 0 for empty and 1-9 
                                        # otherwise
    [m in inner_lexp or r(a[:i]+m+a[i+1:]) for m in'%d'%5**18] # recurse
                            # trying all possible digits for that empty field
                            # if m is not in the inner lexp

from sys import *
r(argv[1]) # thus, a is some string

Entonces, solo necesitamos resolver la expresión de la lista interna. Sé que recopila los dígitos establecidos en la línea; de lo contrario, el código que lo rodea no tiene sentido. Sin embargo, no tengo ni idea de cómo lo hace (y estoy demasiado cansado para resolver esa fantasía binaria en este momento, lo siento)

r(a)es una función recursiva que intenta completar un 0en el tablero en cada paso.

i=a.find('0');~i or exit(a)es la terminación con éxito. Si no 0existen más valores en el tablero, hemos terminado.

mes el valor actual con el que intentaremos rellenar 0.

m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)]evalúa la verdad si es obviamente incorrecto poner mla corriente 0. Pongamos el sobrenombre de "is_bad". Esta es la parte más complicada. :)

is_bad or r(a[:i]+m+a[i+1:]es un paso recursivo condicional. Intentará evaluar de forma recursiva el siguiente 0 en el tablero si el candidato de solución actual parece estar cuerdo.

for m in '%d'%5**18 enumera todos los números del 1 al 9 (de forma ineficaz).

Muchos de los solucionadores de sudoku cortos simplemente prueban recursivamente todos los números legales posibles que quedan hasta que hayan llenado con éxito las celdas. No he desarmado esto, pero solo examinándolo, parece que eso es lo que hace.

El código no funciona realmente. Puede probarlo usted mismo. Aquí hay una muestra de sudoku sin resolver:

807000003602080000000200900040005001000798000200100070004003000000040108300000506

Puede utilizar este sitio web ( http://www.sudokuwiki.org/sudoku.htm ), hacer clic en importar rompecabezas y simplemente copiar la cadena anterior. La salida del programa Python es: 817311213622482322131224934443535441555798655266156777774663869988847188399979596

que no corresponde a la solución. De hecho, ya puedes ver una contradicción, dos 1 en la primera fila.