Smart Sudoku Golf

Question

Der Punkt dieser Frage ist die Schaffung der kürzesten nicht missbräuchlich langsam Sudoku solver.Dieser ist definiert als: don ' T recurse, wenn es sind Flecken auf der platine, die nur möglicherweise eine Ziffer.

Hier ist der kürzeste ich habe so weit in 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"))

Die Letzte Zeile nehme ich Teil des cmd-line-Eingang, es kann geändert werden, um:

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

Dies ist ähnlich zu anderen sudoku-golf-Herausforderungen, außer dass ich möchte, um unnötige Rekursion.Jede Sprache ist akzeptabel.Die challenge ist on!

Answer 1

Ich habe nicht wirklich viel ändern - der Algorithmus ist identisch, aber hier sind ein paar weitere Mikro-Optimierungen, die Sie vornehmen können, um Ihren python-code.

• Keine Notwendigkeit für !=0, 0 ist false, die in einem booleschen Kontext.

• a if c else b ist teurer als der Einsatz von [a,b], [c], wenn Sie brauchen nicht kurzschließen, damit Sie Sie verwenden können h[ [0,A[j]][j/9.. rest of boolean condition].Noch besser ist, zu nutzen, die Tatsache, dass Sie wollen, 0 in die falsche Fall, und so vermehren sich, indem Sie den booleschen Wert (behandelt, als entweder 0*A[j] (dh.0) oder 1*A[j] (dh. A[j]).

• Können Sie weglassen von Leerzeichen zwischen Ziffern und Kennungen an.eg "9 or" -> "9or"

• Können Sie weglassen der Schlüssel zum sortiert werden().Da Sie die Sortierung auf das erste element, eine normale Sortierung produzieren, effektiv die gleiche Reihenfolge (es sei denn, Sie verlassen sich auf die Stabilität, die es nicht so aussieht)

• Sie können sparen Sie ein paar bytes, die durch weglassen der .items () - Aufruf, und nur zuweisen, h,i in der nächsten Zeile z[l]

• Verwenden Sie nur s einmal kein Punkt in über eine variable.Sie können auch vermeiden Sie die Verwendung von range (), indem Sie die entsprechende Scheibe der r statt (r[1:10])

• j not in h werden kann (j in h)-1 (unter Berufung auf True == 1 integer-Kontext)

• [Bearbeiten] Sie können auch ersetzen die erste for-Schleife ist die Konstruktion von h mit einer dict-Konstruktor und einen generator-Ausdruck.Diese können Sie komprimieren die Logik auf eine Zeile, sparen 10 bytes in total.

Mehr im Allgemeinen, möchten Sie wahrscheinlich denken über die Möglichkeiten zum ändern des Algorithmus, um zu reduzieren die Ebenen der Verschachtelung.Jedes level bietet ein zusätzliches byte pro Zeile in python, der sich ansammelt.

Hier ist, was ich habe, so weit (ich habe eingeschaltet, um 1 Platz pro Gedankenstrich, so dass Sie ein genaues Bild von erforderlichen Zeichen.Derzeit ist es mit einem Gewicht von 288 278, das ist immer noch ziemlich groß.

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 Zeichen, und es findet alle Lösungen.Verwendung (nicht gezählt char count):

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

Answer 3

Ich habe gerade getrimmt, die python hier ein bisschen:

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

Dies ist eine saftige 410 Zeichen, 250, wenn Sie nicht zählen Leerzeichen.Wenn Sie schalten Sie es in perl werden Sie zweifellos besser als meine!