Długość ma znaczenie

https://xpil.eu/YscDH 📋

Naiwnie liczę na to, że część moich Czytelników przeczyta dzisiejszy wpis skuszona tym filuternym tytułem.

Niestety, naga prawda jest taka, że po pierwsze primo będe dziś promował krótkość a nie długość, a po drugie primo nie wiem o czym tam sobie jeden z drugim myśli, w każdym razie chodzi dziś o długość (a raczej: krótkość) kodu realizującego pewne całkiem niebanalne zadanie.

Zresztą, każdy kto ma odrobinę oleju w głowie już dawno zauważył, że dzisiejszy wpis jest w kategorii "Pchełki -> Python" i porzucił lekturę na długo przed jej rozpoczęciem.

Niemniej jednak jeżeli po tym przydługim wstępie przynajmniej jedna osoba nadal to czyta, przechodzę do meritum.

Problem jest stary jak pierwsze komputery, a właściwie nawet starszy. Chodzi o to, żeby znaleźć wszystkie ustawienia ośmiu hetmanów na 64-polowej szachownicy, takie, że żaden hetman nie znajduje się pod biciem żadnego innego.

Zagadnienie było już przewałkowane przez tysiące podręczników programowania komputerów, należy bowiem do kanonu zadań opartych o strukturę drzewiastą. No bo jak się dobrze zastanowić, rozwiązanie tego zadania to nic innego jak wędrówka po drzewie: ustawiamy pierwszego hetmana na pierwszym polu w pierwszym wierszu, następnie szukamy najbliższego niebitego pola w drugim wierszu i ustawiamy tam drugiego hetmana. Następnie szukamy najbliższego niebitego pola w trzecim wierszu... I tak dalej, aż do momentu, w którym okaże się, że albo w kolejnym wierszu nie da się dostawić hetmana, bo wszystkie pola tego wiersza się już bite (wtedy trzeba cofnąć ostatni ruch... albo dwa ostatnie.. i tak dalej), albo okaże się, że mamy na planszy osiem hetmanów spełniających warunki zadania - w takiej sytuacji zapisujemy rozwiązanie i znów cofamy odpowiednią ilość ruchów, żeby znaleźć kolejne rozwiązanie. Aż wreszcie wyczerpiemy wszystkie możliwości i zostaniemy z dziewięćdzięsięcioma dwoma poprawnymi rozwiązaniami (po eliminacji symetrii i obrotów można zejść do bodajże ośmiu, o ile dobrze pamiętam, ale to temat na kiedy indziej).

Proste?

W zasadzie tak.

Niech więc ktoś spróbuje zadanie rozwiązać na zwyczajnej szachownicy, ręcznie. Okaże się, że wcale nie takie proste jak by się mogło wydawać, ale w końcu uda się znaleźć przynajmniej jedno z 92 rozwiązań.

No i teraz pytanie: w ilu liniach kodu da się zrealizować algorytm rozwiązujący ww. zadanie, przy założeniu, że każda linia kodu to osobna instrukcja?

W czterdziestu?

W piętnastu?

A może w sześciu?

Otóż znalazłem niedawno rozwiązanie, które składa się dokładnie z pięciu linii kodu w Pythonie. I działa jak najbardziej poprawnie, chociaż zrozumienie DLACZEGO właściwie działa zajęło mi całkiem sporo czasu. Dziś podzielę się z ostatnim (ziewającym sugestywnie) Czytelnikiem tą wiedzą. Co mi tam.

Najpierw kod:

from itertools import permutations
kolumny = range(8)
for proba in permutations(kolumny):
  if 8 == len(set(proba[i] + i for i in kolumny)) == len(set(proba[i] - i for i in kolumny)):
    print (proba)

Teraz objaśnienie.

W pierwszej linii importujemy funkcję permutations (z biblioteki iterools). Biblioteka itertools jest pełna niespodzianek i jestem przekonany, że odkryję w niej jeszcze wiele radości. Póki co jednak tylko permutations, czyli generator permutacji.

W drugiej linii generujemy tablicę liczb od zera do siedmiu: [0,1,2,3,4,5,6,7] i zapisujemy ją w zmiennej kolumny. Każda liczba reprezentuje jedną kolumnę szachownicy.

W trzeciej linii iterujemy zmienną proba po wszystkich permutacjach zmiennej kolumny. Czyli po wszystkich możliwych rozstawieniach ośmiu hetmanów takich, że każdy wiersz planszy zawiera dokładnie jednego hetmana. Przykładowo, jeżeli zmienna proba ma wartosc [1,3,5,7,2,6,8,4], oznacza to, że hetmany stoją: w pierwszej kolumnie pierwszego wiersza, w trzeciej kolumnie drugiego wiersza, w piątej kolumnie trzeciego wiersza, w siódmej kolumnie czwartego wiersza i tak dalej aż do ostatniego wiersza, w którym hetman stoi w czwartej kolumnie.

Takie podejście gwarantuje, że nie trzeba sprawdzać wierszy ani kolumn (żadne dwa hetmany nie mają możliwości znaleźć się w tej samej kolumnie ani w tym samym wierszu). Pozostaje sprawdzić przekątne.

I to właśnie odbywa się w linii numer cztery, której zrozumienie zajęło mi dziś najwięcej czasu. Idea jest w sumie całkiem prosta: dla każdego hetmana wyliczamy osiem pól przekątnej "z góry z lewej w prawo w dół" (proba[i] + i for i in kolumny) oraz osiem pól przekątnej "z góry z prawej w lewo w dół" (proba[i] - i for i in kolumny). Następnie sprawdzamy, czy ilość UNIKALNYCH wartości każdej z tych współrzędnych wynosi osiem. Jeżeli operator SET wyeliminuje duplikaty, w wyniku otrzymamy mniej niż osiem elementów. Będzie to oznaczało, że przekątne idące w którąś ze stron częściowo pokrywają się, a więc, że hetmany w danej permutacji nie spełniają warunków zadania.

Jak ktoś chce, może sobie to rozrysować w Excelu (jak tak zrobiłem, żeby faktycznie załapać ideę). System działa bez pudła.

Jedyna wada tego rozwiązania jest taka, że - w odróżnieniu od "klasycznych" algorytmów, w których "wędrujemy" po kolejnych opcjach oraz "wycofujemy" się natychmiast po stwierdzeniu sytuacji, w której jeden z hetmanów bije innego, tutaj sprawdzamy pracowicie wszystkie permutacje. Na przykład pierwsze permutacje startują od [1,2,...], a więc dwa hetmany stojące na wspólnej głównej przekątnej. "Porządny" algorytm wyeliminowałby wszystkie poddrzewa startujące od [1,2...] za jednym zamachem, a tutaj - niestety - pracowicie sprawdzamy wszystkie te poddrzewa, chociaż z góry wiadomo, że żadne z nich nie spełni warunków.

Nudne, prawda?

[yop_poll id="20"]

https://xpil.eu/YscDH 📋