Kürzester Sudoku-Löser in Python - Wie funktioniert es?

Ich habe mit meinem eigenen Sudoku-Löser herumgespielt und nach Hinweisen auf gutes und schnelles Design gesucht, als ich darauf stieß:

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

Meine eigene Implementierung löst Sudokus genauso, wie ich sie in meinem Kopf löse, aber wie funktioniert dieser kryptische Algorithmus?

http://scottkirkwood.blogspot.com/2006/07/shortest-sudoku-solver-in-python.html

Nun, Sie können die Dinge ein wenig einfacher machen, indem Sie die Syntax korrigieren:

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

Ein wenig aufräumen:

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

Okay, dieses Skript erwartet ein Befehlszeilenargument und ruft die Funktion r darauf auf. Wenn diese Zeichenfolge keine Nullen enthält, wird r beendet und das Argument ausgedruckt.

(Wenn ein anderer Objekttyp übergeben wird, entspricht None der Übergabe von Null, und jedes andere Objekt wird in sys.stderr gedruckt und führt zu einem Exit-Code von 1. Insbesondere ist sys.exit ("eine Fehlermeldung") a schnelle Möglichkeit , ein Programm zu beenden , wenn ein Fehler auftritt. Siehe http://www.python.org/doc/2.5.2/lib/module-sys.html )

Ich denke, dies bedeutet, dass Nullen offenen Räumen entsprechen und ein Rätsel ohne Nullen gelöst wird. Dann gibt es diesen bösen rekursiven Ausdruck.

Die Schleife ist interessant: for m in'%d'%5**18

Warum 5 ** 18? Es stellt sich heraus, dass zu '%d'%5**18bewertet '3814697265625'. Dies ist eine Zeichenfolge, die jede Ziffer 1-9 mindestens einmal hat. Vielleicht wird versucht, jede von ihnen zu platzieren. Tatsächlich sieht es so aus, als ob dies der Fall r(a[:i]+m+a[i+1:])ist: rekursiv r aufrufen, wobei das erste Leerzeichen durch eine Ziffer aus dieser Zeichenfolge ausgefüllt wird. Dies geschieht jedoch nur, wenn der frühere Ausdruck falsch ist. Schauen wir uns das an:

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

Die Platzierung erfolgt also nur, wenn m nicht in dieser Monsterliste enthalten ist. Jedes Element ist entweder eine Zahl (wenn der erste Ausdruck ungleich Null ist) oder ein Zeichen (wenn der erste Ausdruck Null ist). m ist als mögliche Ersetzung ausgeschlossen, wenn es als Zeichen erscheint, was nur passieren kann, wenn der erste Ausdruck Null ist. Wann ist der Ausdruck Null?

Es besteht aus drei Teilen, die multipliziert werden:

• (i-j)%9 Das ist Null, wenn i und j ein Vielfaches von 9 voneinander entfernt sind, dh dieselbe Spalte.
• (i/9^j/9) Das ist Null, wenn i / 9 == j / 9, dh dieselbe Zeile.
• (i/27^j/27|i%9/3^j%9/3) Das ist Null, wenn beide Null sind:
• • i/27^j^27 Das ist Null, wenn i / 27 == j / 27, dh der gleiche Block aus drei Zeilen
• • i%9/3^j%9/3 Das ist Null, wenn i% 9/3 == j% 9/3 ist, dh der gleiche Block aus drei Spalten

Wenn einer dieser drei Teile Null ist, ist der gesamte Ausdruck Null. Mit anderen Worten, wenn i und j eine Zeile, eine Spalte oder einen 3x3-Block gemeinsam nutzen, kann der Wert von j nicht als Kandidat für das Leerzeichen bei i verwendet werden. 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])

Beachten Sie, dass, wenn keine der Platzierungen funktioniert, r zurückkehrt und bis zu dem Punkt zurückkehrt, an dem etwas anderes ausgewählt werden kann. Es handelt sich also um einen grundlegenden Tiefen-First-Algorithmus.

Ohne Heuristik ist es nicht besonders effizient. Ich habe dieses Puzzle aus Wikipedia ( http://en.wikipedia.org/wiki/Sudoku ) genommen:

$ time python sudoku.py 530070000600195000098000060800060003400803001700020006060000280000419005000080079
534678912672195348198342567859761423426853791713924856961537284287419635345286179

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

Nachtrag: Wie ich es als Wartungsprogrammierer umschreiben würde (diese Version hat ungefähr eine 93-fache Beschleunigung :)

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'

unauffällig:

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

Wir müssen also nur den Ausdruck der inneren Liste herausarbeiten. Ich weiß, dass es die in der Zeile eingestellten Ziffern sammelt - ansonsten macht der Code um ihn herum keinen Sinn. Ich habe jedoch keine wirkliche Ahnung, wie es das macht (und ich bin zu müde, um diese binäre Fantasie jetzt herauszufinden, sorry)

r(a)ist eine rekursive Funktion, die versucht, 0in jedem Schritt ein Feld auszufüllen .

i=a.find('0');~i or exit(a)ist die Kündigung bei Erfolg. Wenn 0im Board keine Werte mehr vorhanden sind, sind wir fertig.

mist der aktuelle Wert, mit dem wir versuchen werden, den Wert zu füllen 0.

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)]bewertet als wahr, wenn es offensichtlich falsch ist, mden Strom einzugeben 0. Nennen wir es "is_bad". Dies ist das schwierigste Stück. :) :)

is_bad or r(a[:i]+m+a[i+1:]ist ein bedingter rekursiver Schritt. Es wird rekursiv versucht, den nächsten 0 im Board zu bewerten, wenn der aktuelle Lösungskandidat vernünftig erscheint.

for m in '%d'%5**18 zählt alle Zahlen von 1 bis 9 auf (ineffizient).

Viele der kurzen Sudoku-Löser versuchen nur rekursiv jede mögliche zulässige Nummer, bis sie die Zellen erfolgreich gefüllt haben. Ich habe das nicht auseinander genommen, aber nur überflogen, es sieht so aus, als ob es das ist, was es tut.

Der Code funktioniert nicht wirklich. Sie können es selbst testen. Hier ist ein Beispiel für ein ungelöstes Sudoku-Puzzle:

807000003602080000000200900040005001000798000200100070004003000000040108300000506

Sie können diese Website ( http://www.sudokuwiki.org/sudoku.htm ) verwenden, auf Puzzle importieren klicken und einfach die obige Zeichenfolge kopieren. Die Ausgabe des Python-Programms lautet: 817311213622482322131224934443535441555798655266156777774663869988847188399979596

was nicht der Lösung entspricht. Tatsächlich sieht man bereits einen Widerspruch, zwei Einsen in der ersten Reihe.