Sudoku Solver
Plansza sudoku to siatka 9 × 9 podzielona na dziewięć kwadratów 3 × 3. Na rozwiązanej planszy w każdym wierszu, każdej kolumnie i każdym kwadracie każda cyfra od 1 do 9 występuje dokładnie raz.
Łamigłówka jest podana jako 9 ciągów znaków, po jednym na każdy wiersz, zaczynając od góry; . oznacza puste pole. Wypełnij wszystkie puste pola i zwróć rozwiązaną planszę w tej samej postaci. Plansza ma dokładnie jedno rozwiązanie.
Funkcja
- boardstring-array
- 9 wierszy łamigłówki, kropka w każdej pustej komórce
- Zwracastring-array
- 9 wierszy rozwiązanej planszy
Ograniczenia
boardzawiera 9 ciągów znaków o długości 9.- Każdy znak to
.lub jedna z cyfr1do9. - Podane cyfry nigdy się nie powtarzają w wierszu, kolumnie ani kwadracie.
- Plansza ma dokładnie jedno rozwiązanie.
Przykłady
- Wejście
- board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
- Wyjście
- ["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]
- Wyjaśnienie
- Górny wiersz
9.7.....6zawiera już 9, 7 i 6, więc w jego sześciu pustych komórkach muszą znaleźć się 1, 2, 3, 4, 5 i 8. Kolumny i pola decydują o tym, gdzie trafi każda z nich, a wiersz przyjmuje postać957214386.
Pytanie dodatkowe
W killer sudoku grupy pól muszą również sumować się do podanych wartości. Jak dodać tę zasadę do wyszukiwania i wykorzystać ją do wczesnego odcinania gałęzi?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Śledź, jakie cyfry zawiera już każdy wiersz, każda kolumna i każdy kwadrat 3 × 3. Dzięki temu możesz sprawdzić w czasie O(1), czy dana cyfra pasuje do pustej komórki.
Wypełniaj puste komórki pojedynczo. Wypróbuj każdą cyfrę, która pasuje do komórki, przejdź do następnej komórki i usuń cyfrę, jeśli nie da się z nią uzupełnić reszty planszy.
Kolejność komórek ma znaczenie. Następnie wypełnij pustą komórkę, której pozostało najmniej możliwych cyfr: komórka z jedną opcją nie wymaga rozgałęziania, a komórka bez żadnej od razu wskazuje, że trzeba się cofnąć.
Rozwiązanie
Rozwiąż to metodą nawrotów: wstaw pasującą cyfrę, kontynuuj i cofnij ją, gdy nie da się ukończyć planszy. Kolejność komórek decyduje o szybkości. Na trudnej planszy przeglądanie komórek w kolejności czytania może prowadzić do setek milionów częściowo wypełnionych plansz; wypełnienie najpierw komórki z najmniejszą liczbą możliwości zajmuje około stu prób.
Wycofywanie się w kolejności czytania
Poprawne, ale nie kończy się na największych testach
Intuicja
Wypełniaj puste komórki w kolejności czytania, wpisując w każdą najmniejszą pasującą cyfrę. Gdy w komórce nie zostanie już żadna cyfra, wróć do poprzedniej komórki i spróbuj następnej. Po kolei sprawdzana jest każda kombinacja zgodna z regułami, więc wyszukiwanie znajduje rozwiązanie.
Trzy tablice sprawiają, że każdy test dopasowania ma złożoność O(1): rowUsed[r][d], colUsed[c][d] i boxUsed[b][d], gdzie blok b = (r / 3) * 3 + c / 3. Wpisanie cyfry ustawia trzy wartości, a jej usunięcie je zeruje.
Stała kolejność jest słabym punktem: wyszukiwanie może wypełnić cały wiersz cyframi, które pasują lokalnie, a dopiero później odkryć, że wiele z nich nie pozostawia miejsca na pozostałe komórki. Plansza, której górne wiersze mają niemal żadnych wskazówek, a rozwiązaniem są w nich wysokie cyfry, sprawia, że wyszukiwanie przechodzi przez ponad 300 milionów częściowo wypełnionych plansz.
Algorytm
- Wczytaj planszę do siatki, używając 0 dla pustej komórki, wypełnij
rowUsed,colUsediboxUsed, a puste komórki wypisz w kolejności czytania. backtrack(k): jeślikjest równe liczbie pustych komórek, zwróć true.- Dla każdej cyfry
dod 1 do 9, która nie występuje w wierszu, kolumnie ani polu komórkik, umieść ją, oznacz ją i zwróć true, jeśli tak zrobibacktrack(k+1); w przeciwnym razie usuń oznaczenie. - Jeśli żadna cyfra nie pasuje, wyczyść komórkę i zwróć false. Wywołaj
backtrack(0)i zamień siatkę z powrotem na ciągi znaków.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# row_used[r][d] is True when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
row_used = [[False] * 10 for _ in range(9)]
col_used = [[False] * 10 for _ in range(9)]
box_used = [[False] * 10 for _ in range(9)]
empties = []
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
row_used[r][d] = col_used[c][d] = box_used[(r // 3) * 3 + c // 3][d] = True
else:
empties.append((r, c))
def backtrack(k):
if k == len(empties):
return True
r, c = empties[k]
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
grid[r][c] = d
row_used[r][d] = col_used[c][d] = box_used[b][d] = True
if backtrack(k + 1):
return True
row_used[r][d] = col_used[c][d] = box_used[b][d] = False
grid[r][c] = 0
return False
backtrack(0)
return ["".join(str(d) for d in row) for row in grid]Najpierw wypełnij najbardziej pustą komórkę
Intuicja
Rozwiązanie nie zależy od kolejności wypełniania, więc wybierz taką, która ograniczy przeszukiwanie: na każdym kroku wypełnij pustą komórkę, w której można wpisać najmniej cyfr. Komórka, w której można wpisać tylko jedną cyfrę, jest wymuszona i nie tworzy dodatkowej gałęzi. Komórka, w której nie można wpisać żadnej cyfry, jest wybierana od razu, dzięki czemu błędna plansza zostaje natychmiast wykryta.
Aby szybko zliczać dozwolone cyfry dla 81 komórek na każdym kroku, przechowuj każdy wiersz, każdą kolumnę i każdy blok jako maskę bitową: bit d w rows[r] jest ustawiony, gdy cyfra d znajduje się w wierszu r. Komórka dopuszcza ~(rows[r] | cols[c] | boxes[b]) & 0x3FE, gdzie 0x3FE zachowuje bity od 1 do 9, a liczba dozwolonych cyfr to liczba ustawionych bitów. Wpisanie d ustawia bit d w trzech maskach; operacja XOR usuwa go.
Algorytm
- Zbuduj siatkę i maski
rows,colsorazboxesna podstawie podanych cyfr. backtrack(): przejrzyj wszystkie komórki, oblicz dozwolone cyfry dla każdej pustej komórki i wybierz pierwszą komórkę z najmniejszą liczbą możliwości. Jeśli żadna komórka nie jest pusta, zwróć true.- Dla każdej dozwolonej cyfry w tej komórce umieść ją, ustaw jej bit w trzech maskach i zwróć true, jeśli
backtrack()zwróci true; w przeciwnym razie wyczyść bity. - Jeśli żadna cyfra nie pasuje, opróżnij komórkę i zwróć false. Wywołaj
backtrack()i ponownie zamień siatkę na ciągi znaków.
def solveSudoku(board):
grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
# Bit d of rows[r] is set when digit d already sits in row r; same for
# columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
for r in range(9):
for c in range(9):
d = grid[r][c]
if d:
rows[r] |= 1 << d
cols[c] |= 1 << d
boxes[(r // 3) * 3 + c // 3] |= 1 << d
def backtrack():
# Pick the empty cell with the fewest digits left (the first one on a tie).
best_r, best_c, best_allowed, best_count = -1, -1, 0, 10
for r in range(9):
for c in range(9):
if grid[r][c] == 0:
# Bits 1 to 9 of 0x3FE are the nine digits.
allowed = ~(rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]) & 0x3FE
count = bin(allowed).count("1")
if count < best_count:
best_r, best_c, best_allowed, best_count = r, c, allowed, count
if best_r == -1:
return True # no empty cell is left: the board is solved
r, c = best_r, best_c
b = (r // 3) * 3 + c // 3
for d in range(1, 10):
bit = 1 << d
if best_allowed & bit:
grid[r][c] = d
rows[r] |= bit
cols[c] |= bit
boxes[b] |= bit
if backtrack():
return True
rows[r] ^= bit
cols[c] ^= bit
boxes[b] ^= bit
grid[r][c] = 0
return False
backtrack()
return ["".join(str(d) for d in row) for row in grid]
Pułapki i przypadki brzegowe
- Zapominanie o usunięciu cyfry z rejestrów wiersza, kolumny i bloku po jej cofnięciu. Późniejsze komórki widzą wtedy tę cyfrę jako używaną, a wyszukiwanie pomija rozwiązanie.
- Używanie
r / 3 + c / 3do wyznaczania bloku. Komórki(0, 4)i(4, 0)trafiają do bloku o indeksie 1, więc dwa bloki współdzielą jeden rejestr i planszy nie da się wypełnić. Użyj(r / 3) * 3 + c / 3z dzieleniem całkowitym. - Niezatrzymywanie się po znalezieniu pierwszego rozwiązania. Kroki cofania opróżniają wtedy planszę ponownie, zanim ją odczytasz.
Najczęstsze pytania3
Jaka jest złożoność czasowa solvera sudoku wykorzystującego nawroty?
W najgorszym przypadku złożoność wykładnicza: O(9^m) dla m pustych komórek, ponieważ każda komórka może rozgałęzić się na maksymalnie 9 cyfr. W rzeczywistych łamigłówkach reguły dotyczące wierszy, kolumn i kwadratów eliminują większość możliwości, a wypełnianie najpierw najbardziej pustej komórki eliminuje większość pozostałych.
Jak sprawdzić, czy sudoku ma dokładnie jedno rozwiązanie?
Uruchom to samo wyszukiwanie z nawrotami, ale zliczaj rozwiązania i zakończ, gdy ich liczba osiągnie 2. Wynik 1 oznacza, że łamigłówka ma jedno rozwiązanie, a 0 — że nie ma żadnego. Generatory łamigłówek przeprowadzają tę kontrolę po usunięciu każdej wskazówki.
Czy istnieje szybszy sposób na rozwiązanie sudoku niż wyszukiwanie z nawrotami?
Większość szybkich rozwiązań nadal wymaga cofania się, ale przed każdym zgadywaniem pozwala wywnioskować więcej. Propagacja ograniczeń wypełnia każdą komórkę, która ma tylko jedną możliwą opcję, oraz każdą cyfrę, która pasuje tylko do jednej komórki w wierszu, kolumnie lub kwadracie, a następnie powtarza ten proces. Sudoku można również przedstawić jako problem dokładnego pokrycia i rozwiązać za pomocą algorytmu X Knutha.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def solveSudoku(board):
# Napisz kod tutajTest #1
Argument
board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
Oczekiwany wynik
["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]