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 361

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 tak postępować ani dlaczego miałoby to być korzystne przy realizacji jego metody.

Dalej, nie określa on też, co robić, gdy mamy kilka kolumn o tej samej liczbie białych pól, tzn. w której z nich ustawiamy kolejną wieżę. Hawlicki nie określa również, na którym białym polu takiej kolumny ustawić wieżę, gdyby takich pól było więcej niż jedno. Z analizy większości rysunków zamieszczonych obok jego rozwiązania można jednak próbować wywnioskować, że przy tej samej liczbie białych pól w kilku kolumnach kolejna wieża ustawiana jest w pierwszej takiej kolumnie od lewej, przy czym wieżę tę ustawiamy na dopuszczalnym białym polu leżącym w tej kolumnie najniżej. Jednak rysunek towarzyszący rozwiązaniu15 zdaje się, niestety, przeczyć tej zasadzie. Poza tym Hawlicki nie realizuje chyba konsekwentnie swojego pomysłu, bo nie aktualizuje raz umieszczonych liczb w miarę dostawiania kolejnych wież i ubywania białych pól, na których można by ustawiać nowe wieże, co – jak się wydaje – mogłoby być przydatne w ramach jego metody.

W końcu Hawlicki nie mówi, kiedy powinien zakończyć się proces dostawiania kolejnych wież. W istocie metoda Hawlickiego prowadzi w pewnym sensie do „maksymalnych” rozwiązań, ignorując ewentualne rozwiązania „mniejsze”, które mogłyby pojawić się wcześniej, po drodze do owych rozwiązań „maksymalnych”. Rzeczywiście, w swojej metodzie Hawlicki w żadnym miejscu nie wspomina o tym, by po dostawieniu kolejnej wieży sprawdzić, czy uzyskana konfiguracja wież spełnia punkty 1°–4° zadania, tzn. czy stanowi jego rozwiązanie. Dlatego wydaje się, że jego docelowym zamiarem jest ustawienie wież we wszystkich kolumnach szachownicy, nawet jeśli nie jest to konieczne. Żeby się o tym przekonać, wystarczy zastosować metodę Hawlickiego do szachownicy, na której poza pierwszą, całkowicie białą kolumną jedynymi białymi polami są pola przekątnej.

Zasadnicza część metody rozwiązania Hawlickiego to ta, w której stara się on przekonać swoich Czytelników, że pomimo możliwych przeszkód w dostawianiu nowych wież – wszystkie białe pola w kolejnej kolumnie mogą już być atakowane poziomo przez uprzednio ustawione na szachownicy wieże – można tak zmodyfikować dotychczasową konfigurację wież, by móc kontynuować ich dostawianie na planszy, aż do zrealizowania rozwiązania. I choć w ujęciu przedstawionym w „Matematyce” z 1958 r.16 argumentacja Hawlickiego, która ma służyć temu celowi, jest dość mocno ograniczona, jako że polega tylko na przytoczeniu i przeanalizowaniu pojedynczego przykładu opartego na towarzyszących rozwiązaniu ilustracjach (rys. 93), to jest ona poprawna. Zilustrujemy to podobnie, jak zrobiliśmy to w przypadku analizy „rozwiązania” Paszkowskiego17, a więc „wypreparowując” z tekstu Hawlickiego kilka definicji i twierdzeń. Uprzedźmy jednak od razu Czytelnika, że w tym przypadku będzie to trudniejsze, gdyż o ile „rozwiązanie” Paszkowskiego polegało rzeczywiście głównie na nie całkiem ujawnionych, ale dość prostych do odtworzenia twierdzeniach, to rozwiązanie Hawlickiego jest w istocie prawie wyłącznie opisem metody, dość specyficznie wymyślonej na użytek zadania o wieżach.

DEFINICJA 1. Kolumnę szachownicy nazwiemy „zablokowaną”, jeżeli spełnione są następujące warunki:
a) w kolumnie tej nie stoi żadna wieża,
b) wszystkie białe pola tej kolumny są już atakowane poziomo przez dotychczas ustawione wieże.

Zauważmy, że jeśli podczas ustawiania wież w kolumnach zgodnie z metodą Hawlickiego przyjdzie nam ustawić kolejną wieżę właśnie w zablokowanej kolumnie, to ze względu na warunek b) powyższej definicji nie będziemy w stanie tego zrobić, nie naruszając warunku 3° zadania o wieżach. Taką sytuację nazwiemy za Hawlickim „przeszkodą”.

Wydaje się, że takie przeszkody uniemożliwiają uzyskanie rozwiązania metodą Hawlickiego. Jednak Hawlicki udowadnia, że z takimi przeszkodami możemy sobie poradzić, i pokazuje w istocie, jak to zrobić. W tym celu odróżnia on dwa rodzaje przeszkód. Pierwsze z nich są łatwiejsze do zlikwidowania – robi się to przez zmianę konfiguracji już ustawionych wież. Hawlicki nazywa takie przeszkody „usuwalnymi”. My nazwiemy je tu „usuwalnymi w drodze rekonfiguracji”. Ścisła definicja tego rodzaju przeszkód brzmi następująco:
DEFINICJA 2. Przeszkodę nazwiemy „usuwalną w drodze rekonfiguracji”, jeśli spełniony jest następujący warunek: w kolumnach, w których stoją wieże układu blokującego daną k...

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