[Python-de] Sudoku mit Python

Diez B. Roggisch deets at web.de
Fre Aug 4 11:22:51 CEST 2006


> Ja, es rödelt ganz schön. Man kann die Schleifen begrenzen. Meine 
> Versuche haben gezeigt, dass es mit ca. 10-15 Durchläufe erledigt ist. 
> Darum habe ich eine Max von 50 eingegeben.
> Jetzt habe ich ein Demo eingerichtet (Zahlenvorgabe).

Also da faellt einem schon so einiges auf:


Die Repraesentation

   Es ist zwar legitim, dafuer ein dict von Koordinate nach Belegung zu 
nehmen - aber da ein sudoku ja keine Luecken haben kann (nur unbestimmte 
Felder, aber fehlen tun die ja nicht), macht man das normalerweise mit 
einer liste von listen.

  Zweitens ist es nicht clever, die Freiheitsgrade einfach mit 0 zu 
belegen - damit hast du ja garkeine Informationen mehr! Besser ist es, 
pro Feld eine Menge (set) zu speichern, mit den moeglichen Werten. Fuer 
unbelegte Felder ist das dann set(xrange(1, 10)), fuer vorbelegte 
set([belegung])

Dann kannst du dir auch die explizite Zero-Speicherung sparen. Zero ist 
wo zuviel drin ist!

Berechnung der Zellenkoordinaten

  Du berechnest die jedes mal, aber noch nicht mal "richtig". Soll 
heissen: entweder erstellt man ein dictionary, das die Zellen-nummer auf 
die Koordinaten abbildet, oder man errechnet das wirklich. Letzteres 
waere zb so moeglich:

def cellcols(n, width=3):
     start = (n % width) * width
     return xrange(start, start + width)

def cellrows(n, width=3):
     start = (n / width) * width # achtung, integer division! Eventuell 
// verwenden
     return xrange(start, start + width)


Aber du machst halt einen unsinnvollen Mischmasch aus beidem - 
festkodiertes Wissen und code. Und selbst wenn du auf obigen Trick nicht 
gekommen waerst: man kann die Werte dann ja mal minimal cachen!

Algorithmus

   Abgesehen das ValueFailt ValuesMissing heissen sollte, ist es 
hochgerading ineffizient. Denn statt dir das einmal zu merken und immer 
nur Werte wegzunehmen, berechnest du das jedes mal neu.

Und dann "kann" dein Algorithmus auch wirklich nur die einfachsten aller 
Sudokus loesen: wo sich jedes mal ein Feld neu ergibt, aus simpler 
Schnittmengenberechnung der Zelle, Reihe und Spalte. Es gibt aber 
Sudokus, bei denen man so nicht weiterkommt. Da muss man dann mittels 
Backtracking spekulativ vorgehen.

Dann zaehlst du die moeglichen Werte pro Element immer durch - dabei 
koenntest du im Fall von >1 sofort abbrechen!

Was du aber auf jeden Fall vermeiden solltest ist diese komische 
Abbruchbedingung als Schleife - das ist Unfug. Stattdessen merkst du 
dir, ob du wirklich was veraendert hast. Der Algorithmus laeuft dann 
solange durch, bis sich nix mehr getan hat. Und entweder ist das Ding 
dann geloest, oder eben nicht.



Ich habe mal meinen sehr alten solver angehangen - er kann nur eine 
Optimierung (naked pairs), aber dank backtracking loest er jedes Sudoku.


MfG Diez
-------------- nächster Teil --------------
Ein Dateianhang mit Binärdaten wurde abgetrennt...
Dateiname   : sudoku.py
Dateityp    : application/x-python
Dateigröße  : 4559 bytes
Beschreibung: nicht verfügbar
URL         : http://starship.python.net/pipermail/python-de/attachments/20060804/eaa2d2fd/sudoku-0001.bin


More information about the python-de mailing list