Valid Sudoku

Q: Wie findest du heraus, in welchem 3 × 3-Kasten sich eine Zelle befindet?

Bei ganzzahliger Division bezeichnet r / 3 den Zeilenblock (0, 1 oder 2) und c / 3 den Spaltenblock. (r / 3) * 3 + c / 3 nummeriert die Kästchen von 0 bis 8, von links nach rechts und von oben nach unten. Die Zelle (7, 1) liegt im Kästchen 2 * 3 + 0 = 6 , dem unten links.

MittelHashing

+10

Du erhältst ein 9 × 9-Sudoku-Brett als board, eine Liste aus 9 Zeichenfolgen mit jeweils 9 Zeichen, eine Zeichenfolge pro Zeile. Jedes Zeichen ist eine Ziffer von 1 bis 9 oder . für ein leeres Feld. Gib true zurück, wenn keine Ziffer in derselben Zeile, derselben Spalte oder demselben 3 × 3-Block zweimal 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 sich in keiner Zeile, Spalte oder keinem 3 × 3-Feld 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 Brett 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: Jede Zeile, jede Spalte und jeder Block enthält jede Ziffer höchstens einmal. Zeile 4 (ab 0 gezählt), .74..89.3, enthält die Ziffern 7, 4, 8, 9 und 3 jeweils einmal, und dasselbe gilt für die anderen 26 Gruppen. Daher lautet die Antwort true.

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. Die beiden Zellen befinden sich in unterschiedlichen Zeilen und unterschiedlichen Blöcken; nur die Spaltenprüfung erkennt diesen Fehler.

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 befinden sich in unterschiedlichen Zeilen und unterschiedlichen Spalten, aber beide liegen im Feld oben rechts, daher lautet die Antwort false.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Verallgemeinere die Prüfung auf ein 16 × 16-Brett mit 4 × 4-Blöcken und den Symbolen 1 bis 9 und A bis G. Welche Zahlen in deinem Code hängen von der Brettgröße ab, und wie lautet die Formel für die Blöcke?

Tipps

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

0 von 3 geöffnet

Lösung

Jede Ziffer gehört gleichzeitig zu drei Gruppen: ihrer Zeile, ihrer Spalte und ihrem 3 × 3-Block. Auf Zeilen und Spalten kann direkt zugegriffen werden; im Block entstehen die meisten Fehler. Nummeriere die Blöcke von 0 bis 8 mit (r / 3) * 3 + c / 3, und ein einziger Durchlauf über die 81 Zellen kann alle 27 Gruppen gemeinsam überprüfen.

Überprüfe jede Zeile, jede Spalte und jedes Kästchen einzeln.

Idee

Die Regeln nennen 27 Gruppen: 9 Zeilen, 9 Spalten und 9 Blöcke. Sammle die neun Zellen jeder Gruppe und prüfe, ob sich darunter eine Ziffer wiederholt; ignoriere dabei die Punkte. Wenn sich in keiner Gruppe eine Ziffer wiederholt, ist das Brett gültig.

Zeile i ist board[i][0..8] und Spalte i ist board[0..8][i]. Block i beginnt bei Zeile 3 * (i / 3) und Spalte 3 * (i % 3), wobei ganzzahlig dividiert wird; Block 5 beginnt also bei Zeile 3, Spalte 6. Seine Zelle k liegt von dieser Ecke aus k / 3 Zeilen weiter unten und k % 3 Spalten weiter rechts.

Um eine Wiederholung unter neun Zellen zu finden, behalte für jede Ziffer ein Kennzeichen dafür, ob sie bereits gesehen wurde, und brich beim ersten Kennzeichen ab, das bereits gesetzt ist. Jede der 81 Zellen wird dreimal gelesen, einmal für jede Gruppe, zu der sie gehört: 243 Lesezugriffe, ein fester Arbeitsaufwand. Bei einem n × n-Brett kostet dieselbe Methode O(n²).

Algorithmus

Für i von 0 bis 8 sammelst du Zeile i, Spalte i und Block i, jeweils mit neun Zellen.
Block i beginnt bei top = 3 * (i / 3) und left = 3 * (i % 3); seine Zelle k befindet sich in Zeile top + k / 3, Spalte left + k % 3.
Gehe für jede Gruppe ihre Zellen mit frisch gesetzten Markierungen durch und überspringe Punkte.
Wenn eine Ziffer bereits markiert ist, gib false zurück.
Gib nach allen 27 Gruppen true zurück.

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 bereits gesehener Werte pro Zeile, Spalte und Block

Idee

Anstatt Gruppen zusammenzutragen, besuchst du jede Zelle einmal und stellst alle drei Fragen gleichzeitig. Lege drei Tabellen mit 9 × 9 Markierungen an: seenRow[r][d] gibt an, dass die Ziffer d+1 bereits in Zeile r vorkommt; seenCol und seenBox funktionieren für Spalten und Blöcke genauso.

Die Zelle (r, c) gehört zum Block (r / 3) * 3 + c / 3. Der erste Teil wählt das Band aus drei Blöcken aus (die Zeilen 0 bis 2 ergeben Band 0, die Zeilen 3 bis 5 Band 1, die Zeilen 6 bis 8 Band 2), und c / 3 wählt den Block innerhalb des Bands aus. Die Zelle (4, 7) liegt in Block 1 * 3 + 2 = 5, dem mittleren rechten Block.

Prüfe für jede ausgefüllte Zelle, ob eine ihrer drei Markierungen bereits gesetzt ist. Wenn ja, wiederholt sich die Ziffer in dieser Gruppe, und du gibst sofort false zurück. Andernfalls setzt du alle drei Markierungen. Jede Zelle wird einmal gelesen und die Tabellen enthalten 243 Markierungen, daher sind Laufzeit und Speicherbedarf für ein 9 × 9-Brett konstant und für ein n × n-Brett O(n²).

Algorithmus

Erstelle seenRow, seenCol und seenBox, jeweils mit den Abmessungen 9 × 9 und ausschließlich mit false-Werten.
Durchlaufe jede Zelle (r, c); überspringe sie, wenn sie einen Punkt enthält.
Sei d die Ziffer minus 1 und b = (r / 3) * 3 + c / 3.
Wenn seenRow[r][d], seenCol[c][d] oder seenBox[b][d] true ist, gib false zurück.
Setze andernfalls alle drei auf true. 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

Die Prüfungen von Zeilen und Spalten gehen selten schief. Die Fehler liegen beim Box-Index und bei der Frage, was als Wiederholung zählt.

Die Box als r / 3 + c / 3 berechnen. Das ergibt nur Werte von 0 bis 4, sodass die Zellen (0, 3) und (3, 0) dieselbe Zahl erhalten, obwohl sie in verschiedenen Boxen liegen, und zwei 7er dort als Wiederholung gemeldet werden. Verwende (r / 3) * 3 + c / 3.
In JavaScript, Python 3 oder Lua mit / dividieren, wo 4 / 3 1.33 ergibt und keine Boxnummer. Verwende Math.floor, // oder math.floor.
. als Wert behandeln. Ein leeres Spielfeld hat in jeder Zeile neun Punkte und ist gültig.
Versuchen, das Rätsel zu lösen. Mit 12345678. als Zeile 0 und einer 9 weiter unten in Spalte 8 kann die letzte Zelle von Zeile 0 niemals ausgefüllt werden, doch keine Gruppe wiederholt eine Ziffer, also lautet die Antwort true.
Zeilen und Spalten prüfen, aber nicht die Boxen. Ein vollständiges Gitter, in dem jede Zeile gegenüber der vorherigen um eine Stelle nach links verschoben ist, enthält keine Wiederholung in einer Zeile oder Spalte, während jede Box Wiederholungen enthält.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Valid Sudoku?

Das Spielfeld hat immer 81 Zellen, daher benötigen beide Ansätze O(1) Zeit und O(1) Speicher. Bei einem allgemeinen n × n-Sudoku liest die Prüfung in einem Durchlauf jede der n² Zellen einmal und speichert 3n² Markierungen. Daher beträgt der Zeit- und Speicherbedarf O(n²).

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

Nein. „Gültig“ bedeutet hier nur, dass sich unter den bereits ausgefüllten Zellen keine Ziffer in einer Zeile, einer Spalte oder einem 3 × 3-Feld wiederholt. Ein Sudoku 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.

Wie findest du heraus, in welchem 3 × 3-Kasten sich eine Zelle befindet?

Bei ganzzahliger Division bezeichnet r / 3 den Zeilenblock (0, 1 oder 2) und c / 3 den Spaltenblock. (r / 3) * 3 + c / 3 nummeriert die Kästchen von 0 bis 8, von links nach rechts und von oben nach unten. Die Zelle (7, 1) liegt im Kästchen 2 * 3 + 0 = 6, dem unten links.

Kann man Valid Sudoku mit Bitmasken lösen?

Ja. Weise jeder Zeile, Spalte und jedem Block eine Ganzzahl zu, und lass Bit d bedeuten, dass die Ziffer d+1 bereits vorkam. Berechne für eine ausgefüllte Zelle 1 << d; ergibt eine bitweise UND-Verknüpfung mit einer der drei Masken einen Wert ungleich null, kommt die Ziffer doppelt vor, andernfalls verknüpfst du sie bitweise mit allen drei Masken durch ODER. Das sind 27 Ganzzahlen statt 243 Flags bei derselben Logik in einem Durchlauf.

Python

def isValidSudoku(board):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

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

Erwartet

true