Dołącz do czytelników
Brak wyników

Koło matematyczne

23 czerwca 2018

NR 32 (Maj 2018)

W sprawie rozwiązań zadania 494
O rozwiązaniu Hawlickiego

0 101

Gdy w 1957 roku Hugo Steinhaus opublikował w ramach „Konkursu zadaniowego” w „Matematyce”1 po raz pierwszy poniższe zadanie o wieżach na szachownicy, nie podejrzewał zapewne, że zadanie to – a właściwie jego rozwiązanie – będzie miało aż tak burzliwą historię. 

Wszystko zaczęło się jeszcze w 1958 r., gdy ukazała się książka Steinhausa Sto zadań1, w której zadanie o wieżach zostało opublikowane powtórnie, tym razem z rozwiązaniem. Niestety, bardzo szybko okazało się, że rozwiązanie to jest – delikatnie mówiąc – niepoprawne. Jeszcze bowiem w 1958 r. „Matematyka” w części z rozwiązaniami zadań z „Konkursu zadaniowego”2 opublikowała kolejne rozwiązanie zadania o wieżach, poprzedzone następującym komentarzem:

„Zadanie okazało się trudne. Z czterech nadesłanych rozwiązań trzy są niepoprawne. Również rozwiązanie S. Paszkowskiego, zamieszczone w książce prof. H. Steinhausa Sto zadań, nie jest pełne. Rozpatrzono w nim tylko dwa przypadki szczególne. Rozumowanie, które podajemy, jest oparte na odpowiedzi nadesłanej przez kol. Józefa Hawlickiego (Przemyśl)”.

Powyższy komentarz jest nazbyt łaskawy dla rozwiązania Paszkowskiego, co starałem się wykazać w moim niedawnym artykule, opublikowanym na tych łamach w listopadzie ubiegłego roku3. Rozprawiwszy się w ten sposób z pierwszym, nieudanym podejściem do rozwiązania zadania nr 494, przyszła obecnie pora na podobną, krytyczną analizę drugiego rozwiązania, tzn. rozwiązania Hawlickiego. Zaczniemy więc od przypomnienia treści zadania4: Wieże. Szachownica ma tyle wierszy co kolumn, ale różni się od zwykłej tym, że rozmieszczenie pól białych i czarnych może być dowolne, byle w każdej kolumnie było przynajmniej jedno białe pole i byle przynajmniej jedna kolumna była cała biała. Powiemy, że udało nam się ustawić wieże na szachownicy (a mamy dostateczny zapas wież, tak że ich nie zabraknie), jeśli spełnimy następujące warunki: 1° wieże stoją tylko na białych polach; 2° co najmniej jedna wieża stoi na szachownicy; 3° wieże nie atakują się wzajemnie (to znaczy nie stoją tak, by mogły się bić); 4° każde białe pole niezajęte przez wieżę, ale bite poziomo przez wieże, jest także pionowo bite przez jakąś wieżę.

Należy dowieść, że zawsze można ustawić wieże zgodnie z wymaganiami 1°, 2°, 3° i 4°.

Niestety, odmiennie niż miało to miejsce w przypadku „rozwiązania” Paszkowskiego, które zajmowało około jednej strony i miało trzy ilustracje, rozwiązanie Hawlickiego ma trzy bite strony tekstu plus siedem ilustracji, dlatego niecelowe byłoby przytaczanie go tu w całości i nie będziemy tego czynić. Niemniej, chociaż będziemy przytaczać jego istotne fragmenty, niezbędne do tego, by zrozumieć dalszą jego analizę, to dla Czytelnika może okazać się konieczne sięgnięcie po całość tego rozwiązania5.

Zacznijmy od zauważenia, że już na wstępie do swojego rozwiązania Hawlicki zapowiada w istocie algorytm prowadzący do ustawienia wież będącego żądanym rozwiązaniem. Rzeczywiście, pisze on: „Zadanie rozwiążemy, podając metodę ustawiania wież na szachownicy, taką że końcowy efekt jest zgodny z warunkami 1°, 2°, 3° i 4°”.

Biorąc pod uwagę fakt, że – jak to wykazałem i omówiłem gdzie indziej6 7 – zadanie Steinhausa jest przez swoje rozwiązanie bardzo blisko związane z jednym z klasycznych dziś twierdzeń kombinatoryki skończonej, mianowicie z tzw. twierdzeniem o małżeństwach Halla8, można by mieć nadzieję, że algorytm zaproponowany przez Hawlickiego może kryć w sobie zalążek jednego z powszechnie dziś znanych algorytmów znajdowania maksymalnych8 skojarzeń w grafach dwudzielnych9. Gdyby tak było, Hawlickiemu przypadłby w udziale zaszczyt bycia w wąskim gronie pionierów algorytmiki grafowej. Niestety, jego algorytm – o czym przekonamy się za chwilę – jest w zasadzie prostym algorytmem typu „na siłę” (ang. brute force): polega mianowicie na dostawianiu kolejnych wież, a więc na stopniowym konstruowaniu rozwiązania, z pewnymi modyfikacjami – choć nie całkiem z tym, co dziś nazywamy (klasycznym) wycofywaniem się, czyli nawrotami10 – w wypadku napotkania problemów, tzn. niemożności kontynuowania.

W przypadku zadania Steinhausa najprostszy algorytm typu „brute force”, mianowicie algorytm pełnego przeglądu wszystkich możliwości, jest bardzo łatwy do wymyślenia: zaczynamy od ustawienia pierwszej wieży na dowolnym białym polu pierwszej kolumny planszy. Następnie ustawiamy na tej planszy kolejne wieże w kolejnych kolumnach, oczywiście tak, by uniknąć sytuacji, kiedy atakują się one wzajemnie, tzn. ustawiamy je na białych polach w wierszach, w których nie stoi jeszcze żadna wieża (takie pole nazwiemy „dopuszczalnym”). Gdyby okazało się to niemożliwe, a więc gdyby w istocie okazało się, że dla kolejnej, nowej wieży nie ma już dopuszczalnych pól, a obecna konfiguracja wież nie stanowi jeszcze rozwiązania, to przestawiamy ostatnio ustawioną wieżę na inne dopuszczalne białe pole w tej samej kolumnie. Jeśli również dla tej wieży nie ma już takich pól, cofamy się dalej, tzn. zdejmujemy z planszy ostatnio ustawioną wieżę i staramy się przestawić – o ile to możliwe – wieżę przedostatnią itd. W ten sposób zrobimy systematyczny przegląd wszystkich możliwych, rokujących nadzieję ustawień wież na szachownicy i gdyby któreś z tych ustawień stanowiło rozwiązanie pierwotnego zadania Steinhausa, to w końcu na pewno na nie natrafimy.

Czytelnicy znający algorytmikę z łatwością rozpoznają w tym algorytmie klasyczny dziś algorytm przeszukiwania drzewa z nawrotami, zgodnie z zasadą „najpierw w głąb” (ang. DFS = Depth-First Search1112). Zauważmy dalej, że sam fakt istnienia algorytmu przeszukania przestrzeni potencjalnych rozwiązań nie gwarantuje, że takie rozwiązanie rzeczywiście istnieje. To wymaga odrębnego dowodu. Algorytm gwarantuje tylko, że jeśli rozwiązanie istnieje, to je znajdziemy, przynajmniej w teorii. „W teorii”, jako że nawet jeśli rozwiązanie takie istnieje, to w praktyce może nam zabraknąć czasu na jego praktyczne znalezienie metodą pełnego przeszukiwania.

Oczywiście, tak jak każdy prosty algorytm tego typu, daje się on łatwo zmieniać (zwykle – ulepszać) przez modyfikację zasady dostawiania nowych wież. Zamiast dostawiać te wieże jakkolwiek, byle tylko nie atakować wież już stojących, możemy np. dostawiać je tak, by atakować pionowo (możliwie liczne) białe pola już atakowane poziomo. Uważny Czytelnik znający algorytmikę ponownie zauważy z łatwością, że ta konkretna modyfikacja to powszechnie dziś znana „zachłanność”1314 danego algorytmu.

W swoim rozwiązaniu Hawlicki proponuje jednak inną, następującą modyfikację zasady dostawiania nowych wież: przed rozpoczęciem ustawiania wież na szachownicy umieszcza on nad każdą kolumną liczbę białych pól leżących w tej kolumnie, po czym dostawia kolejne wieże w kolumnach, w których jest najmniej takich pól. Niestety, nie wyjaśnia, dlaczego chce ta...

Pozostałe 70% treści dostępne jest tylko dla Prenumeratorów.

Co zyskasz, kupując prenumeratę?
  • 6 wydań czasopisma "Matematyka"
  • Dostęp do wszystkich archiwalnych artykułów w wersji online
  • Możliwość pobrania materiałów dodatkowych, testów i zadań
  • ...i wiele więcej!
Sprawdź

Przypisy