Grafy w Pythonie – SUDOKU
su = [
[ 1, None, 2, 7 , None, None, 4, None, 5],
[ None, None, None, None, None, 3, 6, None, None],
[None, None, 4, 8, None, None, None, None, None],
[8, None, None, 4, None, None, None, 1, 2],
[None, None, None, None, None, 2, None, None, None],
[3, None, None, None, None, 8, None, None, 4],
[5, None, None, None, None, None, 1, 6, None],
[None, 6, None, None, None, 9, None, 3, 7],
[None, None, 3, None, None, None, None, None, None]
]
su = [
[None, None, 4, None, 3, None, 6, None, None],
[None, None, 7, None, None, 4, 3, None, None],
[None, None, None, 8, None, 1, 9, None, None],
[None, 9, None, 7, None, 5, None, 1, None],
[7, None, 3, 2, None, None, None, 6, None],
[5, None, None, None, None, None, None, None, None],
[4, None, None, None, 6, None, None, None, None],
[3, None, None, None, 2, None, 5, 9, None],
[2, None, 5, None, None, None, None, 8, None]
]
# czym są kolory w rozwiązywaniu sudoku? To po prostu liczby, ktore wpisujemy w kratki!
# ile takich kolorów ma być? Tyle ile pól w sudoku. Zakladajac ze mamy sudoku 9x9, to liczba
# kolorów wynosi 81
colors = []
for p in su:
colors.extend(p)
# Do rozwiazania sudoku potrzebujemy grafu, ktory określa jakie pola ze sobą "sąsiadują"
# Słowo "sąsiadują" oznacza w tym przypadku
# pola w tym samym wierszu
# pola w tej samej kolumnie
# pola w tym samym kwadracie
# Do ustalenia, które pola są ze sobą w tej relacji przyda się kilka stałych wartości:
SIZE3 = 3
SIZE9 = SIZE3 * SIZE3
SIZE27 = SIZE3 * SIZE9
SIZE81 = SIZE3 * SIZE27
number_of_colors = SIZE9
# generowanie grafu - początkowo graf jest pusty, ale zaraz będą zaznaczane polaczenia pomiędzy polami\
graph = [ [0] * SIZE81 for x in range(SIZE81) ]
# zaczyna się zabawa. Trzeba ustalić, które pola są w tym samym wierszu/kolumnie/kwadracie
# przgladamy każde pole i ustalamy relacje
for row in range(SIZE81):
for col in range(SIZE81):
# relacja do wszystkich w tym samym wierszu
if col % SIZE9 == row % SIZE9:
graph[row][col] = 1
# relacja do wszystkich w tej samej kolumnie
if col // SIZE9 == row // SIZE9:
graph[row][col] = 1
# relacja dla wszystkich w tym samym kwadracie
mini_box_horizontal_row = (row // SIZE27) * SIZE27
mini_box_horizontal_col = (col // SIZE27) * SIZE27
mini_box_vertical_row = (row % SIZE9 ) // SIZE3
mini_box_vertical_col = (col % SIZE9 ) // SIZE3
if mini_box_horizontal_row == mini_box_horizontal_col and mini_box_vertical_row == mini_box_vertical_col:
graph[row][col] = 1
# komórka nie jest w relacji sama do siebie:
if row == col:
graph[row][col] = 0
# funkcje służące do kolorowania grafu, tak jak bylo to pokazane na kursie
# tutaj funkcja sprawdzająca, czy pomalowanie węzła na określony kolor spowodowałoby konflikt
def is_no_conflict(graph, vertex_idx, colors, color):
for i in range(len(graph)):
if graph[vertex_idx][i] == 1 and colors[i] == color:
return False
return True
# funkcja służąca do kolorowania grafu. W porownaniu do funkcji z kursu mamy tu mala zmiane.
# Część pól w sudoku ma już swoją określoną wartość, dlatego w tych polach nie próbujemy
# odgadnąć wartości - bierzemy ją tak jak jest
def try_paint(graph, number_of_colors, colors, vertex_idx):
# jesli jestesmy na ostatnim polu to koniec
if vertex_idx == len(graph):
return True
# jesli aktualna komorka jeszcze nie ma przypisanej liczby-koloru
if colors[vertex_idx] == None:
# probujemy kolorowac kazdym kolorem po kolei - w koncu trafimy!
for color in range(1,number_of_colors+1):
colors[vertex_idx] = color
# sprawdzamy czy nie ma konfliktu i jeśli ok, to zwrócimy wartość dalszych prób kolorowania
if is_no_conflict(graph, vertex_idx, colors, color):
# probujemy dalej kolorowac
if try_paint(graph, number_of_colors, colors, vertex_idx + 1):
return True
# jesli jestemy tutaj, to nowy kolor spowodowal konflikt i... trzeba sie wycofac z tego koloru
# i w kolejnej iteracji petli zastosować następny kolor
colors[vertex_idx] = None
else:
# tu juz mam kolor i nie musze zgadywac
return try_paint(graph, number_of_colors, colors, vertex_idx + 1)
# jesli jestem tutaj, to kolorowanie nie udalo sie i trzeba wyprobowac inny kolor gdzies wczesniej
return False
# probujemy kolorowania, czyli wypeniania grafu
result = try_paint(graph, number_of_colors, colors, 0)
# jesli udalo sie znalezc rozwiazanie to je wyswietl
if result:
print(f"Solution found: {colors}")
start = 0
while start < SIZE81:
print(colors[start:start+SIZE9])
start += SIZE9
else:
print("Solution not found.")