· 

Sudoku Checker!

1. Problem

Beim Valid Sudoku Problem von LeetCode geht es darum, eine Funktion zu schreiben, die ein eingegebenes Sudoku auf seine Richtigkeit überprüft. Was ist ein Sudoku?

Bei einem Sudoku handelt es sich um ein Zahlenrätsel aus Japan. Es werden (im klassischen Sudoku) die Zahlen von 1 bis 9 so in eine 9x9 Matrix eingetragen, dass in jeder Zeile, jeder Spalte und jeder 3x3-Matrix, von denen es insgesamt 9 Stück gibt, jede Zahl nur genau einmal vorkommt.

Die Spielregeln lauten also:

  • Jede der Zahlen 1 bis 9 kommt genau einmal in jeder Zeile vor.
  • Jede der Zahlen 1 bis 9 kommt genau einmal in jeder Spalte vor.
  • Jede der Zahlen 1 bis 9 kommt genau einmal in jeder der 9 Boxen vor.

Du sollst nun für eine eingegebenes Sudoku überprüfen, ob es valide ist, d. h. es werden alle Regeln erfüllt. Je nach Programmiersprache kann man ein Sudoku als zweidimensionales Array oder eine Liste aus Listen darstellen. Da wir das Problem in der Programmiersprache Python lösen werden, gehen wir von einer Liste bestehend aus Listen aus.


2. Lösung

Die vorgegebene Methodensignatur enthält als Parameter ein board, das eine Liste aus Listen von Strings darstellt. Die Methode gibt einen Boolean-Wert zurück, d. h. als Ergebnis wird einfach nur festgestellt "das eingegebene Board ist ein valides Sudoku" oder "das eingegebene Board ist kein ein valides Sudoku"

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:

Das Sudoku muss übrigens nicht schon vollständig gelöst sein. Überall dort, wo kein Eintrag zu finden sein soll, steht ein ".". Als Eingabe erhält die Funktion z. B. 

[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]

und liefert True zurück, weil dieses Sudoku alle Regeln erfüllt. Dieses Sudoku

[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]

ist hingegen fehlerhaft, weil in der ersten Spalte die Zahl 8 zweimal vorkommt. Deshalb wird False zurückgegeben.

Wie geht man nun bei der Implementierung vor? Dass wir das gesamte Sudoku durchlaufen müssen, ist klar, d. h. wir können schon einmal zwei ineinander verschachtelte for-Schleifen mit einem Index i (für die Zeilen) und einem Index j (für die Spalten), die jeweils von 0 bis (exklusive) 9 laufen, aufschreiben:

def isValidSudoku(self, board: List[List[str]]) -> bool:
   for i in range(0, 9):
      for j in range(0,9):

Den Startindex 0 könnte man auch weglassen, weil dann automatisch 0 als erster Wert genommen wird. Wir lesen nun die Zahl in der i-ten Zeile und der j-ten Spalte aus. Was machen wir jetzt? Wir überlegen uns, wie wir geschickt entscheiden können, ob wir die aktuell betrachtete Zahl schon einmal in einer Zeile, einer Spalte oder eine der Boxen gesehen haben. Wir müssen diese Information also irgendwie zwischenspeichern. Dafür bietet sich ein Set an, da es keine Duplikate enthält und in einigen Programmiersprachen (wie z. B. Java) dafür Methoden vorhanden sind, die vor dem Hinzufügen eines neuen Elements erstmal überprüfen, ob dieses schon vorhanden ist (in diesem Fall wird dann der Wert False zurückgegeben). In Python können wir dafür auch ein Set verwenden.

def isValidSudoku(self, board: List[List[str]]) -> bool:
   found = set()
   for i in range(0, 9):
      for j in range(0,9):

In dieses Set speichern wir nun Strings, die angeben, welches Element wir in welcher Reihe, welcher Spalte und welcher Box schon einmal gesehen haben. Natürlich müssen wir nur Elemente berücksichtigen, die nicht dem Platzhalter "." für ein leeres Feld entsprechen. 

  • Der String für die Zeilen setzt sich z. B. aus dem Wort "row", dem Index der Zeile "i" und dem aktuell ausgelesenen Wert zusammen.
  • Der String für die Spalten setzt sich z. B. aus dem Wort "col", dem Index der Spalte "j" und dem aktuell ausgelesenen Wert zusammen. Braucht man die Information, ob man sich in einer Zeile oder einer Spalte befindet? Ja, da sonst jeweils nur ein Index mit einem Wert vorhanden wäre, wodurch es zu Dopplungen kommen kann, die gar nicht im Sudoku vorhanden sind, z. B. wenn Zeile 2 eine 3 und Spalte 2 ebenfalls eine 3 enthält.
  • Der String für die Boxen setzt sich (optional) aus dem Keyword box, den Maßen der Box und dem aktuell ausgelesenen Wert zusammen. Wie kommt man auf die Maße der Box? Ganz einfach! Da es sich um 3x3-Boxen in einem 9x9-Sudoku handelt, führt man eine ganzzahlige Division der aktuellen Zeile und Spalte durch 3 durch. Wichtig: eine ganzzahlige Division, damit 1/3 und 2/3 dasselbe Ergebnis (0) liefern!
class Solution:
   def isValidSudoku(self, board: List[List[str]]) -> bool:
      found = []
      for i in range(9):
         for j in range(9):
            value = board[i][j]
            if value != ".":
               row = f"row-{i}-{value}"
               col = f"col-{j}-{value}"
               box = f"box-{i//3}-{j//3}-{value}"

Wenn entweder der String für die Zeile, der für die Spalte oder der für die Box im Set vorhanden sind, wird False zurückgegeben und es muss nicht weitergetestet werden, da bereits (mindestens) eine der Regeln verletzt wurde.

class Solution:
   def isValidSudoku(self, board: List[List[str]]) -> bool:
      found = []
      for i in range(9):
         for j in range(9):
            value = board[i][j]
            if value != ".":
               row = f"row-{i}-{value}"
               col = f"col-{j}-{value}"
               box = f"box-{i//3}-{j//3}-{value}"
               if row in found or col in found or box in found:
                  return False

Ansonsten fügst du die soeben erstellten Strings dem Set hinzu.

class Solution:
   def isValidSudoku(self, board: List[List[str]]) -> bool:
      found = []
      for i in range(9):
         for j in range(9):
            value = board[i][j]
            if value != ".":
               row = f"row-{i}-{value}"
               col = f"col-{j}-{value}"
               box = f"box-{i//3}-{j//3}-{value}"
               if row in found or col in found or box in found:
                  return False
               else:
                  found.add(row)
                  found.add(col)
                  found.add(box)

Ganz zum Schluss der doppelten for-Schleife wird True zurückgegeben, da keine Regel verletzt wurde.

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        found = set()
        for i in range(0, 9):
            for j in range(0,9):
                value = board[i][j]
                if value != ".":
                    row = f"row-{i}-{value}"
                    col = f"col-{j}-{value}"
                    box = f"box-{i//3}-{j//3}-{value}"
                    if row in found or col in found or box in found:
                        return False
                    else:
                        found.add(row)
                        found.add(col)
                        found.add(box)
        return True