Backtracking: Sudoku

Wenden wir uns den Auslösern für die PCNEWS-Beitrag zu: zu den Rätseln in der Sonntagsausgabe der Presse. Ich vermute, dass die Sudoku-Regeln den meisten Lesern bekannt sind. Trotzdem hier noch einmal eine Kurzfassung:

Beim Sudoku sind in einem 9×9-Quadrat die Zahlen 1 bis 9 so zu verteilen, dass jede Zahl in jeder Zeile, in jeder Spalte und in jedem der neun 3×3-großen Unterquadrate genau einmal vorkommt. Das wäre aber zu leicht. Daher sind die Zahlen einzelner Felder schon vorgegeben.

Dazu bedarf es einer passenden internen Darstellung und einiger Rechenmethoden: Datei sudiku.py. Die Felder des 9×9-Quadrats (oder “Plätze” im Quadrat) werden der Reihe nach gefüllt. Deshalb ist es praktisch, sie von 0 bis 80 zu nummerieren. Wir haben wieder einen vector, der zu Beginn mit 81 Nullen gefüllt wird. Jedes Mal, wenn eine neue Zahl vergeben wird, steigen wir bei der Lösung des Problems um einen level “hinauf”. Daher ist der level gleich dem Index der Liste vector, die mit einem Wert (aus move) gefüllt wird.

Um den Ablauf zu beschleunigen und nur jene Zahlen in Betracht zu ziehen, die noch nicht verwendet wurden, legen wir für jede Zeile, für jede Spalte und für jedes Unterquadrat eine Menge (set) an. Wenn eine Zahl widerspruchsfrei eingefügt werden kann, wird sie im vector an der Stelle mit dem Index level gespeichert und in die drei Mengen, die zu diesem Platz gehören, eingefügt. Das macht die Methode record. Wenn sich später herausstellt, dass die Zahl doch nicht zur Lösung führt, setzt undo den Eintrag in der Liste vector auf 0 und entfernt die Zahl aus den drei Mengen.

getSets: Bei etlichen Vorgängen müssen aus dem Index (dem level) die Nummer der Zeile, der Spalte und des Unterquadrats bestimmt werden und daraus die zugehörigen Mengen ermittelt werden. Das wird von der Methode getSets erledigt. Sie errechnet aus dem level vorerst die Nummern der Zeile (rr), der Spalte (cc) und Unterquadrats (ss).

• Die Zeilennummer eines Feldes ist gleich Index (level), ganzzahlig geteilt (Divisionssymbol “//“) durch die Größe des Quadrats (hier gehen wir von 9 aus, aber das Programm kann auch mit anderen Größen umgehen).
• Die Spaltennummer ist gleich dem Divisionsrest des Index geteilt durch diese Größe.
• Die Nummer des Unterquadrats wird etwas trickreich bestimmt: die Zeilennummer rr wird ganzzahlig durch die Größe des Unterquadrats (hier: 3) geteilt und gleich wieder damit multipliziert. Damit erhalten die Unterquadrate die Nummern 0, 3 und 6. Danach muss aus der Spalte cc ebenso errechnet werden, welches der drei nebeneinander liegenden Unterquadrate gemeint ist: demnach wird 0, 1 oder 2 zu der Zahl aus dem ersten Schritt addiert.

Die Zwischenrechnungen sind abgeschlossen, die Methode getSets gibt eine Liste mit den drei Sets, die zu rr, cc und ss gehören, zurück.

moves liefert eine Liste, die jene Werte enthält, die in das Feld mit der Nummer level eingefügt werden können und der Reihe nach zu überprüfen sind.

Aber was ist mit den schon vorgegebenen Zahlen? Hier kommt das Dictionary sudoku zum Einsatz. Python unterscheidet zwischen Groß- und Kleinbuchstaben in Namen, Sudoku ist der Name der Klasse, sudoku heißt das Dictionary, das die Aufgabe beschreibt. Für jeden bereits (in der Angabe des Rätsels) belegten Platz bekommt sudoku einen Eintrag, dessen Schlüssel die Platznummer ist und dessen Wert sich aus der Angabe ergibt. Im Beispiel hat der Platz ganz links oben den Schlüssel 0 und den Wert 3 und daher den Eintrag sudoku = { 0:3, ... }

Ist der Wert von level als Schlüssel in sudoku enthalten, ist der zugehörige Wert die einzige Zahl, die Moves liefert: der Wert ist vorgegeben, daher darf gar nichts anderes erprobt werden. Andernfalls ermittelt moves alle jene Zahlen, die nicht in jenen drei Mengen enthalten sind, die von getSets ermittelt worden sind. Dabei wird wieder die Mengendifferenz verwendet.

valid bestimmt, ob die einzufügende Zahl (move) widerspruchsfrei in das Sudoku-Quadrat eingefügt werden kann. Das ist ganz einfach: valid liefert True, wenn die Zahl in keiner der drei Mengen, die zu dem Platz mit der Nummer level gehören, enthalten ist.

done untersucht, ob level den Höchstwert erreicht hat. Wenn ja haben wir eine Lösung, die mit show (zusammen mit einem erklärenden Text) ausgegeben wird.

Ja, das Ganze ist schon etwas komplizierter als das Platzieren von 8 Königinnen. Aber mit der objektorientierten Programmierung ist alles recht sauber getrennt.

sudoku.py

# File sudoku.py

from backtrack import Backtrack

import math

 

class Sudoku(Backtrack):

 

    vector = []

    size = 9

    sqrtSize = int(math.sqrt(size))

    solutionNr = 0

   

 

    rset = [set() for i in range(size)]  # row sets

    cset = [set() for i in range(size)]  # column sets

    sset = [set() for i in range(size)]  # subsquare sets

 

    sudoku = { # leicht

        0:3, 4:1,

        12:5, 14:6, 15:9, 16:8,

        20:9, 25:1, 26:5,

        28:9, 29:4, 30:3, 31:6, 32:7, 34:5, 35:2,

        37:1, 38:7, 40:9, 41:5, 42:3, 43:4, 44:8,

        46:2, 47:3, 51:6,

        54:4, 56:6, 58:5, 59:2,

        63:9, 66:1, 68:3, 71:4,

        74:5, 78:8

        }

 

    values = range(1, size+1)

 

    def __init__(self, test:bool= False, showAttempts:bool = False):        

        self.vector = [0 for i in range(self.size*self.size)]

        super().__init__(test, showAttempts)

 

    def getSets(self, level:int):

        s = self.size

        sq = self.sqrtSize

 

        # Zeilennummer bestimmen: 0 bis size-1

        rr = level // s

 

        # Spaltennummer bestimmen: 0 bis size-1

        cc = level % s

 

        # Nummer des Unterquarats bestimmen: 0 bis size-1

        ss = rr // sq * sq + cc // sq

 

        return [self.rset[rr], self.cset[cc], self.sset[ss]]

 

    def moves(self, level: int):

        res = self.sudoku.get(level, 0)

        if res:

            return [res]

        return list(set(self.values) – set().union(*self.getSets(level)))

   

    def valid(self, level: int, move) -> bool:

        return move not in set().union(*self.getSets(level))

 

    def done(self, level: int):

        if level==self.size*self.size-1:

            self.solutionNr += 1

            self.show(f"Resultat {self.solutionNr:4d}")

            return True

        return False        

   

    def record(self, level: int, move):

        self.vector[level]=move  

        for s in self.getSets(level):

            s.add(move)        

 

        if self.test:

            print (level, move, rr, cc, ss, self.rset[rr], self.cset[cc], self.sset[ss])

 

    def undo(self, level: int, move):

        self.vector[level]=0

        for s in self.getSets(level):

            s.discard(move)        

 

    def show(self, text):

        print(f"\n{text}")

        for r in range(self.size):

            print(self.vector[r*self.size : (r+1)*self.size])      

   

if __name__ == "__main__":

    Sudoku(test=False, showAttempts=True)

 

Und hier das Ergebnis:

Resultat    1
[3, 5, 8, 4, 1, 9, 2, 7, 6]
[7, 4, 1, 5, 2, 6, 9, 8, 3]
[2, 6, 9, 7, 3, 8, 4, 1, 5]
[8, 9, 4, 3, 6, 7, 1, 5, 2]
[6, 1, 7, 2, 9, 5, 3, 4, 8]
[5, 2, 3, 8, 4, 1, 6, 9, 7]
[4, 8, 6, 9, 5, 2, 7, 3, 1]
[9, 7, 2, 1, 8, 3, 5, 6, 4]
[1, 3, 5, 6, 7, 4, 8, 2, 9]
       6_432_362 attempts in    41.54 seconds

Somit ist das die einzige Lösung, grafisch aufbereitet:

Erweiterungen

• Auf janko.at (https://www.janko.at/Raetsel/) oder puzzlephil (https://puzzlephil.com/) sind viele interessante Rätsel zu finden. Dazu zählen Sudokus, bei denen statt der Unterquadrate oder zusätzlich zu den Unterquadraten andere Formen, meist durch Farben gekennzeichnet, verwendet werden. Mit einer geänderten valid-Methode können diese Sudokus auch rasch gelöst werden.
• Auch Sudokus in der Form eines sechsstrahligen Sterns löst das Programm. An dieser Stelle zeigt sich, dass die Darstellung als vector für alle Formen geeignet ist. Wäre die Aufgabe mit einem zweidimensionalen Feld gelöst worden, wäre der Wechsel zu einem Stern nicht einfach.

Verbesserungsmöglichkeiten

• Wie beim Beispiel der Königinnen werden die Größe und die Variable sudoku als Parameter übergeben. Aufruf mit Sudoku(size=9, sudoku= { 0:3, 4:1, 12:5, 14:6, 15:9, 16:8, 20:9, 25:1, 26:5,…})
  Zu finden in sudoku2_py.
• Die Ausgabe könnte grafisch schöner sein.

Ich habe auf all das verzichtet, um das Programm nicht weiter zu vergrößern.

Es gibt noch genug zu tun!

Links

• Alle Dateien
• Was ist eigentlich ‘Backtracking’? (clubcomputer.at)
• Backtracking: Königinnenproblem (clubcomputer.at)
• Backtracking: Sudoku (clubcomputer.at)
• Backtracking: Kendoku (clubcomputer.at)
• Backtracking: Skyline (clubcomputer.at)
• Backtracking: Zeltlager (clubcomputer.at)