structures - El Sudoku Solver más corto en Python-¿Cómo funciona?

python algorithms mastering basic algorithms in the python language

Question

Estaba jugando con mi propio solucionador de Sudoku y estaba buscando algunos consejos para el 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 el Sudokus de la misma forma en 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

Answer 1

Bueno, puedes facilitar las cosas 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])

Limpiando 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])

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

(Si se pasa otro tipo de objeto, Ninguno es equivalente a pasar el 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 ciclo es interesante: for m in''%d''%5**18

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

m in [(ij)%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 colocación se hace 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 una posible sustitución si aparece como un 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:

• (ij)%9 que es cero si i y j son un múltiplo de 9 aparte, 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, una columna o un bloque de 3x3, entonces el valor de j no se puede usar como candidato para el espacio en blanco en i. Aha!

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 volverá al punto donde se puede elegir algo más, por lo que es un algoritmo básico de profundidad básica.

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

$ time python sudoku.py 530070000600195000098000060800060003400803001700020006060000280000419005000080079
534678912672195348198342567859761423426853791713924856961537284287419635345286179

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

Adición: Cómo lo reescribiría como programador de mantenimiento (esta versión tiene una aceleración de hasta 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''

Answer 2

El código en realidad no funciona. Puedes probarlo tú mismo. Aquí hay un ejemplo de sudoku sin resolver:

807000003602080000000200900040005001000798000200100070004003000000040108300000506

Puede usar este sitio web ( http://www.sudokuwiki.org/sudoku.htm ), hacer clic en Importar rompecabezas y simplemente copiar la cadena anterior. El resultado del programa python es: 817311213622482322131224934443535441555798655266156777774663869988847188399979596

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

Answer 3

Muchos de los pequeños solucionadores de sudoku prueban recursivamente todos los números legales posibles hasta que hayan llenado con éxito las celdas. No lo he desarmado, pero solo lo he rozado, parece que es lo que hace.

Answer 4

lo desenfocando:

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 recoge los dígitos establecidos en la línea; de lo contrario, el código 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)

Answer 5

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

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

m es el valor actual con el que trataremos de llenar el 0 .

m in[(ij)%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 obvio que es incorrecto poner m en el 0 actual. Vamos a apodarlo "is_bad". Este es el truco más complicado. :)

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

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