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ść 🙂