Smart Sudoku Golf

Question

El punto de esta pregunta es crear el más corto no abusivamente lento solucionador de Sudoku. Esto se define como: no retroceder cuando hay puntos en la pizarra que posiblemente solo pueden tener un dígito .

Aquí está el más corto que tengo hasta ahora en python:

r=range(81)
s=range(1,10)
def R(A):
    bzt={}
    for i in r:
        if A[i]!=0: continue; 
        h={}
        for j in r:
            h[A[j]if(j/9==i/9 or j%9==i%9 or(j/27==i/27)and((j%9/3)==(i%9/3)))else 0]=1
        bzt[9-len(h)]=h,i
    for l,(h,i)in sorted(bzt.items(),key=lambda x:x[0]):
        for j in s:
            if j not in h:
                A[i]=j
                if R(A):return 1
        A[i]=0;return 0
    print A;return 1

R(map(int, "080007095010020000309581000500000300400000006006000007000762409000050020820400060"))

La última línea que tomo como parte de la entrada de la línea cmd, se puede cambiar a:

import sys; R(map(int, sys.argv[1]);

Esto es similar a otros desafíos de sudoku golf, excepto que quiero eliminar la recursión innecesaria. Cualquier idioma es aceptable. ¡El desafío está en marcha!

Answer 1

Realmente no he hecho muchos cambios, el algoritmo es idéntico, pero aquí hay algunas micro-optimizaciones adicionales que puedes hacer con tu código de Python.

• No hay necesidad de! = 0, 0 es falso en un contexto booleano.

• a si c más b es más caro que usar [a, b] [c] si no necesita cortocircuito, por lo tanto, puede usar h [[0, A [j] ] [j / 9 .. resto de condición booleana] . Aún mejor es explotar el hecho de que desea 0 en el caso falso, y así multiplicar por el valor booleano (tratado como 0 * A [j] (es decir, 0) o 1 * A [j] (es decir, A[j? ).

• Puede omitir espacios entre dígitos e identificadores. por ejemplo, " 9 o " - > " 9or "

• Puedes omitir la clave para ordenar (). Ya que estás clasificando en el primer elemento, una ordenación normal producirá efectivamente el mismo orden (a menos que estés confiando en la estabilidad, que no parece)

• Puede guardar un par de bytes al omitir la llamada .items (), y simplemente asignar h, i en la siguiente línea a z [l]

• Solo usa s una vez; no tiene sentido usar una variable. También puede evitar usar el rango () seleccionando la porción apropiada de r en su lugar (r [1:10])

• j no en h puede convertirse en (j in h) -1 (basándose en True == 1 en contexto entero)

• [Editar] También puede reemplazar el primero para la construcción de bucle de h con un constructor de dict y una expresión de generador. Esto le permite comprimir la lógica en una línea, ahorrando 10 bytes en total.

Más en general, es probable que desee pensar en formas de cambiar el algoritmo para reducir los niveles de anidación. Cada nivel proporciona un byte adicional por línea dentro de python, que se acumula.

Esto es lo que tengo hasta ahora (cambié a 1 espacio por sangría para que pueda obtener una imagen precisa de los caracteres requeridos. Actualmente está pesando en 288 278, que es sigue siendo bastante grande.

r=range(81)
def R(A):
 z={} 
 for i in r:
  if 0==A[i]:h=dict((A[j]*(j/9==i/9or j%9==i%9or j/27==i/27and j%9/3==i%9/3),1)for j in r);z[9-len(h)]=h,i
 for l in sorted(z):
  h,i=z[l]
  for j in r[1:10]:
   if(j in h)-1:
    A[i]=j
    if R(A):return A
  A[i]=0;return[]
 return A

Answer 2

r=range(81)
def R(A):
 if(0in A)-1:yield A;return
 def H(i):h=set(A[j]for j in r if j/9==i/9or j%9==i%9or j/27==i/27and j%9/3==i%9/3);return len(h),h,i
 l,h,i=max(H(i)for i in r if not A[i])
 for j in r[1:10]:
  if(j in h)-1:
   A[i]=j
   for S in R(A):yield S
  A[i]=0

269 caracteres, y encuentra todas las soluciones. Uso (no contado en el recuento de caracteres):

sixsol = map(int, "300000080001093000040780003093800012000040000520006790600021040000530900030000051")
for S in R(sixsol):
    print S

Answer 3

Acabo de recortar un poco la pitón aquí:

r=range(81);s=range(1,10)
def R(A):
    z={}
    for i in r:
        if A[i]!=0:continue
        h={}
        for j in r:h[A[j]if j/9==i/9 or j%9==i%9 or j/27==i/27 and j%9/3==i%9/3 else 0]=1
        z[9-len(h)]=h,i
    for l,(h,i)in sorted(z.items(),cmp,lambda x:x[0]):
        for j in s:
            if j not in h:
                A[i]=j
                if R(A):return A
        A[i]=0;return[]
    return A

print R(map(int, "080007095010020000309581000500000300400000006006000007000762409000050020820400060"))

Este es un alto 410 caracteres, 250 si no cuenta los espacios en blanco. ¡Si solo lo conviertes en perl, sin duda serás mejor que el mío!