Golfe Sudoku Inteligente

Question

O objetivo desta questão é criar o mais curto não abusivamente lento Solucionador de Sudoku.Isso é definido como: não repita quando houver pontos no tabuleiro que só possam ter um dígito.

Aqui está o mais curto que tenho até agora em 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"))

A última linha que considero fazer parte da entrada da linha cmd, pode ser alterada para:

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

Isso é semelhante a outros desafios de golfe sudoku, exceto que quero eliminar recursões desnecessárias.Qualquer idioma é aceitável.O desafio está lançado!

Answer 1

Eu realmente não fiz muita mudança - o algoritmo é idêntico, mas aqui estão mais algumas micro -otimizações que você pode fazer no seu código Python.

• Não há necessidade de! = 0, 0 é falsa em um contexto booleano.

• a se c else b é mais caro do que usar [a, b] [c] se você não precisar de curto-circuito, portanto, pode usar h[ [0,A[j]][j/9.. rest of boolean condition]. Ainda melhor é explorar o fato de que você deseja 0 no caso falso e, assim, multiplique pelo valor booleano (tratado como qualquer um 0*A[j] (ou seja, 0) ou 1*A[j] (ou seja. A[j]).

• Você pode omitir espaços entre dígitos e identificadores. por exemplo "9 or" -> "9or"

• Você pode omitir a chave para classificar (). Como você está classificando o primeiro elemento, um tipo normal produzirá efetivamente a mesma ordem (a menos que você esteja confiando na estabilidade, o que não parece)

• Você pode salvar alguns bytes omitindo a chamada .Items () e apenas atribua H, eu na próxima linha para z [l

• Você usa apenas S uma vez - não há sentido em usar uma variável. Você também pode evitar o uso de range () selecionando a fatia apropriada de r (r [1:10])

• j not in h pode se tornar (j in h)-1 (confiando em true == 1 no contexto inteiro)

• Editar Você também pode substituir o primeiro pela construção de H do Loop por um construtor ditado e uma expressão de gerador. Isso permite comprimir a lógica em uma linha, economizando 10 bytes no total.

De maneira mais geral, você provavelmente deseja pensar em maneiras de alterar o algoritmo para reduzir os níveis de nidificação. Cada nível fornece um byte adicional por linha dentro do Python, que se acumula.

Aqui está o que eu tenho até agora (mudei para 1 espaço por recuo para que você possa obter uma imagem precisa dos personagens necessários. Atualmente, está pesando 288 278, que ainda é muito 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 e encontra todas as soluções.Uso (não contado na contagem de caracteres):

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

Answer 3

Acabei de cortar um pouco o python aqui:

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 é um elegante 410 caracteres, 250 se você não conta o espaço em branco. Se você apenas transformá -lo em Perl, sem dúvida será melhor que o meu!