Smart Sudoku Golf

Question

Le but de cette question est de créer le résolveur de Sudoku le plus court sans abuser lente . Ceci est défini comme suit: ne recurse pas quand il y a des taches sur le tableau qui ne peuvent contenir qu'un seul chiffre .

Voici le plus court que j'ai jusqu'ici 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 dernière ligne que je considère comme faisant partie de l'entrée de ligne cmd peut être remplacée par:

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

Cela ressemble à d’autres défis de golf au sudoku, sauf que je veux éliminer les récursions inutiles. Toute langue est acceptable. Le défi est lancé!

Answer 1

Je n'ai pas vraiment fait grand-chose de changement - l'algorithme est identique, mais voici quelques micro-optimisations supplémentaires que vous pouvez effectuer sur votre code python.

• Pas besoin de! = 0, 0 est faux dans un contexte booléen.

• a si c sinon b est plus cher que d'utiliser [a, b] [c] si vous n'avez pas besoin de court-circuit, vous pouvez donc utiliser h [[0, A [j] ] [j / 9 .. reste de la condition booléenne] . Encore mieux, exploitez le fait que vous voulez 0 dans le cas faux et multipliez-le par la valeur booléenne (traité comme 0 * A [j] (c.-à-d. 0) ou 1 * A [j] (c'est-à-dire A [j] ).

• Vous pouvez omettre les espaces entre les chiffres et les identificateurs. Par exemple, " 9 ou " - > " 9ou "

• Vous pouvez omettre la clé pour trier (). Puisque vous triez sur le premier élément, un tri normal produira effectivement le même ordre (à moins que vous ne dépendiez de la stabilité, ce à quoi il ne ressemble pas).

• Vous pouvez enregistrer quelques octets en omettant l'appel .items (), et affectez simplement h, i à la ligne suivante à z [l]

• Vous n'utilisez s qu'une fois - cela ne sert à rien d'utiliser une variable. Vous pouvez également éviter d'utiliser range () en sélectionnant la tranche de r appropriée à la place (r [1:10])

• j pas dans h peut devenir (j dans h) -1 (en s'appuyant sur True == 1 dans un contexte entier)

• [Éditer] Vous pouvez également remplacer la première de la construction de la boucle for de h par un constructeur de dict et une expression génératrice. Cela vous permet de compresser la logique sur une ligne, en économisant au total 10 octets.

Plus généralement, vous voudrez probablement réfléchir à des moyens de modifier l’algorithme afin de réduire les niveaux d’imbrication. Chaque niveau donne un octet supplémentaire par ligne dans python, qui s'accumule.

Voici ce que j’ai eu jusqu’à présent (j’ai opté pour un espace par retrait afin d’obtenir une image précise des caractères requis. Actuellement, il pèse < 288 278, ce qui est toujours assez gros.

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 caractères, et il trouve toutes les solutions. Utilisation (non compté dans le nombre de caractères):

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

Answer 3

Je viens de couper un peu le python ici:

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"))

Ceci est un lourd 410 caractères, 250 si vous ne comptez pas les espaces. Si vous le transformez simplement en Perl, vous serez sans aucun doute meilleur que le mien!