Valid Sudoku

Q: Jak ustalić, w którym polu 3 × 3 znajduje się komórka?

Przy dzieleniu całkowitym r / 3 określa pas wierszy (0, 1 lub 2), a c / 3 — stos kolumn. (r / 3) * 3 + c / 3 numeruje pola od 0 do 8, od lewej do prawej i z góry na dół. Komórka (7, 1) znajduje się w polu 2 * 3 + 0 = 6 , tym w lewym dolnym rogu.

ŚrednieHaszowanie

+10

Otrzymujesz planszę Sudoku 9 × 9 jako board, listę 9 ciągów znaków, każdy o długości 9 znaków, po jednym ciągu na wiersz. Każdy znak to cyfra od 1 do 9 albo . oznaczająca puste pole. Zwróć true, jeśli żadna cyfra nie występuje dwukrotnie w tym samym wierszu, tej samej kolumnie ani w tym samym polu 3 × 3, a w przeciwnym razie false. Sprawdzane są tylko wypełnione pola: plansza nie musi mieć rozwiązania.

Funkcja

isValidSudoku(board: string-array) → boolean

boardstring-array: 9 ciągów po 9 znaków, po jednym w każdym wierszu, cyfry od 1 do 9 i . oznaczająca pustą komórkę
Zwracaboolean: true, jeśli żaden wiersz, kolumna ani kwadrat 3 × 3 nie zawiera powtórzonej cyfry; w przeciwnym razie false

Ograniczenia

board.length == 9 oraz board[i].length == 9
board[i][j] to cyfra od 1 do 9 lub .
Ukończenie planszy może być niemożliwe; liczą się tylko powtórzenia wśród wypełnionych pól.

Przykłady

Wejście: board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
Wyjście: true
Wyjaśnienie: Każdy wiersz, każda kolumna i każde pole zawiera każdą cyfrę najwyżej raz. Wiersz 4 (licząc od 0), .74..89.3, zawiera po jednym wystąpieniu cyfr 7, 4, 8, 9 i 3. To samo dotyczy pozostałych 26 grup, więc odpowiedź to true.

Wejście: board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
Wyjście: false
Wyjaśnienie: Zarówno wiersz 0, jak i wiersz 7 zaczynają się od 3, więc w kolumnie 0 znajdują się dwie trójki. Te dwie komórki są w różnych wierszach i różnych polach; tylko sprawdzenie kolumny wykrywa ten przypadek.

Wejście: 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"]
Wyjście: false
Wyjaśnienie: 5 w wierszu 0, kolumnie 8 i 5 w wierszu 2, kolumnie 7 znajdują się w różnych wierszach i różnych kolumnach, ale obie są w prawym górnym polu, więc odpowiedzią jest false.

+16 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Uogólnij sprawdzanie dla planszy 16 × 16 z kwadratami 4 × 4 i symbolami od 1 do 9 oraz od A do G. Które liczby w Twoim kodzie zależą od rozmiaru planszy i jak będzie wyglądał wzór na kwadrat?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Każda cyfra należy jednocześnie do trzech grup: swojego wiersza, swojej kolumny i swojego pola 3 × 3. Wiersze i kolumny można indeksować bezpośrednio; to pole jest źródłem większości błędów. Ponumeruj pola od 0 do 8 za pomocą (r / 3) * 3 + c / 3, a jedno przejście po 81 komórkach pozwoli sprawdzić wszystkie 27 grup jednocześnie.

Sprawdź osobno każdy wiersz, każdą kolumnę i każde pole

Intuicja

Reguły określają 27 grup: 9 wierszy, 9 kolumn i 9 kwadratów. Zbierz dziewięć komórek z każdej grupy i sprawdź, czy któraś cyfra się w nich powtarza, ignorując kropki. Jeśli w żadnej grupie nie ma powtórzeń, plansza jest poprawna.

Wiersz i to board[i][0..8], a kolumna i to board[0..8][i]. Kwadrat i zaczyna się w wierszu 3 * (i / 3) i kolumnie 3 * (i % 3), przy czym używane jest dzielenie całkowite, więc kwadrat 5 zaczyna się w wierszu 3, kolumnie 6. Jego komórka k znajduje się k / 3 wierszy poniżej i k % 3 kolumn na prawo od tego narożnika.

Aby znaleźć powtórzenie wśród dziewięciu komórek, przechowuj flagę obecności dla każdej cyfry i zatrzymaj się przy pierwszej cyfrze, która ma już ustawioną flagę. Każda z 81 komórek jest odczytywana trzy razy, po jednym razie dla każdej grupy, do której należy: 243 odczyty, stała ilość pracy. Na planszy n × n ta sama metoda wymaga O(n²).

Algorytm

Dla i od 0 do 8 zbierz wiersz i, kolumnę i i blok i, po dziewięć komórek w każdym.
Blok i zaczyna się w top = 3 * (i / 3) i left = 3 * (i % 3); jego komórka k znajduje się w wierszu top + k / 3, kolumnie left + k % 3.
Dla każdej grupy przejdź przez jej komórki, używając nowych znaczników „widziano”, pomijając kropki.
Jeśli cyfra jest już oznaczona, zwróć false.
Po przejściu przez wszystkie 27 grup zwróć true.

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

Jedno przejście z tabelą odwiedzonych pól dla każdego wiersza, kolumny i bloku

Intuicja

Zamiast zbierać grupy, odwiedź każdą komórkę raz i zadaj wszystkie trzy pytania jednocześnie. Użyj trzech tabel flag o rozmiarze 9 × 9: seenRow[r][d] oznacza, że cyfra d+1 znajduje się już w wierszu r, a seenCol i seenBox działają tak samo dla kolumn i kwadratów.

Komórka (r, c) należy do kwadratu (r / 3) * 3 + c / 3. Pierwsza część wskazuje pas trzech kwadratów (wiersze od 0 do 2 dają pas 0, wiersze od 3 do 5 — pas 1, a wiersze od 6 do 8 — pas 2), a c / 3 wskazuje kwadrat w tym pasie. Komórka (4, 7) trafia do kwadratu 1 * 3 + 2 = 5, czyli środkowego prawego kwadratu.

Dla każdej wypełnionej komórki, jeśli któraś z jej trzech flag jest już ustawiona, cyfra powtarza się w tej grupie i od razu zwracasz false. W przeciwnym razie ustawiasz wszystkie trzy flagi. Każda komórka jest odczytywana raz, a tabele przechowują 243 flagi, więc czas i pamięć są stałe dla planszy 9 × 9, a dla planszy n × n wynoszą O(n²).

Algorytm

Utwórz seenRow, seenCol i seenBox, każde o wymiarach 9 × 9 i wypełnione wartościami false.
Odwiedź każdą komórkę (r, c); pomiń ją, jeśli zawiera kropkę.
Niech d będzie cyfrą pomniejszoną o 1, a b = (r / 3) * 3 + c / 3.
Jeśli seenRow[r][d], seenCol[c][d] lub seenBox[b][d] ma wartość true, zwróć false.
W przeciwnym razie ustaw wszystkie trzy na true. Po ostatniej komórce zwróć true.

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

Pułapki i przypadki brzegowe

Kontrola wierszy i kolumn rzadko zawodzi. Błędy dotyczą indeksu kwadratu oraz tego, co uznaje się za powtórzenie.

Obliczanie kwadratu jako r / 3 + c / 3. Daje to wartości tylko od 0 do 4, więc komórki (0, 3) i (3, 0) mają ten sam numer, choć znajdują się w różnych kwadratach, a dwie 7 w tych miejscach zostaną uznane za powtórzenie. Użyj (r / 3) * 3 + c / 3.
Dzielenie za pomocą / w JavaScript, Python 3 lub Lua, gdzie 4 / 3 daje 1.33, a nie numer kwadratu. Użyj Math.floor, // lub math.floor.
Traktowanie . jako wartości. Pusta plansza ma w każdym wierszu dziewięć kropek i jest poprawna.
Próba rozwiązania łamigłówki. Jeśli wiersz 0 to 12345678., a niżej w kolumnie 8 znajduje się 9, ostatniej komórki wiersza 0 nie da się wypełnić, ale żadna grupa nie zawiera powtarzających się cyfr, więc odpowiedzią jest true.
Sprawdzanie wierszy i kolumn, ale nie kwadratów. Pełna plansza, w której każdy wiersz jest przesunięty o jedno miejsce w lewo względem poprzedniego, nie zawiera powtórzeń w żadnym wierszu ani kolumnie, ale w każdym kwadracie są powtórzenia.

Najczęstsze pytania4

Jaka jest złożoność czasowa rozwiązania poprawnego Sudoku?

Plansza zawsze ma 81 pól, więc oba podejścia działają w czasie O(1) i zużywają O(1) pamięci. W przypadku ogólnego Sudoku n × n kontrola w jednym przebiegu odczytuje każde z n² pól raz i przechowuje 3n² flag, więc jej złożoność czasowa i pamięciowa wynosi O(n²).

Czy poprawna plansza Sudoku musi być rozwiązywalna?

Nie. Tutaj „poprawne” oznacza jedynie, że żadna cyfra nie powtarza się w wierszu, kolumnie ani kwadracie 3 × 3 wśród już wypełnionych komórek. Plansza może przejść tę kontrolę i nadal nie mieć rozwiązania. Ustalenie, czy da się ją rozwiązać, wymaga wyszukiwania, na przykład z nawrotami, a to już inny problem.

Jak ustalić, w którym polu 3 × 3 znajduje się komórka?

Przy dzieleniu całkowitym r / 3 określa pas wierszy (0, 1 lub 2), a c / 3 — stos kolumn. (r / 3) * 3 + c / 3 numeruje pola od 0 do 8, od lewej do prawej i z góry na dół. Komórka (7, 1) znajduje się w polu 2 * 3 + 0 = 6, tym w lewym dolnym rogu.

Czy można rozwiązać Valid Sudoku za pomocą masek bitowych?

Tak. Przypisz każdemu wierszowi, kolumnie i blokowi jedną liczbę całkowitą i przyjmij, że bit d oznacza, że cyfra d+1 została już napotkana. Dla wypełnionej komórki oblicz 1 << d; jeśli wynik operacji AND z dowolną z trzech masek jest niezerowy, cyfra się powtarza, w przeciwnym razie wykonaj operację OR i zapisz wynik we wszystkich trzech maskach. To 27 liczb całkowitych zamiast 243 flag, przy tej samej logice jednego przebiegu.

Python

def isValidSudoku(board):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

true