Ein Sudoku kannst du auch von einem Computer lösen lassen. Am einfachsten geht das so: Du probierst in einem leeren Feld der Reihe nach Zahlen aus, und wenn du in einer Sackgasse landest, gehst du einen Schritt zurück und versuchst es anders. Diese Methode heißt Backtracking.

Die Idee hinter dem Backtracking

  1. Suche von links oben aus das erste leere Feld.
  2. Setze dort der Reihe nach 1 bis 9 ein. Steht dieselbe Zahl schon in der Zeile, Spalte oder im Block, überspringst du sie.
  3. Passt eine Zahl, trägst du sie ein und gehst zum nächsten leeren Feld.
  4. Kommst du zu einem Feld, in das keine Zahl passt, gehst du zum vorigen Feld zurück und probierst dort die nächste Zahl.
  5. Gibt es keine leeren Felder mehr, ist das Rätsel gelöst.

Wer von Hand löst, vermeidet blindes Raten. Ein Computer kann einen Fehler aber sofort zurücknehmen. Deshalb kommt er auch durch wildes Ausprobieren schnell ans Ziel.

In Python

Das Brett ist eine Liste mit 81 Zahlen, von links nach rechts und von oben nach unten (0 ist ein leeres Feld). Beim i-ten Feld ist der ganzzahlige Quotient von i÷9 die Zeile und der Rest die Spalte.

def can_place(grid, r, c, d):
    # d kann gesetzt werden, wenn es nicht in derselben Zeile, Spalte oder demselben Block steht
    for k in range(9):
        if grid[r * 9 + k] == d or grid[k * 9 + c] == d:
            return False
    br, bc = r // 3 * 3, c // 3 * 3
    for rr in range(br, br + 3):
        for cc in range(bc, bc + 3):
            if grid[rr * 9 + cc] == d:
                return False
    return True


def solve(grid):
    # Ein leeres Feld finden und 1 bis 9 der Reihe nach probieren. Bei einer Sackgasse zurückgehen
    for i in range(81):
        if grid[i] == 0:
            r, c = divmod(i, 9)
            for d in range(1, 10):
                if can_place(grid, r, c, d):
                    grid[i] = d
                    if solve(grid):
                        return True
                    grid[i] = 0
            return False
    return True


puzzle = "3..5..182.....2.9.8.2.91.4...52.9..6724.1.8396..4.85...5.12.9.7.3.7.....267..4..8"
grid = [0 if ch == "." else int(ch) for ch in puzzle]
solve(grid)
for r in range(9):
    print(" ".join(str(v) for v in grid[r * 9 : r * 9 + 9]))

Wenn du das Programm startest, erscheint die Lösung so. Das Rätsel ist eine ★1-Aufgabe der App NumberPlace.

3 4 9 5 6 7 1 8 2
5 1 6 8 4 2 7 9 3
8 7 2 3 9 1 6 4 5
1 8 5 2 3 9 4 7 6
7 2 4 6 1 5 8 3 9
6 9 3 4 7 8 5 2 1
4 5 8 1 2 3 9 6 7
9 3 1 7 8 6 2 5 4
2 6 7 9 5 4 3 1 8

Zählen, wie viele Lösungen es gibt

Wenn du Rätsel erstellst, willst du prüfen, ob es genau eine Lösung gibt (Warum ein Sudoku nur eine Lösung hat). Du änderst das Programm oben ein wenig: Es hört nach dem Fund einer Lösung nicht auf, sondern zählt weiter. Dann kennst du die Anzahl der Lösungen. Sobald zwei gefunden sind, steht fest, dass es nicht genau eine ist, und du brichst ab.

def count_solutions(grid, limit=2):
    # Anhalten, sobald limit Lösungen gefunden sind (bei 2 Funden ist klar: nicht genau eine)
    for i in range(81):
        if grid[i] == 0:
            r, c = divmod(i, 9)
            found = 0
            for d in range(1, 10):
                if can_place(grid, r, c, d):
                    grid[i] = d
                    found += count_solutions(grid, limit - found)
                    grid[i] = 0
                    if found >= limit:
                        break
            return found
    return 1


grid = [0 if ch == "." else int(ch) for ch in puzzle]
print(count_solutions(grid))

Beim ★1-Rätsel oben erscheint 1, bei einem Rätsel mit zwei Lösungen erscheint 2.

Tricks für mehr Tempo

Statt von links oben der Reihe nach vorzugehen, wird es viel schneller, wenn du mit dem Feld beginnst, in das die wenigsten Zahlen passen. Füllst du zuerst die Felder mit nur einem Kandidaten, musst du kaum noch zurückgehen. Auch die App NumberPlace probiert in dieser Reihenfolge, wenn sie die Zahl der Lösungen prüft.

Lösen mit denselben Techniken wie ein Mensch

Backtracking ist schnell und sicher, sagt dir aber nicht, „warum an dieser Stelle diese Zahl steht“. Für den „Tipp“ der App NumberPlace und für die Einschätzung der Schwierigkeit eines Rätsels nutzt die App ein anderes Verfahren.

  1. Zu jedem leeren Feld merkst du dir die Zahlen, die hineinpassen (die Kandidaten).
  2. Du suchst nach einer anwendbaren Technik, beginnend bei den einfachen.
  3. Nach einem Schritt suchst du wieder von der einfachsten Technik an.

Es gibt 15 Techniken, nach Schwierigkeit geordnet: von „Diese Zahl passt nur hierher“ und „Hier passt nur diese Zahl“ über Locked Candidates und Paare bis zum X-Wing, XY-Wing und Swordfish (So löst du Sudoku). Da das Verfahren in derselben Reihenfolge vorgeht wie ein Mensch, sieht man, welche Technik nötig war. So lassen sich die ★ festlegen, und der Tipp kann den Grund zeigen.