Sudoku

This is an old revision of the document!

Ziel ist es, ein Sudoku-Solver zu programmieren, der die allermeisten Sudokus in nützlicher Frist lösen kann.

Wir werden eine Klasse Sudoku programmieren. Darin werden die Zahlen in einem 2-dimensionalen Array 9×9-Array gespeichert. Dazu werden wir Funktionen einbauen, die wir als Aufgaben bei den Funktionen schon programmiert haben.

Klasse zum Starten

sudoku.py

 
class Sudoku:
 
    def __init__(self):
        self.feld = [[0 for i in range(9)] for j in range(9)]
 
    # Liest ein Sudoku als String ein, z.B.
    # "003020600900305001001806400008102900700000008006708200002609500800203009005010300"
    # "200080300\n060070084\n030500209\n000105408\n\n000000000\n402706000\n301007040\n720040060\n004010003"
    def parse(self,s):
        x=0
        y=0
        for c in s:
            if (c>="0" and c<="9") or (c=="."):
                if c==".":
                    c="0"
                self.feld[x][y] = int(c)
                x+=1
                if (x==9):
                    x=0;
                    y+=1
 
    # Liest ein Sudoku von einer Text-Datei ein.
    def fromFile(self,f):
        file1 = open(f,"r")
        sudoku = file1.read()
        file1.close()
        self.parse(sudoku)
 
    # Umwandlung in ASCII-Art
    def __str__(self):
        hbar1 = ("#==="+"===="*2)*3+"#\n"
        hbar2 = ("#---"+"+---"*2)*3+"#\n"
        symbols = [str(i) for i in range(10)]
        symbols[0] = " "
        separators = ["|", "|", "#"]
        res = hbar1
        for y in range(9):
            res += "#"
            for x in range(9):    
                res += " "+symbols[self.feld[x][y]]+" "+separators[x%3]
            res+="\n"
            if y%3==2:
                res += hbar1
            else:
                res += hbar2
        return res
 
# ENDE der Klasse Sudoku        
 
# Beginn vom Hauptprogramm
 
s = Sudoku()
s.parse("003020600900305001001806400008102900700000008006708200002609500800203009005010300")
print(s)

Ziel: Eine Methode, die überprüft, ob eine Zahl in ein bestimmtes Feld darf:

  # Koordinaten von 0 bis 8
  def ok(zahl, x, y):
    # Zeile überpruefen
    # Spalte überpruefen
    a = x - x%3
    b = y - y%3
    # a,b ist die Koordinate oben links im 3x3-Subquadrat. Erklaeren Sie warum!
    # Subquadrat ueberpruefen
 
    # Alle Tests durch? Also
    return True

Als erstes brauchen wir ein Feld mit True/False-Werten, das angibt, ob die Zahl vorgegeben ist oder nicht. Schreiben Sie eine Methode dafür, oder verstehen Sie folgende Implementation

  def make_given(self):
    self.given = [[feld[i][j]!=0 for j in range(9)] for i in range(9)]

Wir haben folgende Variablen, die den Zustand der Suche beschreiben:

Das Feld mit Zahlen und Information, ob die einzelnen Zahlen vorgegeben sind oder nicht (self.given[x][y])
Aktuelle Position (x,y)

Des Weiteren brauchen wir

Eine Reihenfolge, um die Felder durchzugehen (z.B. zeilenweise).

Die Idee ist folgende: Wir probieren alle möglichen Zahlen für ein Feld aus und schauen, ob sich damit das Feld vollständig ausfüllen lässt. Ist es vollständig ausgefüllt, sind wir fertig. Gibt es auch für das erste Feld keine Möglichkeit, hat das Sudoku keine Lösung.

Initialisierung:
  Aktuelles Feld (x,y)=(0,0)
 
Wiederholen:
  Sei z1 = feld[x][y], die Zahl an der aktuellen Position (0 wenn leer)
  Sie z2 die nächst-grössere Zahl, die an die Position passt.
  Wenn es z2 nicht gibt:
    feld[x][y]=0 (wieder löschen)
    (x,y) auf die nächste, vorhergehende Position setzen, die nicht vorgegeben ist.
    Wenn es keine solche Position gibt:
       Melden, dass das Sudoku keine Lösung hat und abbrechen.
  Sonst:
    feld[x][y]=z2 (neue Zahl schreiben)
    (x,y) auf die nächste, nachfolgende Position setzen, die nicht vorgegeben ist.
    Wenn es keine solche Position gibt:
      Melden, dass die Lösung gefunden wurde und abbrechen.