Das logische Zahlenrätsel Sudoku ist nicht nur ein beliebtes Freizeitvergnügen, sondern auch eine Herausforderung an Programmierer. Das Backtracking-Verfahren löst manch komplexes Problemen und spielt eine tragende Rolle in der KI-Forschung.

Seit letztem Sommer sind Sudokus – japanisch “die einzige Zahl” – omnipräsent. Sie erscheinen in Zeitungen, Zeitschriften und auf Cornflakes-Packungen, die Zahl der Sudoku-Bücher übertrifft an vielen Kiosken sogar die für klassische Kreuzworträtsel. Im Gegensatz zu den Kreuzworträtseln basieren Sudokus auf einer mathematischen Logik, sie sind somit per Automatik durch Computer lösbar – wenn auch nicht ganz trivial.

Problem und Lösung

Laut Wikipedia tauchte Sudoku [1] in großem Maßstab Mitte der 80er Jahre erstmals in japanischen Tageszeitungen auf und trat 2005 den Siegeszug im Rest der Welt an. Das Spielfeld besteht aus neun Zeilen und neun Spalten, wobei einige Felder mit Zahlen belegt sind und der Rest leer ist. Die leeren Kästchen muss der Spieler so füllen, dass in jeder Zeile und in jeder Spalte die Zahlen eins bis neun jeweils nur einmal vorkommen. Außerdem teilt sich das Feld in neun Blöcke von je drei mal drei Kästchen, die ebenfalls die Zahlen eins bis neun enthalten sollen.

Das hier vorgestellte Beispielprogramm ignoriert die dritte Bedingung jedoch und konzentriert sich auf die Grundlagen des Lösungsverfahrens. Zum Einsatz kommt dafür ein aus anderen Anwendungsbereichen bekannter Algorithmus: das Backtracking (Rückverfolgung) oder auch Rücksetzverfahren. Es untersucht die einzelnen Äste eines Lösungsbaums nacheinander, bis die einzig mögliche Option übrig bleibt.

Das Mini-Sudoku in Abbildung 1 besteht aus einem Feld mit drei Zeilen zu je drei Spalten, in dem die Werte dreier Kästchen vorgegeben sind. Der Spieler darf jedes Kästchen nur mit einer Zahl zwischen eins und drei füllen, sodass in allen Zeilen und Spalten jede Zahl nur einmal vorkommt. Zeilen wie 1, 3, 3 oder 2, 1, 1 sind also nicht erlaubt. Für die Lösung dieses Puzzles gibt es mehrere Möglichkeiten.

Abbildung 1: Ein Mini-Sudoku mit drei mal drei Kästchen liefert dieselbe Problemstellung in kleinerem Rahmen.

Das Beispielprogramm konzentriert sich auf die Lücken, deshalb ignoriert es die bereits belegten Kästchen zunächst. Für jedes leere Kästchen muss es eine Zahl finden, die bis zu diesem Zeitpunkt weder in derselben Zeile noch in der Spalte vorkommt. Dafür bedarf es einer Funktion, die beide Dimensionen nach bislang unbenutzten Zahlen durchsucht. Daraus wählt das Programm eine aus und geht nach rechts weiter bis zum letzten Kästchen.

Um das Design nicht unnötig kompliziert zu gestalten, verwendet das folgende Beispiel eine Liste, die ihrerseits drei Listen enthält. Jede Zeile im Sudoku entspricht einer Liste. Die folgende Form repräsentiert das Mini-Sudoku aus Abbildung 1:

>>> sudoku = [[1,0,0], [0,2,0], [0,0,3]]
>>> sudoku[0][0]
1
>>> sudoku[1][2]
0

Der Eintrag »0« repräsentiert ein leeres Kästchen. Bei der Navigation durch das Sudoku muss das Programm das Ende der Zeile beachten, um in der nächsten fortzufahren. Dafür sorgt die Klasse »Position« (Listing 1).

Vorzeigeklasse

»Position« ermöglicht über ihre Methoden eine einfache Positionskontrolle. Sie funktioniert wie ein Iterator: Zuerst legt sie im Konstruktor die Grenzen des Spielfelds fest. Die Methode »naechste()« (Zeile 39 in Listing 1) sorgt für das Weiterschreiten, weitere Methoden setzen Werte ein oder nehmen sie entgegen. »getPos()« (Zeile 51) liefert die aktuelle Position, »setZeile()« (Zeile 10) und »setSpalte()« (Zeile 18) steuern eine bestimmtes Kästchen an und »ende()« (Zeile 32) gibt den booleschen Wert »True« zurück, falls sich der Zeiger im letzten Feld des Spielfelds befindet.

Zum besseren Verständnis tragen sämtliche Klassen, Funktionen und Methoden – im Gegensatz zum empfohlenen Standard Englisch – deutsche Namen. Der interaktive Modus des Python-Interpreters eignet sich dazu, die Methoden der Klasse »Position« auszuprobieren:

>>> p = Position(1,1)
>>> p.getPos()
[0,0]
>>> p.naechste()
>>> p.naechste()
>>> p.getPos()
[1,0]
>>> p.naechste ()
>>> p.naechste ()
>>> p.ende()
true
>>> p.getPos()
[-1,-1]

»Position« nimmt die Zahl der Zeilen und Spalten entgegen. Wenn es sich wie gewöhnlich um ein Quadrat handelt, sind die beiden Werte identisch.

01 class Position:
02 ### Verwaltet eine Position durch
03 ### die Kontrolle der ausgeführten Schritte über das Spielfeld
04   def __init__(self,maxzeile,maxspalte):
05     self.maxzeile = maxzeile
06     self.maxspalte = maxspalte
07     self.zeile = 0
08     self.spalte = 0
09 
10   def setZeile(self, zeile):
11     if zeile < 0:
12       self.zeile = 0
13     elif zeile >= self.maxzeile:
14       self.zeile = -1
15     else:
16       self.zeile = zeile
17 
18   def setSpalte(self, spalte):
19     if spalte < 0:
20       self.spalte = 0
21     elif spalte >= self.maxspalte:
22       self.spalte = -1
23     else:
24       self.spalte = spalte
25 
26   def getZeile(self):
27     return self.zeile
28 
29   def getSpalte(self):
30     return self.spalte
31 
32   def ende(self):
33     return self.zeile==-1 and self.spalte==-1
34 
35   def reset(self):
36     self.zeile = 0
37     self.spalte = 0
38 
39   def naechste(self):
40   # Erhöht die Position und achtet über die Methode »ende()« darauf,
41   # dass sie nicht über das Feld hinausgeht.
42     if not self.ende():
43       self.spalte += 1
44       if self.spalte == self.maxspalte:
45         self.spalte = 0
46         self.zeile +=1
47         if self.zeile == self.maxzeile:
48           self.zeile = -1
49           self.spalte = -1
50 
51   def getPos(self):
52     return [self.zeile, self.spalte]

Auf den Schirm

Listing 2 zeigt eine Funktion »drucken()«, die das Sudoku auf dem Bildschirm ausgibt und zwei Parameter entgegegennimmt: das Sudoku in Form einer Liste aus Listen, die die vorgegebenen Werte jeder Zeile enthalten, und eine Liste weiterer bereits zugewiesener Werte mit Positionsangaben. Statt die leeren Kästchen des eigentlichen Sudoku zu füllen, legt sie die zu einem Kästchen gehörenden Zahlen in einem Stapel ab, der jedes Element in der Form Zeile, Spalte, Wert enthält. In der Funktion »drucken()« heißt dieser Stapel »zugewiesene«. Abbildung 2 zeigt die Ausgabe mit einem Beispielrätsel.

01 def drucken(sudoku, zugewiesene):
02   strich = ""
03   for i in range(0,SPALTEN):
04     strich += "·---"
05   strich += "."
06 
07   print strich
08   for zeile in range(0,len(sudoku)):
09     zeichenkette = ""
10     for spalte in range(0,len(sudoku)):
11       if sudoku[zeile][spalte] == 0:
12         gefunden = False
13         for a in zugewiesene:
14           if a[0] == zeile and a[1] == spalte:
15             zeichenkette += "| "+ str(a[2]) + " "
16             gefunden = True
17         if not gefunden:
18           zeichenkette += "|"+"   "
19       else:
20         zeichenkette += "| "+str(sudoku[zeile][spalte])+" "
21     zeichenkette += "|"
22     print zeichenkette
23     print strich

Abbildung 2: Die Funktion »drucken()« (Listing 2) gibt ein als Parameter übergebenes Sudoku auf dem Bildschirm aus.

Für jede Lücke muss der Suchalgorithmus eine Liste mit den Zahlen erzeugen, die weder in der zugehörigen Zeile noch in derselben Spalte auftauchen. Darum kümmert sich die Funktion »test()« (Listing 3), indem sie eine Liste aus den noch unbenutzten Zahlen erzeugt. Dazu testet sie alle möglichen Werte sowohl für die Zeile als auch für die Spalte. Passt keine der als Parameter übergebenen Zahlen, gibt sie eine Liste mit dem Inhalt »[-1]« zurück.

01 def test(sudoku, zugewiesene, zeile, spalte):
02   # Die Funktion nimmt vier Parameter entgegen und kann drei Werte zurückgeben:
03   # a) [] wenn besetzt
04   # b) Liste der möglichen Zahlen
05   # c) [-1] wenn nicht möglich
06 
07   if sudoku[zeile][spalte] != 0:
08     return []
09 
10   else:
11     ergebnis = []
12 
13     # Probiert alle moeglichen Zahlen
14     for n in range(1,LINIEN+1):
15       existiert = False
16       # Linien löschen
17       for l in range(0,LINIEN):
18         if sudoku[l][spalte] == n:
19           existiert = True
20           break
21 
22       # Spalten löschen
23       for c in range(0,SPALTEN):
24         if sudoku[zeile][c] == n:
25           existiert = True
26           break
27
28       # Suche in zugewiesenen Positionen
29       for zugew in zugewiesene:
30         if zugew[0]==zeile and zugew[2] == n:
31           existiert = True
32           break
33         if zugew[1]==spalte and zugew[2]==n:
34           existiert = True
35           break
36 
37       if not existiert:
38         ergebnis.append(n)
39 
40     if ergebnis == []:
41       # Sackgasse
42       ergebnis = [-1]
43 
44     return ergebnis

Wie beschrieben landen die bereits ausgefüllten Kästchen in einem Stapel, deshalb durchsucht »test()« nicht nur das Sudoku-Feld, sondern fahndet auch in diesem Stapel nach bereits benutzten Zahlen. Die Funktion scannt zuerst die Zeile, dann die Spalte und zuletzt den Stapel. Jede Zahl, die in keiner der drei Positionen auftaucht, trägt die »test()«-Funktion in eine Liste ein, die sie am Ende zurückgibt.

Das Backtracking genannte Verfahren kommt zum Zuge, wenn »test()« eine leere Liste ausgibt, also keine freie Zahl gefunden hat. Damit ist der Lösungsversuch aber keineswegs beendet, der interessante Teil beginnt an dieser Stelle. Ein menschlicher Spieler versucht es gewöhnlich mit Ausprobieren und setzt hier und dort eine Zahl nach Augenmaß, wobei er sich zunächst die Kästchen vornimmt, die zumindest auf den ersten Blick weniger mögliche Lösungswerte zulassen. Das Beispielprogramm geht methodischer und mechanischer vor. Technisch gesprochen untersucht es den Raum aller Möglichkeiten.

In Anbetracht aller möglicher Kombinationen geht der Backtracking-Algorithmus sämtliche Möglichkeiten Schritt für Schritt durch. Das Beispiel testet dabei, wie weit es mit jeder Kombination kommt, und wenn es ohne mögliche Lösung steckenbleibt, geht es zurück bis zur letzten Verzweigung im Lösungsbaum und probiert es mit dem nächsten noch nicht getesteten Wert.

Für ein Kästchen stehen beispielsweise die Werte 1, 3 und 5 zur Auswahl. Zuerst probiert das Programm einen Lösungsweg mit der 1 und speichert die 3 und die 5. Gerät es in eine Sackgasse, geht es Schritt für Schritt zurück und wählt bei jedem Schritt die anderen gespeicherten Möglichkeiten.

Für das menschliche Gehirn erscheint dieses Vorgehen intuitiv, es in ein Computerprogramm umzusetzen ist jedoch nicht ganz so einfach. Es gibt dazu verschiedene Techniken und es bieten sich in jeder Variante an vielen Stellen Ansatzpunkte zur Optimierung.

Die erste Idee des Autors war eine rekursive Lösung, die aus einer Funktion besteht, die sich selbst aufruft. Dieser Weg käme zwar mit weniger Code aus, doch bei einem größeren Sudoku bleibt das Programm stecken, weil es den System-Stack überlastet. Das passiert, wenn viele Funktionen – eine innerhalb der anderen – aufgerufen werden: Hierbei träten möglicherweise hunderte oder tausende Aufrufe gleichzeitig auf, das Programm gäbe deshalb früher oder später einen Fehler aus. Ein anderer Ansatz liegt im Einsatz von Schleifen; das ist zwar weniger elegant, aber stabiler.

Zwei Stapel

Der Trick besteht ein Einsatz von zwei Stapeln. Stapel sind Datenstrukturen, die Informationen speichern und sie später mit einer Besonderheit wieder ausgeben: Das zuletzt abgelegte Element gibt ein in diesem Fall verwendeter Lifo-Stapel (last in, first out) als Erstes wieder aus. Genau wie bei einem Stapel Teller landet einer auf dem anderen und der Hausmann nimmt sie in umgekehrter Reihenfolge wieder von oben herunter. Stapel sind in fast allen Bereichen der Informatik essenziell.

Das Beispielprogramm verwendet zwei Stapel: einen zum Speichern der bisher durchprobierten Optionen – mit den ältesten unten und den neuesten oben – und einen, um die noch nicht getesten Möglichkeiten darin abzulegen. Gibt die Funktion »test()« in einer Position beispielsweise die Liste »[3,7,9]« – Wert 9 für die Koordinaten 3, 7 – zurück, enthalten die Stapel folgende Einträge:

>>> stapelAktuelle
[...[3,3,2],[3,4,3]]
>>> stapelMoegliche
[...[3,4,7],[3,4,9]]

Angenommen nach einer Serie von Fehlentscheidungen landet das Programm bei »[3,4,3]«, also dem Wert 3 für das Kästchen an Position 3, 4, und keine der möglichen Optionen im weiteren Lösungsbaum führt zu einer Lösung. Dann muss es die Auswahl »[3,4,3]« widerrufen und eine andere gespeicherte Möglichkeit wählen.

Dafür sorgt die Funktion »pop()«. Sie nimmt das letzte Element aus einer Liste:

>>> stapelAktuelle.pop()
[3,4,3]
>>> stapelAktuell
[...[3,3,2]]
>>> stapelAktuelle.append(stapelMoegliche.pop())
[...[3,3,2],[3,4,7]]
>>> stapelMoegliche
[...[3,4,9]]

Die Funktion entfernt gemäß dem Backtracking-Verfahren »[3,4,3]« aus »stapelAktuelle« und ersetzt es durch »[3,4,7]« aus »stapelMoegliche«. Listing 4 enthält den Code, der die Lösung sucht.

01 def loesen(sudoku):
02   MAXLINIEN = len(sudoku)
03   MAXSPALTEN = MAXLINIEN
04   # Beginne bei [0,0]
05   pos = Position(MAXLINIEN,MAXSPALTEN)
06   stapelAktuelle = []
07   stapelMoegliche = []
08   while not pos.ende():
09     moegliche = test(sudoku,stapelAktuelle,pos.getZeile(),pos.getSpalte())
10     while moegliche == []:
11       if pos.ende():
12         # Am Ende angekommen
13         drucken(sudoku,stapelAktuelle)
14         return True
15       pos.naechste()
16       moegliche = test(sudoku,stapelAktuelle,pos.getZeile(),pos.getSpalte())
17 
18     if moegliche == [-1]:
19       # Backtracking
20       zustand = stapelAktuelle.pop()
21       while zustand[0] != stapelMoegliche[-1][0]or zustand[1] != stapelMoegliche[-1][1]:
22         zustand = stapelAktuelle.pop()
23       # Jetzt haben die letzten Zustaende von beiden dieselbe Position
24       stapelAktuelle.append(stapelMoegliche.pop())
25       # Setzen der richtigen Position
26       pos.setZeile(stapelAktuelle[-1][0])
27       pos.setSpalte(stapelAktuelle[-1][1])
28 
29     else:
30       # Hier gibt es mehrere mögliche
31       # Nimmt die Erste mögliche Zahl und legt sie auf stapelAktuelle und den Rest auf stapelMoegliche
32       for moeglich in moegliche[1:]:
33         stapelMoegliche.append([pos.getZeile(),pos.getSpalte(),moeglich])
34 
35       stapelAktuelle.append([pos.getZeile(),pos.getSpalte(),moegliche[0]])
36 
37     pos.naechste()
38 
39 def existiert(sudoku, num, linie, spalte):
40   gefunden = False
41   for l in range(0,LINIEN):
42     if sudoku[l][spalte] == num:
43       gefunden = True
44 
45   for c in range(0,SPALTEN):
46     if sudoku[linie][c] == num:
47       gefunden = True
48   return gefunden

Funktion »loesen()«

Als Erstes ermittelt die Funktion »loesen()« die Größe des Sudoku-Felds und bereitet die beiden Stapel mit leeren Listen sowie einer Variablen, die die Position repräsentiert, vor. Dann startet sie in Zeile 8 die »while«-Schleife, die sie erst dann wieder verlässt, wenn das Rätsel gelöst ist.

Die Schleife sucht alle Zahlen, die in ein Kästchen passen. Wenn die Funktion »test()« eine leere Liste zurückgibt, geht alles einen Schritt weiter bis zur nächsten Position, denn die aktuelle ist bereits belegt. Diese Schleife spielt eine bedeutsame Rolle, weil in ihr eine Bedingung gestellt wird, die die Funktion vorzeitig beendet; das bewirkt das »return«-Statement in Zeile 14.

Gibt die Funktion »test()« die Liste »[-1]« zurück, kann »loesen()« keine Nummer auswählen und das Backtracking startet. Stehen dagegen mehrere mögliche Lösungswerte zur Auswahl, wählt die »else«-Konstruktion aus der Liste der möglichen Zahlen die erste aus und speichert sie in »stapelAktuelle« für den nächsten Schritt. Die anderen Zahlen legt sie unter »stapelMoegliche« mit der Position des Kästchens für den späteren Gebrauch ab – falls nötig. Dann geht es weiter zum nächsten Schritt. »pop()« liefert den letzten Zustand aus »stapelAktuell«, weil es an dieser Stelle nicht mehr weiterging.

Da die weiteren Möglichkeiten nach und nach in einem Stapel gelandet sind, befinden sich die zuletzt abgelegten am Ende des Stapels:

>>> stapelAktuell
[......[6,1,4],[6,2,8][6,3,9]]
>>> stapelMoegliche
[......[6,1,5]]

Wenn die Koordinaten der Zustände aus »stapelAktuell« wie in diesem Aufruf nicht mit denen aus »stapelMoegliche« übereinstimmen, gibt es weder Alternativen für »[6,2,8]« noch für »[6,3,9]«. Es bleibt als einzige Möglichkeit, die Zustände aus »stapelAktuell« Schritt für Schritt zu entfernen, bis einer mit den Koordinaten des letzten Zustands in »stapelMoegliche« übereinstimmt.

Das entspricht im Beispiel dem Voranschreiten bis zum Kästchen »[6,3]«, dann geht es zurück zu »[6,1]« – es folgt der Neubeginn von vorne. Nach dem Leeren des Stapels wird die Position auf »[6,1]« aktualisiert – es geht einen Schritt weiter zu den Koordinaten »[6,2]«.

Effizienz: Mangelhaft

Dieses komplexe Vorgehen führt zu einer automatischen Lösung des Rätsels. Der Schwachpunkt liegt jedoch in der Performance, denn das Abfragen der Spielräume von Lösungen läuft langsam ab. Der verwendete Testrechner mit einem 1600-MHz-Prozessor brauchte etwa zehn Minuten, um ein Sudoku zu lösen. Das liegt aber nicht nur am Algorithmus, auch Python ist nicht so effizient wie höhere Sprachen. Die Wikipedia-Seite zu Sudoku beschreibt aber effizientere Vorgehensweisen, die es unter gleichen Bedingungen in einem Fünftel der Zeit schaffen.

Das gezeigte Beispielprogramm ist also nicht auf Effizienz, sondern auf Einfachheit ausgelegt, getreu dem Satz des bekannten Informatikers Donald E. Knuth [2]: “Verfrühte Optimierung ist die Quelle allen Übels.” Ein simples und korrektes Programm lässt sich nachträglich immer noch optimieren. (csc)