Valid Sudoku

+10

Du erhältst ein 9 × 9-Sudoku-Brett als board, eine Liste aus 9 Zeichenketten mit jeweils 9 Zeichen, eine Zeichenkette pro Zeile. Jedes Zeichen ist eine Ziffer von 1 bis 9 oder . für ein leeres Feld. Gib true zurück, wenn keine Ziffer zweimal in einer Zeile, einer Spalte oder einem 3 × 3-Block vorkommt, und andernfalls false. Es werden nur die ausgefüllten Felder überprüft: Das Brett muss nicht lösbar sein.

Funktion

isValidSudoku(board: string-array) → boolean

boardstring-array: 9 Zeichenfolgen mit je 9 Zeichen, eine pro Zeile, Ziffern von 1 bis 9 und . für ein leeres Feld
Gibt zurückboolean: wahr, wenn keine Zeile, Spalte oder 3 × 3-Box eine Ziffer wiederholt, andernfalls falsch

Einschränkungen

board.length == 9 und board[i].length == 9
board[i][j] ist eine Ziffer von 1 bis 9 oder .
Das Spielfeld lässt sich möglicherweise nicht vervollständigen; relevant sind nur Wiederholungen unter den ausgefüllten Zellen.

Beispiele

Eingabe: board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
Ausgabe: true
Erklärung: Zeile 4, von 0 an gezählt, .74..89.3, enthält die Ziffern 7, 4, 8, 9 und 3 jeweils einmal, und auch keine der anderen 26 Gruppen enthält eine Ziffer doppelt.

Eingabe: board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
Ausgabe: false
Erklärung: Zeile 0 und Zeile 7 beginnen beide mit einer 3, daher enthält Spalte 0 zwei 3en. Sie teilen sich weder eine Zeile noch einen Block, daher wird der Konflikt nur bei der Spaltenprüfung erkannt.

Eingabe: board = ["987..36.5", "2.6.8..13", ".1.64.75.", "8..261..4", "16.97.3.8", "..9.5..6.", "7.....49.", "..48.....", "5.1.....7"]
Ausgabe: false
Erklärung: Die 5 in Zeile 0, Spalte 8 und die 5 in Zeile 2, Spalte 7 haben weder eine Zeile noch eine Spalte gemeinsam, befinden sich aber beide im Feld oben rechts. Daher lautet die Antwort false.

Weiterführende Frage

Wie würdest du ein 16 × 16-Spielfeld mit 4 × 4-Blöcken und den Symbolen 1 bis 9 und A bis G überprüfen? Wie lautet die Formel für die Blöcke dann?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Jede Ziffer gehört zu drei Gruppen: ihrer Zeile, ihrer Spalte und ihrem 3 × 3-Block. Zeilen und Spalten lassen sich direkt indizieren; im Block stecken die Tücken. Nummeriere die Blöcke von 0 bis 8 mit (r / 3) * 3 + c / 3, und ein Durchlauf über die 81 Zellen prüft alle 27 Gruppen.

Prüfe jede Zeile, jede Spalte und jeden Kasten einzeln

Idee

Die Regel benennt 27 Gruppen: 9 Zeilen, 9 Spalten und 9 Blöcke. Sammle die neun Zellen jeder Gruppe und suche nach einer wiederholten Ziffer; Punkte werden ignoriert. Das Brett ist genau dann gültig, wenn keine Gruppe eine Wiederholung enthält.

Ein Merker pro Ziffer findet eine Wiederholung unter neun Zellen. Jede der 81 Zellen wird einmal für jede ihrer drei Gruppen gelesen: 243 Lesezugriffe, ein fester Arbeitsaufwand. Auf einem n × n-Brett benötigt dieselbe Methode O(n²).

Algorithmus

Für i von 0 bis 8 die Zeile i, die Spalte i und den Block i erfassen.
Der Block i hat seine Ecke in Zeile 3 * (i / 3), Spalte 3 * (i % 3); seine Zelle k liegt k / 3 Zeilen darunter und k % 3 Spalten rechts davon.
Jede Gruppe mit frisch zurückgesetzten Merker-Flags durchlaufen und Punkte überspringen. Wenn eine Ziffer bereits markiert ist, false zurückgeben.
Nach allen 27 Gruppen true zurückgeben.

def has_repeat(cells):
    seen = set()
    for ch in cells:
        if ch == '.':
            continue
        if ch in seen:
            return True
        seen.add(ch)
    return False


def isValidSudoku(board):
    for r in range(9):
        if has_repeat(board[r][c] for c in range(9)):
            return False
    for c in range(9):
        if has_repeat(board[r][c] for r in range(9)):
            return False
    for top in (0, 3, 6):
        for left in (0, 3, 6):
            box = (board[top + i][left + j] for i in range(3) for j in range(3))
            if has_repeat(box):
                return False
    return True

Ein Durchlauf mit einer Tabelle für bereits gesehene Werte pro Zeile, Spalte und Block

Idee

Gehe jede Zelle einmal durch und stelle alle drei Fragen zusammen. Verwende drei 9 × 9-Tabellen mit Markierungen: seenRow[r][d] bedeutet, dass die Ziffer d+1 bereits in Zeile r vorkommt; seenCol und seenBox funktionieren genauso.

Die Zelle (r, c) gehört zum Block (r / 3) * 3 + c / 3. Der erste Teil bestimmt den Streifen aus drei Blöcken, und c / 3 bestimmt den Block innerhalb des Streifens. Die Zelle (4, 7) liegt im Block 1 * 3 + 2 = 5, dem mittleren rechten Block.

Eine bereits gesetzte Markierung bedeutet, dass sich die Ziffer in dieser Gruppe wiederholt. Jede Zelle wird einmal gelesen, und die Tabellen enthalten 243 Markierungen: hier feste Laufzeit und fester Speicherbedarf, O(n²) auf einem n × n-Spielfeld.

Algorithmus

Erstelle seenRow, seenCol und seenBox, jeweils mit den Maßen 9 × 9 und ausschließlich false.
Für jede ausgefüllte Zelle (r, c) sei d ihre Ziffer minus 1 und b = (r / 3) * 3 + c / 3.
Falls seenRow[r][d], seenCol[c][d] oder seenBox[b][d] gesetzt ist, gib false zurück; andernfalls setze alle drei.
Gib nach der letzten Zelle true zurück.

def isValidSudoku(board):
    # seen_row[r][d] is True once digit d + 1 appears in row r; same for columns and boxes.
    seen_row = [[False] * 9 for _ in range(9)]
    seen_col = [[False] * 9 for _ in range(9)]
    seen_box = [[False] * 9 for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == '.':
                continue
            d = int(ch) - 1
            b = (r // 3) * 3 + c // 3
            if seen_row[r][d] or seen_col[c][d] or seen_box[b][d]:
                return False
            seen_row[r][d] = seen_col[c][d] = seen_box[b][d] = True
    return True

Stolperfallen und Grenzfälle

Den Block als r / 3 + c / 3 berechnen. Das ergibt nur Werte von 0 bis 4, sodass (0, 3) und (3, 0) dieselbe Zahl erhalten, obwohl sie zu unterschiedlichen Blöcken gehören, und zwei 7er dort als Wiederholung gemeldet werden.
Durch / in JavaScript, Python 3 oder Lua teilen, wo 4 / 3 1.33 ergibt. Abrunden.
. als Wert behandeln. Ein leeres Spielfeld mit neun Punkten pro Zeile ist gültig.
Versuchen, das Rätsel zu lösen. Eine Zeile 0 mit 12345678., in der weiter unten in Spalte 8 eine 9 steht, kann niemals vervollständigt werden, dennoch wiederholt sich nichts: true.
Die Blöcke überspringen. Ein vollständiges Gitter, bei dem jede Zeile gegenüber der darüberliegenden um eine Stelle nach links verschoben ist, weist weder in einer Zeile noch in einer Spalte Wiederholungen auf, während jeder Block Wiederholungen enthält.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Valid Sudoku?

Das Brett hat immer 81 Zellen, daher laufen beide Ansätze in O(1)-Zeit und benötigen O(1)-Speicher. Bei einem allgemeinen n × n-Sudoku liest die Prüfung in einem Durchlauf jede der n² Zellen genau einmal und speichert 3n² Flags: O(n²)-Zeit und -Speicher.

Muss ein gültiges Sudoku-Brett lösbar sein?

Nein. Gültig bedeutet hier nur, dass sich unter den ausgefüllten Zellen keine Ziffer in einer Zeile, einer Spalte oder einem 3 × 3-Feld wiederholt. Ein Spielfeld kann diese Prüfung bestehen und trotzdem keine Lösung haben. Um festzustellen, ob es lösbar ist, braucht man eine Suche wie Backtracking – das ist ein anderes Problem.

Kann gültiges Sudoku mit Bitmasken gelöst werden?

Ja. Gib jeder Zeile, jeder Spalte und jedem Block eine Ganzzahl, wobei das Bit d bedeutet, dass die Ziffer d+1 bereits vorkam. Wenn bei einem ausgefüllten Feld 1 << d mit einer der drei Masken per AND einen Wert ungleich null ergibt, kommt die Ziffer doppelt vor; andernfalls führst du in allen drei Masken ein OR damit aus. Das sind 27 Ganzzahlen statt 243 Flags.

def isValidSudoku(board):
    # Schreibe hier Code

Test #1

Test #2

Test #3

Argument

board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]

Erwartete Ausgabe

true