Przeczytaj

Problem ośmiu hetmanów

W poprzednim e‑materialeP6iWCRsmke‑materiale omówiliśmy, na czym polega problem ośmiu hetmanów. Przedstawiliśmy także algorytm rozwiązujący ten problem. W sekcji „Film samouczek” zaimplementowaliśmy algorytm.

W tej sekcji przedstawimy alternatywną implementację algorytmu, pokażemy dlaczego metoda siłowa (ang. brute‑force), generująca wszystkie możliwe ustawienia hetmanów nie jest optymalna, a także zaprezentujemy graficzną planszę z wynikiem działania algorytmu.

Ro6vScD6sPBgq

Ilustracja przedstawia szachownicę. Szachownica jest w kształcie kwadratu złożonego z mniejszych jasnych i ciemnych kwadratów. Przy poziomych bokach kwadratu znajdują się oznaczenia: a, b, c, d, e, f, g, h identyfikujące poszczególne mniejsze kwadratowe pola. W linii pionowej szachownicy, przy pomniejszych polach znajdują się oznaczenia: 8, 7, 6, 5, 4, 3, 2, 1. Na szachownicy znajduje się osiem hetmanów ustawionych na polach z oznaczeniami: a4, b6, c8, d2, e7, f1, g3, h5. — Jedno z wielu możliwych rozwiązań problemu ośmiu hetmanów.
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Metoda 1

Zastanówmy się nad siłowym rozwiązaniem problemu (ang. brute‑force). Polega ono na przejrzeniu wszystkich możliwych ustawień hetmanów na szachownicy i sprawdzeniu, czy figury są poprawnie ustawione. Ta metoda ma jednak podstawową wadę: ogromną liczbę przypadków do rozpatrzenia - ponad 4 mld.

Dla zainteresowanych

Skąd taka liczba? Każde ustawienie to wybór 8 pól spośród wszystkich 64 pól szachownicy. Takich ustawień jest tyle, ile 8‑elementowych kombinacji bez powtórzeń zbioru 64‑elementowego. Ich liczbę można wyznaczyć z użyciem wzoru na liczbę k‑elementowych kombinacji bez powtórzeń ze zbioru n‑elementowego: $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ , gdzie $\binom{n}{k}$ to współczynnik dwumianowy Newtona. Po podstawieniu wartości otrzymujemy:

$\binom{64}{8} = \frac{64!}{8!(64-8)!} = 4426165368$ .

Taka liczba przypadków do rozpatrzenia jest ogromna nawet dla bardzo szybkiego komputera. Przy założeniu, że procesor będzie wykonywał 4 000 obliczeń na sekundę, to i tak znalezienie rozwiązania zajmie ponad 278 godzin.

Metoda 2

Znacznie lepszym sposobem jest algorytm przeszukiwania z nawrotami, przedstawiony w sekcji „Film samouczek” i omówiony szczegółowo w e‑materiale Problem ośmiu hetmanówP6iWCRsmkProblem ośmiu hetmanów.

Przykład 1

Przygotujmy program, który zrealizuje ten algorytm, a jako wynik zwróci listę (tablicę) zawierającą osiem elementów – będą to numery kolumn, w których należy ustawić hetmana w kolejnych wierszach szachownicy. Jeżeli ustawienia nie da się zrealizować, program powinien wypisać komunikat: Nie istnieje rozwiązanie.

Specyfikacja:

Dane:

N – liczba hetmanów oraz liczba wierszy i kolumn szachownicy; liczba naturalna dodatnia

Wynik:

Program wypisuje numery kolumn, w których należy ustawić hetmana w kolejnych wierszach szachownicy lub wypisuje komunikat: Nie istnieje rozwiązanie – jeśli hetmanów nie da się ustawić zgodnie z warunkami zadania.

Linia 1. kratka Funkcja sprawdza czy pole o współrzędnych w przecinek k nie. Linia 2. kratka jest atakowane przez innego hetmana kropka Zwracaną wartością jest True przecinek. Linia 3. kratka jeżeli pole jest bezpieczne przecinek bądź False w p kropka p kropka. Linia 4. def dopuszczalny otwórz nawias okrągły w przecinek k zamknij nawias okrągły dwukropek. Linia 5. wynik znak równości a otwórz nawias kwadratowy w zamknij nawias kwadratowy and b otwórz nawias kwadratowy w plus k zamknij nawias kwadratowy and c otwórz nawias kwadratowy w minus k zamknij nawias kwadratowy. Linia 6. return wynik. Linia 8. kratka Procedura cudzysłów ustawia cudzysłów hetmana na wskazanym polu kropka Do tablic informujących. Linia 9. kratka czy pola są bezpiczne zapisywana jest informacja przecinek o ataku kropka. Linia 10. def zapisz otwórz nawias okrągły w przecinek k zamknij nawias okrągły dwukropek. Linia 11. x otwórz nawias kwadratowy k zamknij nawias kwadratowy znak równości w kratka tu zapisujemy numer wiersza. Linia 12. a otwórz nawias kwadratowy w zamknij nawias kwadratowy znak równości False. Linia 13. b otwórz nawias kwadratowy w plus k zamknij nawias kwadratowy znak równości False. Linia 14. c otwórz nawias kwadratowy w minus k zamknij nawias kwadratowy znak równości False. Linia 16. kratka Procedura oznacza pola jako ponownie bezpiczne kropka. Linia 17. def wymaz otwórz nawias okrągły w przecinek k zamknij nawias okrągły dwukropek. Linia 18. a otwórz nawias kwadratowy w zamknij nawias kwadratowy znak równości True. Linia 19. b otwórz nawias kwadratowy w plus k zamknij nawias kwadratowy znak równości True. Linia 20. c otwórz nawias kwadratowy w minus k zamknij nawias kwadratowy znak równości True. Linia 22. kratka Funkcja próbuje ustawić hetmana w kolumnie k kropka. Linia 23. def probuj otwórz nawias okrągły k zamknij nawias okrągły dwukropek. Linia 24. udany znak równości False. Linia 25. w znak równości 1. Linia 27. while otwórz nawias okrągły not udany zamknij nawias okrągły and otwórz nawias okrągły w otwórz nawias ostrokątny znak równości N zamknij nawias okrągły dwukropek. Linia 28. if dopuszczalny otwórz nawias okrągły w przecinek k zamknij nawias okrągły dwukropek. Linia 29. zapisz otwórz nawias okrągły w przecinek k zamknij nawias okrągły. Linia 31. if k otwórz nawias ostrokątny N dwukropek. Linia 32. udany znak równości probuj otwórz nawias okrągły k plus 1 zamknij nawias okrągły. Linia 34. if not udany dwukropek. Linia 35. wymaz otwórz nawias okrągły w przecinek k zamknij nawias okrągły. Linia 36. else dwukropek. Linia 37. udany znak równości True. Linia 39. w plus znak równości 1. Linia 41. return udany. Linia 43. kratka definiujemy wartości globalne. Linia 44. kratka skorzystamy z właściwości możliwości zmiany elementów listy. Linia 45. kratka niezależnie od przestrzeni nazw w języku Python. Linia 47. N znak równości 8 kratka bok szachownicy i jednocześnie liczba hetmanów. Linia 48. x znak równości otwórz nawias okrągły N plus 1 zamknij nawias okrągły asterysk otwórz nawias kwadratowy 0 zamknij nawias kwadratowy kratka x otwórz nawias kwadratowy i zamknij nawias kwadratowy to pozycja hetmana w wierszu i. Linia 49. a znak równości otwórz nawias okrągły N plus 1 zamknij nawias okrągły asterysk otwórz nawias kwadratowy True zamknij nawias kwadratowy kratka a otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości znak równości True to brak hetmana w wierszu j. Linia 50. kratka b otwórz nawias kwadratowy k zamknij nawias kwadratowy znak równości znak równości True to brak hetmana na przekątnej k otwórz nawias kwadratowy prawy ukośnik zamknij nawias kwadratowy kropka. Linia 51. b znak równości otwórz nawias okrągły 2 asterysk otwórz nawias okrągły N plus 1 zamknij nawias okrągły minus 1 zamknij nawias okrągły asterysk otwórz nawias kwadratowy True zamknij nawias kwadratowy. Linia 52. kratka Suma wiersz plus kolumna od 0 do otwórz nawias okrągły 2N minus 2 zamknij nawias okrągły kropka. Linia 53. kratka c otwórz nawias kwadratowy k zamknij nawias kwadratowy znak równości znak równości True to brak hetmana na przekątnej k kropka. Linia 54. c znak równości otwórz nawias okrągły 2 asterysk otwórz nawias okrągły N plus 1 zamknij nawias okrągły minus 1 zamknij nawias okrągły asterysk otwórz nawias kwadratowy True zamknij nawias kwadratowy. Linia 55. kratka Różnica wiersz minus kolumna od otwórz nawias okrągły minus N plus 1 zamknij nawias okrągły do otwórz nawias okrągły N minus 1 zamknij nawias okrągły kropka. Linia 56. kratka pierwsze możliwe miejsce dla hetmana otwórz nawias okrągły 0 przecinek 0 zamknij nawias okrągły. Linia 57. startowa podkreślnik pozycja znak równości 1. Linia 59. if probuj otwórz nawias okrągły startowa podkreślnik pozycja zamknij nawias okrągły dwukropek. Linia 60. print otwórz nawias okrągły x otwórz nawias kwadratowy 1 dwukropek zamknij nawias kwadratowy zamknij nawias okrągły. Linia 61. else dwukropek. Linia 62. print otwórz nawias okrągły cudzysłów Nie istnieje rozwiązanie cudzysłów zamknij nawias okrągły. Linia 64. kratka przykładowe wykonanie tego proramu daje wynik dwukropek. Linia 65. kratka Mamy rozwiązanie dwukropek otwórz nawias kwadratowy 1 przecinek 5 przecinek 8 przecinek 6 przecinek 3 przecinek 7 przecinek 2 przecinek 4 zamknij nawias kwadratowy.

# Funkcja sprawdza czy pole o współrzędnych w, k nie 
# jest atakowane przez innego hetmana. Zwracaną wartością jest True, 
# jeżeli pole jest bezpieczne, bądź False w p.p.
def dopuszczalny(w, k):
	wynik = a[w] and b[w + k] and c[w - k]
	return wynik

# Procedura "ustawia" hetmana na wskazanym polu. Do tablic informujących
# czy pola są bezpiczne zapisywana jest informacja, o ataku.
def zapisz(w, k):
	x[k] = w # tu zapisujemy numer wiersza
	a[w] = False
	b[w + k] = False
	c[w - k] = False

# Procedura oznacza pola jako ponownie bezpiczne.
def wymaz(w, k):
	a[w] = True
	b[w + k] = True
	c[w - k] = True

# Funkcja próbuje ustawić hetmana w kolumnie k. 
def probuj(k):
	udany = False
	w = 1

	while (not udany) and (w <= N):
		if dopuszczalny(w, k):
			zapisz(w, k)

			if k < N:
				udany = probuj(k + 1)

				if not udany:
					wymaz(w, k)
			else:
				udany = True

		w += 1

	return udany

# definiujemy wartości globalne
# skorzystamy z właściwości możliwości zmiany elementów listy
# niezależnie od przestrzeni nazw w języku Python

N = 8  # bok szachownicy i jednocześnie liczba hetmanów
x = (N + 1) * [0] # x[i] to pozycja hetmana w wierszu i
a = (N + 1) * [True] # a[j] == True to brak hetmana w wierszu j
# b[k] == True to brak hetmana na przekątnej k [/].
b = (2 * (N + 1) - 1) * [True]
# Suma wiersz + kolumna od 0 do (2N - 2).
# c[k] == True to brak hetmana na przekątnej k.
c = (2 * (N + 1) - 1) * [True]
# Różnica wiersz-kolumna od (-N + 1) do (N - 1).
# pierwsze możliwe miejsce dla hetmana (0,0)
startowa_pozycja = 1

if probuj(startowa_pozycja):
	print(x[1:])
else:
	print("Nie istnieje rozwiązanie")
    
# przykładowe wykonanie tego proramu daje wynik:
# Mamy rozwiązanie: [1, 5, 8, 6, 3, 7, 2, 4]

Przykład 2

Zdefiniujmy funkcję, która korzystając z danych przygotowanych przez program z Przykładu 1, pozwoli wyświetlić prostą reprezentację wyników.

Linia 1. def rysuj otwórz nawias okrągły dane przecinek n zamknij nawias okrągły dwukropek. Linia 2. for w in range otwórz nawias okrągły 1 przecinek n plus 1 zamknij nawias okrągły dwukropek. Linia 3. print otwórz nawias okrągły f cudzysłów Dla wiersza otwórz nawias klamrowy w zamknij nawias klamrowy kolumna otwórz nawias klamrowy dane otwórz nawias kwadratowy w zamknij nawias kwadratowy zamknij nawias klamrowy kropka cudzysłów zamknij nawias okrągły. Linia 5. print otwórz nawias okrągły cudzysłów minus minus minus minus minus otwórz nawias kwadratowy przykładowa szachownica zamknij nawias kwadratowy minus minus minus minus minus cudzysłów zamknij nawias okrągły. Linia 7. for w in range otwórz nawias okrągły 1 przecinek n plus 1 zamknij nawias okrągły dwukropek. Linia 8. print otwórz nawias okrągły f cudzysłów W dwukropek otwórz nawias klamrowy w zamknij nawias klamrowy K dwukropek otwórz nawias klamrowy dane otwórz nawias kwadratowy w zamknij nawias kwadratowy zamknij nawias klamrowy minus zamknij nawias ostrokątny cudzysłów przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły. Linia 10. for k in range otwórz nawias okrągły 1 przecinek n plus 1 zamknij nawias okrągły dwukropek. Linia 11. if dane otwórz nawias kwadratowy w zamknij nawias kwadratowy znak równości znak równości k dwukropek. Linia 12. print otwórz nawias okrągły cudzysłów H cudzysłów przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły. Linia 13. else dwukropek. Linia 14. print otwórz nawias okrągły cudzysłów kropka cudzysłów przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły. Linia 16. print otwórz nawias okrągły cudzysłów cudzysłów zamknij nawias okrągły. Linia 18. kratka wywołujemy program przecinek podając jako parametry. Linia 19. kratka dane uzyskane z poprzedniego programu. Linia 21. rysuj otwórz nawias okrągły x przecinek N zamknij nawias okrągły. Linia 23. kratka przykładowy wynik działania funkcji rysuj. Linia 24. kratka Dla wiersza 1 kolumna 1 kropka. Linia 25. kratka Dla wiersza 2 kolumna 5 kropka. Linia 26. kratka Dla wiersza 3 kolumna 8 kropka. Linia 27. kratka Dla wiersza 4 kolumna 6 kropka. Linia 28. kratka Dla wiersza 5 kolumna 3 kropka. Linia 29. kratka Dla wiersza 6 kolumna 7 kropka. Linia 30. kratka Dla wiersza 7 kolumna 2 kropka. Linia 31. kratka Dla wiersza 8 kolumna 4 kropka. Linia 32. kratka minus minus minus minus minus otwórz nawias kwadratowy przykładowa szachownica zamknij nawias kwadratowy minus minus minus minus minus. Linia 33. kratka W dwukropek 1 K dwukropek 1 minus zamknij nawias ostrokątny H kropka kropka kropka kropka kropka kropka kropka. Linia 34. kratka W dwukropek 2 K dwukropek 5 minus zamknij nawias ostrokątny kropka kropka kropka kropka H kropka kropka kropka. Linia 35. kratka W dwukropek 3 K dwukropek 8 minus zamknij nawias ostrokątny kropka kropka kropka kropka kropka kropka kropka H. Linia 36. kratka W dwukropek 4 K dwukropek 6 minus zamknij nawias ostrokątny kropka kropka kropka kropka kropka H kropka kropka. Linia 37. kratka W dwukropek 5 K dwukropek 3 minus zamknij nawias ostrokątny kropka kropka H kropka kropka kropka kropka kropka. Linia 38. kratka W dwukropek 6 K dwukropek 7 minus zamknij nawias ostrokątny kropka kropka kropka kropka kropka kropka H kropka. Linia 39. kratka W dwukropek 7 K dwukropek 2 minus zamknij nawias ostrokątny kropka H kropka kropka kropka kropka kropka kropka. Linia 40. kratka W dwukropek 8 K dwukropek 4 minus zamknij nawias ostrokątny kropka kropka kropka H kropka kropka kropka kropka.

def rysuj(dane, n):
	for w in range(1, n + 1):
		print(f"Dla wiersza {w} kolumna {dane[w]}.")

	print("-----[przykładowa szachownica]-----")

	for w in range(1, n + 1):
		print(f"W:{w} K:{dane[w]}->", end="")

		for k in range(1, n + 1):
			if dane[w] == k:
				print(" H", end="")
			else:
				print(" .", end="")

		print("")

# wywołujemy program, podając jako parametry
# dane uzyskane z poprzedniego programu

rysuj(x, N)

# przykładowy wynik działania funkcji rysuj
# Dla wiersza 1 kolumna 1.
# Dla wiersza 2 kolumna 5.
# Dla wiersza 3 kolumna 8.
# Dla wiersza 4 kolumna 6.
# Dla wiersza 5 kolumna 3.
# Dla wiersza 6 kolumna 7.
# Dla wiersza 7 kolumna 2.
# Dla wiersza 8 kolumna 4.
# -----[przykładowa szachownica]-----
# W:1 K:1-> H . . . . . . .
# W:2 K:5-> . . . . H . . .
# W:3 K:8-> . . . . . . . H
# W:4 K:6-> . . . . . H . .
# W:5 K:3-> . . H . . . . .
# W:6 K:7-> . . . . . . H .
# W:7 K:2-> . H . . . . . .
# W:8 K:4-> . . . H . . . .

Dla zainteresowanych

Prezentację wyników możemy wykonać za pomocą biblioteki Pygame ZeroPygame ZeroPygame Zero. Pozwoli ona w łatwy sposób wyświetlić grafiki hetmanów na szachownicy.

Przykład 3

Przygotujmy kod, który – wykorzystując bibliotekę Pygame ZeroPygame ZeroPygame Zero – zrealizuje graficzną wizualizację.

Linia 1. TITLE znak równości cudzysłów 8 hetmanów cudzysłów. Linia 2. WIDTH znak równości 400. Linia 3. HEIGHT znak równości 400. Linia 4. pozycje znak równości otwórz nawias kwadratowy 1 przecinek 5 przecinek 8 przecinek 6 przecinek 3 przecinek 7 przecinek 2 przecinek 4 zamknij nawias kwadratowy. Linia 5. hetmany znak równości otwórz nawias kwadratowy. Linia 6. Actor otwórz nawias okrągły cudzysłów queen kropka png cudzysłów zamknij nawias okrągły przecinek. Linia 7. Actor otwórz nawias okrągły cudzysłów queen kropka png cudzysłów zamknij nawias okrągły przecinek. Linia 8. Actor otwórz nawias okrągły cudzysłów queen kropka png cudzysłów zamknij nawias okrągły przecinek. Linia 9. Actor otwórz nawias okrągły cudzysłów queen kropka png cudzysłów zamknij nawias okrągły przecinek. Linia 10. Actor otwórz nawias okrągły cudzysłów queen kropka png cudzysłów zamknij nawias okrągły przecinek. Linia 11. Actor otwórz nawias okrągły cudzysłów queen kropka png cudzysłów zamknij nawias okrągły przecinek. Linia 12. Actor otwórz nawias okrągły cudzysłów queen kropka png cudzysłów zamknij nawias okrągły przecinek. Linia 13. Actor otwórz nawias okrągły cudzysłów queen kropka png cudzysłów zamknij nawias okrągły. Linia 14. zamknij nawias kwadratowy. Linia 16. def draw otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 17. screen kropka fill otwórz nawias okrągły otwórz nawias okrągły 255 przecinek 255 przecinek 255 zamknij nawias okrągły zamknij nawias okrągły kratka ustawiamy białe tło. Linia 19. kratka rysujemy linie pionowe i poziome. Linia 20. for x in range otwórz nawias okrągły 0 przecinek 400 przecinek 50 zamknij nawias okrągły dwukropek. Linia 21. start znak równości otwórz nawias okrągły x przecinek 0 zamknij nawias okrągły. Linia 22. koniec znak równości otwórz nawias okrągły x przecinek 400 zamknij nawias okrągły. Linia 23. screen kropka draw kropka line otwórz nawias okrągły start przecinek koniec przecinek otwórz nawias okrągły 0 przecinek 0 przecinek 0 zamknij nawias okrągły zamknij nawias okrągły. Linia 25. for y in range otwórz nawias okrągły 0 przecinek 400 przecinek 50 zamknij nawias okrągły dwukropek. Linia 26. start znak równości otwórz nawias okrągły 0 przecinek y zamknij nawias okrągły. Linia 27. koniec znak równości otwórz nawias okrągły 400 przecinek y zamknij nawias okrągły. Linia 28. screen kropka draw kropka line otwórz nawias okrągły start przecinek koniec przecinek otwórz nawias okrągły 0 przecinek 0 przecinek 0 zamknij nawias okrągły zamknij nawias okrągły. Linia 30. kratka wykreślamy hetmany na ekranie. Linia 31. for w in range otwórz nawias okrągły 1 przecinek 9 zamknij nawias okrągły dwukropek. Linia 32. k znak równości pozycje otwórz nawias kwadratowy w minus 1 zamknij nawias kwadratowy. Linia 33. x znak równości otwórz nawias okrągły k asterysk 50 zamknij nawias okrągły minus 25. Linia 34. y znak równości otwórz nawias okrągły w asterysk 50 zamknij nawias okrągły minus 25. Linia 35. kratka ustawiamy pozycję na szachownicy. Linia 36. hetmany otwórz nawias kwadratowy w minus 1 zamknij nawias kwadratowy kropka pos znak równości otwórz nawias okrągły x przecinek y zamknij nawias okrągły. Linia 37. kratka metodą draw otwórz nawias okrągły zamknij nawias okrągły wyświetlamy dany element. Linia 38. hetmany otwórz nawias kwadratowy w minus 1 zamknij nawias kwadratowy kropka draw otwórz nawias okrągły zamknij nawias okrągły.

TITLE = "8 hetmanów"
WIDTH = 400
HEIGHT = 400
pozycje = [1, 5, 8, 6, 3, 7, 2, 4]
hetmany = [
	Actor("queen.png"),
	Actor("queen.png"),
	Actor("queen.png"),
	Actor("queen.png"),
	Actor("queen.png"),
	Actor("queen.png"),
	Actor("queen.png"),
	Actor("queen.png")
]

def draw():
	screen.fill((255, 255, 255)) # ustawiamy białe tło

	# rysujemy linie pionowe i poziome
	for x in range(0, 400, 50):
		start = (x, 0)
		koniec = (x, 400)
		screen.draw.line(start, koniec, (0, 0, 0))

	for y in range(0, 400, 50):
		start = (0, y)
		koniec = (400, y)
		screen.draw.line(start, koniec, (0, 0, 0))

	# wykreślamy hetmany na ekranie
	for w in range(1, 9):
		k = pozycje[w - 1]
		x = (k * 50) - 25
		y = (w * 50) - 25
		# ustawiamy pozycję na szachownicy
		hetmany[w - 1].pos = (x, y) 
		# metodą draw() wyświetlamy dany element
		hetmany[w - 1].draw()

Ważne!

Aby używać biblioteki Pygame Zero, uruchomimy program zapisany w języku Python za pomocą polecenia pgzrun program.py, korzystając z linii poleceń systemu operacyjnego.

pgzrun nazwa_programu.py

Oto przykład wykonania naszego kodu:

R1ZjBo0rmNumu

Zrzut ekranu przedstawia linię poleceń, w którą wpisano polecenie: pgzrun hetmany_pygame.py. Poniżej wyświetliło się okno programu 8 hetmanów. Wewnątrz okna znajduje się szachownica z wydzielonymi polami oraz 8 hetmanów ustawionymi na polach: a8, b2, c4, d1, e7, f5, g3, h6.

Biblioteka Pygame Zero wymaga, aby obrazki, które wykorzystujemy w naszym programie, były zapisane w postaci plików png w podkatalogu images, w katalogu, w którym istnieje nasz program. Użyjemy w tym celu grafiki pochodzącej z jednego z serwisów oferujących ilustracje na otwartej licencji. Musimy tylko zmienić rozdzielczość tej grafiki, aby mieściła się w polu 50x50 pikseli. Przykładowy katalog z plikami wygląda następująco:

R1PrtNs4r4S6m

Zrzut ekranu przedstawia folder python/hetmany/images. Wewnątrz folderu znajduje się plik: queen.png czyli ikona hetmana (korona z pięcioma czubkami).

Efekt końcowy działania programu to graficzna prezentacja możliwych ustawień hetmanów na szachownicy.

R2A31hU0rLe3J

Zrzut ekranu przedstawia okno programu 8 hetmanów. Wewnątrz okna znajduje się szachownica z wydzielonymi polami oraz 8 hetmanów ustawionymi na polach: a8, b2, c4, d1, e7, f5, g3, h6.

Słownik

algorytm z nawrotami

(z ang. backtracking) algorytm, który wyszukuje rozwiązania niektórych problemów obliczeniowych, stopniowo generując kandydatów na rozwiązanie; gdy zauważy, że kandydat nie może być poprawnym rozwiązaniem, wraca do punktu, w którym może zmienić decyzję

Pygame Zero

biblioteka służąca do szybkiego tworzenia gier w języku Python; oparta na bibliotece Pygame, umożliwia tworzenie programów graficznych za pomocą minimalnej ilości kodu; nie jest dostępna w standardowej instalacji języka Python – należy ją zainstalować, korzystając z polecenia pip install pgzero

Film samouczek

Sprawdź się

Problem ośmiu hetmanów

Metoda 1

Metoda 2

Słownik