Wędrująca wieża czyli UCW z blokadami

Zapewne najbardziej znanym zagadnieniem matematyczno-szachowym jest to, które dotyczy rozmieszczenia na szachownicy ośmiu hetmanów – takiego, aby żadne dwa się nie atakowały. Ten klasyczny problem, przedstawiony w roku 1848 na łamach berlińskiego miesięcznika „Schachzeitung”, doczekał się po dwóch latach 12 rozwiązań, a kilkanaście lat później angielski matematyk James W. L. Glaisher dowiódł, że ów tuzin wyczerpuje liczbę ustawień całkowicie różnych, czyli z dokładnością do odbić i obrotów. Problem był więc rozwiązany, ale nieoczekiwanie stał się zalążkiem innego zagadnienia.

Przed niespełna wiekiem angielski autor zadań szachowych Thomas R. Dawson zauważył, że jedno i tylko jedno ze wspomnianych 12 ustawień hetmanów ma ciekawą własność – można na nim oznaczyć UCW, czyli Unikalny Cykl Wieżowy. UCW jest taką trasą obejścia wszystkich wolnych pól wieżą szachową, która stanowi linię łamaną zamkniętą, gości tylko raz w każdym polu, a co najistotniejsze – jest wyjątkowa, czyli przy danej liczbie i układzie wolnych pól jedyna możliwa. Na rys. 1 znajduje się to nieagresywne i szczególne, jako sprzyjające wyznaczeniu UCW (zielona linia), ustawienie 8 hetmanów. W ujęciu matematycznym UCW jest unikalnym cyklem Hamiltona – w tym przypadku w 56-wierzchołkowym grafie wieży, gdzie wierzchołkami są środki pustych pól.

Na szachownicy bez hetmanów, czyli w grafie z 64 wierzchołkami, całkowicie różnych wieżowych cykli Hamiltona jest 580 717 (przypadkowo liczba pierwsza). Cykl najskromniej łamany składa się z 16 odcinków prostych, najobficiej łamany – z 56 (symetryczne przykłady na rys. 2). Problemowe pytanie brzmi: czy na szachownicy (8×8) może pojawić się UCW przy liczbie zablokowanych pól mniejszej niż 8, jak na rys. 1?

Podstawowym warunkiem, który musi być spełniony dla kwadratu 2k×2k (tu k=4), jest parzysta liczba blokad – w dodatku rozmieszczonych tak, aby na ciemnych polach znalazło się ich tyle, ile na jasnych. Wówczas pozostaną także równe liczby wolnych pól ciemnych i jasnych, a równość ta jest warunkiem koniecznym (choć oczywiście nie dostatecznym) obecności UCW, ponieważ każde dwa kolejne pola na okrężnej trasie różnią się kolorem.

Odpowiedź na powyższe pytanie okazała się zaskakująca: UCW istnieje na szachownicy nie tylko przy liczbie hetmanów-blokad mniejszej niż 8, ale – co w pierwszej chwili wydaje się prawie niemożliwe – przy liczbie dwukrotnie mniejszej. Nawet z ustawienia na rys. 1 uda się usunąć 4 hetmany – bez ruszania pozostałych – tak, by na 60 wolnych polach pojawił się jedyny możliwy cykl wieżowy (rys. 3).

Po tym niezwykłym odkryciu szachowi matematycy zaczęli zgłębiać temat i ustalili, że całkowicie różnych ustawień czterech blokad na szachownicy, generujących UCW, jest 14 – wszystkie można przedstawić na trzech diagramach (rys. 4). Na każdym czerwoną linią połączone są dwie alternatywne pozycje niektórych blokad – na pierwszym rysunku trzech, co w sumie daje 8 ustawień, na drugim dwóch (4 ustawienia), na trzecim jednej (2 ustawienia) – czyli w sumie 14. Zielone linie są fragmentami UCW, które można oznaczyć na każdym diagramie niezależnie od alternatywnych pozycji blokad.

Ponieważ nie jest znany dowód, że 14 to maksimum, więc odkrycie jakiegoś nowego ustawienia trudno wykluczyć. Jest natomiast dowód tego, co intuicyjnie nie budzi wątpliwości: żaden sposób umieszczenia na szachownicy tylko 2 hetmanów nie skutkuje pojawieniem się UCW. Dość łatwo bowiem wykazać, że w narożnej ćwiartce szachownicy (kwadrat 4×4) musi znaleźć się blokada, aby przebieg trasy w tym obszarze był jednoznaczny. Co prawda nie jest to zbyt eleganckie, bo wymaga przenalizowania wszystkich możliwych trasowań w ćwiartce, by stwierdzić, że zawsze znajdą się przynajmniej dwa takie, których końce wypadną w tych samych kratkach. Dwa przykłady takiej dwoistości – z dwoma i z sześcioma końcami – przedstawione są na rys. 5. Sposobem na unikalność jest więc wstawienie blokady.

Naturalnym rozwinięciem tematu UCW jest wzbogacenie asortymentu plansz – choćby o wszystkie kwadratowe, a praktycznie o kwadratowe diagramy różnej wielkości. Chodzi przede wszystkim o ustalenie minimalnych liczb blokad L(b), generujących UCW na planszach n×n. Wartości dla początkowych n są podane w poniższej tabeli.

Przypadki n≤3 są trywialne. Przykłady ustawienia blokad i przebiegu UCW dla pozostałych n objętych tabelą (oprócz n=8, którego dotyczą rys. 3 i 4) znajdują się na rys. 6. Jak widać, kolejnym nieparzystym n odpowiadają w podanym zakresie wartości L(b)= n-2. Natomiast dla parzystych n L(b)=n/2, gdy n jest wielokrotnością 4 lub L(b)=n/2+1, gdy n nie jest wielokrotnością 4.

Dopiero przed kilkunastu laty japońscy autorzy zadań logicznych odkryli, że podane wzory na L(b) nie muszą sprawdzać się dla n>12. Na pewno od n=13 nieco się zmienia wzór dla nieparzystych n na L(b)=n-4. Proszę sprawdzić, że takie ustawienie 9 blokad na 169-polowym diagramie, jak na rys. 7, umożliwia wyznaczenie tylko jednego cyklu wieżowego, czyli UCW. Czy nowy wzór działa dla wszystkich nieparzystych n>12, a podane wyżej dwa wzory są słuszne dla wszystkich n parzystych – nie wiadomo, bo dotąd nikt nie zgłębiał tego tematu.

Warto zauważyć, że dla n>8 blokady lokowane są przy brzegach diagramu, a wnętrze „zieje pustką” – ekstremalną dla n=12. Wydaje się więc, że to czyste wnętrze powinno umożliwiać poprowadzenie wielu różnych dróg Hamiltonowskich. Dopiero w trakcie wyznaczania cyklu okazuje się, że „pole manewru” jest niewielkie, a w ostatecznym efekcie okazuje się, że alternatywy brak.

Przykładowe ustawienia na rys. 6 nie są oczywiście jedynymi dla konkretnych liczb blokad, ale dokładne liczby całkowicie różnych ustawień dla poszczególnych n>8 są znane tylko jako hipotezy (np. dla n=10 znanych jest 20).

* * *

Temat UCW zainspirował osoby układające łamigłówki. Na pomysł tych formalnie najprostszych wpaść nietrudno – właściwie jest to łamigłówkowy „samograj” z następującą instrukcją: w kwadracie n×n niektóre kratki są zaczernione, czyli tworzą blokady; należy narysować UCW obejmujący wszystkie pozostałe kratki. Po raz pierwszy takie zadania pojawiły się w prasie amerykańskiej przed 40 laty pod niezbyt oryginalną nazwą „Pętla” (Loop). Logika pętli jest dość prosta – wynika z jej podstawowej własności: linia przechodzi przez dwa boki każdego pola. W związku z tym rysując cykl, wystarczy oznaczać i odpowiednio łączyć jego fragmenty, czyli krótkie linie:

(a) wychodzące z pól, które mają tylko dwie drogi wyjścia;

(b) których brak prowadziłby do przedwczesnego utworzenia pętli.

Z punktem (a) ściśle wiąże się warunek, aby w trakcie trasowania nie rysować linii, które powodowałyby pojawienie się „ślepych zaułków”, czyli pól z tylko jednym wyjściem. Natomiast w związku z punktem (b) należy uważać, aby nie łączyć linii, zamykających jakąś mniejszą pętlę – a o taką pomyłkę nietrudno przy większych diagramach.

Uwzględnianie podanych wskazówek ilustruje przykład na rys. 8. Na lewym rysunku zielone linie wynikają z warunku (a), natomiast niebieska jest konieczna ze względu na warunek (b) – gdyby jej nie było, to przez pole A przechodziłby poziomy odcinek, zamykający małą pętlę. Z kolei czerwony odcinek jest wykluczony, bo połączenia jego końca (B) z zieloną linią nad nim uczyniłoby pole C „ślepym zaułkiem”, a połączenie z zieloną linią pod nim owocowałoby małą pętlą. Na prawym rysunku oznaczony jest końcowy efekt wypełniania przedstawionej części diagramu fragmentami UCW. Oczywiście wnioskowanie o konieczności oznaczania albo unikania jakichś linii nie zawsze jest tak proste – czasem wymaga przeanalizowania następstw więcej niż jednego kroku.

* * *

Właściwie dopiero na przełomie XX i XXI wieku, tuż przed „epidemią” sudoku, zaczęły się pojawiać bardziej oryginalne i ambitniejsze rodzaje zadań logicznych z blokadami okrążanymi przez UCW. Oryginalność polega ogólnie na tym, że blokady nie są w nich ujawniane wprost – ich rozmieszczenie, wszystkich lub niektórych, trzeba samemu ustalić na podstawie dodatkowych informacji. W trakcie ujawniania blokad należy oczywiście pamiętać, że przez wszystkie wolne pola między nimi powinna przebiegać trasa wieżowa – i to jedyna możliwa.

Najpopularniejsze są trzy rodzaje kluczowych informacji umożliwiających lokowanie blokad. Wszystkie wymyślono w Japonii, co wiąże się z nazwami zawierających je zadań: koburin, heyarin i yajirin. Obecna we wszystkich nazwach końcówka -rin oznacza linię, a początkowe cząstki słowotwórcze wiążą się z przeszkodą (kobu-), pomieszczeniem (heya-) lub strzałką (yaji-).

Koburin ma wiele wspólnego z łamigłówką zwaną saperem, wzorowaną z kolei na klasycznej jednoosobowej grze komputerowej o takiej samej nazwie. Każda liczba w diagramie wskazuje, w ilu polach sąsiadujących z polem z liczbą są blokady (czarne kratki). Sąsiedztwo oznacza tylko wspólny bok, więc liczbą może być 1, 2, 3 lub 4. Pola z liczbami także są blokadami, czyli UCW musi je omijać. Ponadto istotne są dwa warunki:

– pola z czarnymi blokadami nie mogą ze sobą graniczyć (bokiem);

– nie wszystkie czarne blokady muszą być wskazane liczbami.

Przykład koburin z rozwiązaniem – na rys. 9.

W drugim rodzaju zadania, czyli w heyarin, diagram podzielony jest na działki, a wszystkie blokady są ukryte. Kluczem do ich ujawnienia są kolory działek. Każdy kolor oznacza liczbę blokad, które powinny pojawić się w danej działce: w żółtej – zero, w zielonej – jedna, w niebieskiej – dwie, w różowej – trzy. Teoretycznie blokad w działce może być więcej, ale w praktyce zdarza się to bardzo rzadko – wówczas pojawia się dodatkowy kolor. Działka może być też biała – wtedy liczba blokad nie jest znana i trzeba ją samemu ustalić. Podobnie jak w koburin pola z blokadami nie mogą być sąsiednimi, czyli zakazane są prostokąty złożone z dwóch zablokowanych kratek. Przykład z rozwiązaniem – na rys. 10.

Trzeci typ zadania zwany yajirin (czyt. jadzirin) zawiera tzw. liczbostrzałki umieszczone w niektórych polach diagramu. Strzałka wskazuje kierunek, w którym w danym rzędzie należy ulokować tyle blokad, jaka liczba towarzyszy strzałce. Poza tym podobnie jak w koburin:

– pola z liczbostrzałkami także stanowią blokady, więc UCW powinien je omijać;

– pola z blokadami (czarnymi) nie mogą graniczyć bokami;

– nie wszystkie czarne blokady muszą być wskazane przez liczbostrzałki.

W rozwiązaniu małego przykładu yajirin na lewym diagramie rys. 11 znajduje się jedna niewskazana blokada. Natomiast prawy diagram jest zadaniem treningowym – do rozwiązania przed zmierzeniem się z zadaniami konkursowymi.

Zadania

Objaśnienia czterech poniższych zadań znajdują się w artykule. Zadaniami są: pętla (rys. 12), koburin (rys. 13), heyarin (rys. 14) i yajirin (rys. 15). Heyarin jest wariantem jednobarwnym – zieleń oznacza, że w każdej działce powinna się znaleźć tylko jedna blokada. Jako końcowe rozwiązanie każdego zadania wystarczy podać, w ilu polach diagramu UCW się nie załamuje.

Rozwiązania prosimy nadsyłać do 31 sierpnia 2024 roku pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 08/24. Spośród autorów poprawnych rozwiązań przynajmniej trzech zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką popularnoanukową. Warunkiem udziału w konkursie jest zamieszczenie w e-mailu z odpowiedzią oświadczenia:

Zapoznałam/em się z regulaminem konkursu i akceptuję jego treść oraz wyrażam zgodę na przetwarzanie danych osobowych na potrzeby realizacji konkursu.

Regulamin konkursu jest dostępny na stronie www.swiatnauki.pl

***

Rozwiązania zadań z numeru czerwcowego

1. Czterema różnymi liczbami całkowitymi (a, b, c, d), spełniającymi dwie równości: a^b=c^d i b^a=d^c są a=2, b=–4, c=4, d=–2.

2. Podniesienie liczby A do potęgi 1000 na kalkulatorze umożliwiającym tylko mnożenie i dzielenie wymaga wykonania co najmniej 12 działań.

3. Najmniejszym iloczynem P>2 kolejnych liczb naturalnych, najmniej różniącym się od potęgi, jest 24=2×3×4=25–1.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę popularnoanukową otrzymują: Grzegorz Górzny z Wrocławia, Zbigniew Kapusta z Banina, Daniel Kłobuszewski i Szczepan Zdybowicz z Warszawy, Andrzej Żołyński z Zielonej Góry.

***

Marek Penszko, z wykształcenia inż. poligrafii, jest znawcą i popularyzatorem gier i rozrywek umysłowych, głównie matematyki rekreacyjnej. Współpracuje z wieloma czasopismami, m.in. pisze blog dla „Polityki”.