Valid Sudoku

+10

Otrzymujesz planszę Sudoku 9 × 9 jako board, listę 9 ciągów znaków, z których każdy ma 9 znaków, po jednym ciągu na każdy wiersz. Każdy znak to cyfra od 1 do 9 albo . oznaczająca pustą komórkę. Zwróć true, jeśli żadna cyfra nie występuje dwukrotnie w wierszu, kolumnie ani kwadracie 3 × 3, a w przeciwnym razie zwróć false. Sprawdzane są tylko wypełnione komórki: 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 puste pole
Zwracaboolean: true, jeśli żadna cyfra nie powtarza się w wierszu, kolumnie ani polu 3 × 3; w przeciwnym razie false

Ograniczenia

board.length == 9 oraz board[i].length == 9
board[i][j] to cyfra od 1 do 9 lub .
Plansza może być niemożliwa do ukończenia; 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: Wiersz 4, licząc od 0, .74..89.3, zawiera po jednym wystąpieniu cyfr 7, 4, 8, 9 i 3, a żadna z pozostałych 26 grup również nie powtarza żadnej cyfry.

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: Wiersz 0 i wiersz 7 zaczynają się od 3, więc w kolumnie 0 znajdują się dwie trójki. Nie mają wspólnego wiersza ani bloku, więc tylko sprawdzenie kolumny to wykrywa.

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 nie znajdują się w tym samym wierszu ani kolumnie, ale oba znajdują się w prawym górnym polu, więc odpowiedź to false.

Pytanie dodatkowe

Jak sprawdzić planszę 16 × 16 z polami 4 × 4 i symbolami od 1 do 9 oraz od A do G? Jak będzie wyglądał wzór na pole?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Każda cyfra należy do trzech grup: swojego wiersza, swojej kolumny i swojego kwadratu 3 × 3. Wiersze i kolumny można indeksować bezpośrednio; problemy pojawiają się przy kwadratach. Ponumeruj kwadraty od 0 do 8 za pomocą (r / 3) * 3 + c / 3, a jedno przejście przez 81 komórek sprawdzi wszystkie 27 grup.

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

Intuicja

Reguła określa 27 grup: 9 wierszy, 9 kolumn i 9 bloków. Zbierz dziewięć komórek z każdej grupy i poszukaj powtórzonej cyfry, ignorując kropki. Plansza jest poprawna wtedy i tylko wtedy, gdy żadna grupa jej nie zawiera.

Flaga informująca o wystąpieniu każdej cyfry pozwala znaleźć powtórzenie wśród dziewięciu komórek. Każda z 81 komórek jest odczytywana raz dla każdej z trzech grup, do których należy: 243 odczyty, czyli stała liczba operacji. Na planszy n × n ta sama metoda ma koszt O(n²).

Algorytm

Dla i od 0 do 8 zbierz wiersz i, kolumnę i i kwadrat i.
Kwadrat i ma róg w wierszu 3 * (i / 3), kolumnie 3 * (i % 3); jego komórka k znajduje się o k / 3 wierszy niżej i o k % 3 kolumn w prawo.
Przejdź przez każdą grupę, używając nowych flag oznaczających widziane cyfry i pomijając kropki. Jeśli cyfra jest już oznaczona flagą, zwróć false.
Po sprawdzeniu wszystkich 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 tablicą odwiedzonych elementów dla każdego wiersza, kolumny i bloku

Intuicja

Odwiedź każdą komórkę raz i zadaj wszystkie trzy pytania jednocześnie. Używaj trzech tablic 9 × 9 z flagami: seenRow[r][d] oznacza, że cyfra d+1 znajduje się już w wierszu r, a seenCol i seenBox działają tak samo.

Komórka (r, c) należy do pudełka (r / 3) * 3 + c / 3. Pierwsza część wskazuje pas trzech pudełek, a c / 3 wskazuje pudełko w tym pasie. Komórka (4, 7) znajduje się w pudełku 1 * 3 + 2 = 5, czyli w środkowym pudełku po prawej.

Już ustawiona flaga oznacza, że cyfra powtarza się w tej grupie. Każda komórka jest odczytywana raz, a tablice przechowują 243 flagi: stały czas i ilość pamięci w tym przypadku, O(n²) na planszy n × n.

Algorytm

Utwórz seenRow, seenCol i seenBox, każde o rozmiarze 9 × 9 i wypełnione wartościami false.
Dla każdej wypełnionej komórki (r, c) przyjmij, że d to jej cyfra pomniejszona o 1, a b = (r / 3) * 3 + c / 3.
Jeśli ustawiono seenRow[r][d], seenCol[c][d] lub seenBox[b][d], zwróć false; w przeciwnym razie ustaw wszystkie trzy.
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

Obliczanie bloku jako r / 3 + c / 3. Daje to tylko wartości od 0 do 4, więc (0, 3) i (3, 0) mają ten sam numer, mimo że należą do różnych bloków, a dwie 7 w tych blokach zostaną zgłoszone jako powtórzenie.
Dzielenie za pomocą / w JavaScript, Pythonie 3 lub Lua, gdzie 4 / 3 wynosi 1.33. Zaokrąglij w dół.
Traktowanie . jako wartości. Pusta plansza, dziewięć kropek w każdym wierszu, jest poprawna.
Próba rozwiązania łamigłówki. Wiersza 0 zawierającego 12345678. nie da się uzupełnić, jeśli 9 znajduje się niżej w kolumnie 8, a mimo to nic się nie powtarza: true.
Pomijanie bloków. W pełnej planszy, w której każdy wiersz jest przesunięty o jedno miejsce w lewo względem poprzedniego, nic nie powtarza się w wierszu ani kolumnie, ale w każdym bloku występują powtórzenia.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu Valid 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 sprawdzenie w jednym przebiegu odczytuje każde z n² pól raz i przechowuje 3n² znaczników: czas i pamięć O(n²).

Czy poprawna plansza Sudoku musi mieć rozwiązanie?

Nie. Tutaj „poprawna” oznacza tylko, że wśród wypełnionych pól żadna cyfra nie powtarza się w wierszu, kolumnie ani kwadracie 3 × 3. Plansza może przejść tę kontrolę, a mimo to nie mieć rozwiązania. Ustalenie, czy da się ją rozwiązać, wymaga przeszukiwania, na przykład z nawrotami, co jest innym problemem.

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

Tak. Przypisz każdemu wierszowi, kolumnie i polu jedną liczbę całkowitą, gdzie bit d oznacza, że widziano cyfrę d+1. Dla wypełnionej komórki, jeśli operacja AND między 1 << d a dowolną z jej trzech masek daje wartość niezerową, cyfra się powtarza; w przeciwnym razie wykonaj operację OR z każdą z trzech masek. To 27 liczb całkowitych zamiast 243 flag.

def isValidSudoku(board):
    # Wpisz tutaj kod

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"]

Oczekiwany wynik

true