Czytam ostatnio trochę o algorytmach i natrafiłem na algorytm Backtrackingu (pol. algorytm z nawrotami). Zacząłem czytać, aby zrozumieć do czego można to zastosować i jak to działa. Ostatecznie napisałem też implementację tego algorytmu w postaci sudoku solver’a. Szczegóły implementacji oraz wyjaśnienie co do czego i jak to działa w poniższym opisie.
Okej. Pierwsze pytanie (dla niezaznajomionych) co to jest sudoku? Za wikipedią:
Łamigłówka, której celem jest wypełnienie diagramu 9 × 9 w taki sposób, aby w każdym wierszu, w każdej kolumnie i w każdym z dziewięciu pogrubionych kwadratów 3 × 3 (zwanych „blokami” lub „podkwadratami”) znalazło się po jednej cyfrze od 1 do 9.
Czas na implementację 😉 Zdefiniujmy główną funkcję rozwiązującą soduku o nazwie solve. Funkcja przyjmować będzie jeden parametr: grid (o wielkości 9×9 pól)
def solve(grid):
# szukamy lokalizacji pierwszego zera na gridzie; location to lista zawierająca dwie liczby - pierwsza
# wskazuje numer wiersza (licząc od zera), druga wskazuje numer kolumny (licząc od zera)
location = find_empty_location(grid)
# jeżeli nie znaleźliśmy lokalizacji zera to znaczy, że jest super i cały grid został uzupełniony
if not location:
return True
# iterujemy po liczbach od 1 do 9
for num in range(1, 10):
# sprawdzamy czy lokalizacja jest bezpieczna
if location_is_safe(num, location, grid):
row_index, column_index = location
# aktualizujemy znalezioną lokalizację wybraną liczbą
grid[row_index][column_index] = num
# wywołujemy rekurencyjnie funkcję solve - jeśli udało się znaleźć liczbę wychodzimy z funkcji
if solve(grid):
return True
# nie udało się znaleźć odpowiedniej liczby, dlatego ustawiamy lokalizację z powrotem na 0
grid[row_index][column_index] = 0
# tutaj odbywa się backtracing, czyli nawrót z funkcji
return False
Mamy już główną funkcję solve, która jest sercem naszego solvera. Teraz czas na funkcje pomocnicze. Zacznijmy od funkcji szukającej lokalizacji z zerem:
def find_empty_location(grid):
# przechodzimy po wierszach i kolumnach i zwracamy lokalizację pierwszego znalezionego zera
for row in range(9):
for column in range(9):
if grid[row][column] == 0:
return [row, column]
Teraz utwórzmy funkcję sprawdzającą, czy wybrana lokalizacja jest bezpieczna:
def location_is_safe(num, location, grid):
row_index, column_index = location
# wszystkie liczby wchodzące w wiersz, gdzie znajduje się nasza liczba
row = [item for item in grid[row_index]]
# sprawdzamy, czy wiersz jest bezpieczny (nie zawiera wybranej liczby)
if not check_is_safe(row, num):
return False
# wszystkie liczby wchodzące w kolumnę, gdzie znajduje się nasza liczba
column = [grid[index][column_index] for index in range(9)]
# sprawdzamy, czy kolumna jest bezpieczna (nie zawiera wybranej liczby)
if not check_is_safe(column, num):
return False
# czas na sprawdzenie, czy box 3x3 zawiera wybraną liczbę
# żeby to sprawdzić ustalamy index boxu, czyli pierwszą liczbę w lewym górnym rogu
# możemy mieć takie lokalizacje jak np.: [0,0], [3,0], [3,3] itd.
box_row_index = row_index - row_index % 3
box_column_index = column_index - column_index % 3
# ustalamy cały box, tzn. do wybranej lokalizacji boxu dodajemy + 3 aby uzyskać box o wielkości 3x3
box = [row[box_column_index:box_column_index + 3] for row in grid[box_row_index:box_row_index + 3]]
# sprawdzamy czy box jest bezpieczny (nie zawiera wybranej liczby)
if not check_box_is_safe(box, num):
return False
# zwracamy True, to znaczy, że lokalizacja jest bezpieczna
return True
Dodajmy funkcję sprawdzającą czy lokalizacja jest bezpieczna dla wiersza lub kolumny:
def check_is_safe(row, num):
# iterujemy po każdej liczbie w wierszu / kolumnie
# jeśli znajdziemy naszą liczbę to zwracamy False
for field in row:
if num == field:
return False
# wiesz / kolumna jest bezpieczna
return True
Teraz sprawdźmy czy box jest bezpieczny:
def check_box_is_safe(box, num):
# iterujemy po wszystkich wierszach i kolumnach boxu
# jeśli znajdziemy naszą liczbę to zwracamy False
for i in range(3):
for j in range(3):
if box[i][j] == num:
return False
# box jest bezpieczny
return True
Stwórzmy również funkcję pomocniczą do wyświetlenia na ekranie naszego rozwiązanego grida:
def print_grid(grid):
for i in range(9):
for j in range(9):
print(grid[i][j], end="")
print('\n')
Zdefiniujmy grid, który chcemy rozwiązać:
grid = [
[0,5,8,0,0,0,0,0,3],
[1,7,0,0,5,0,0,0,8],
[0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,0,0],
[4,0,7,0,8,0,0,0,6],
[0,8,3,0,6,0,0,1,7],
[9,1,0,0,0,3,0,7,0],
[0,0,6,0,0,0,0,8,0],
[0,0,0,0,0,0,0,3,4],
]
Wszystko gotowe, możemy uruchomić nasz sudoku solver:
if solve(grid):
print_grid(grid)
else:
print("Nie znaleziono rozwiazania")
Rozwiązane sudoku:
658142793 172359468 349678152 561237849 497581326 283964517 914823675 736495281 825716934
W przypadku grida zdefiniowanego w powyższym przykładzie funkcja solve potrzebowała 301478 nawrotów.
Cały skrypt znajdziecie tutaj: https://gist.github.com/bgruszka/df6e441761a8e5412300b9392c17d2b9
Dodatkowo poniżej jeszcze filmik (~15 min) z tłumaczeniem na żywo jak to działa. PS. Wybaczcie czasami szumy w filmie – nie wiedzieć czemu laptop mi się strasznie rozgrzał 😉 Dodam jeszcze, że to mój pierwszy film tego typu, więc proszę o wyrozumiałość 🙂