Króle, okręty i miny

Na szachownicy stoi tuzin króli i 10 pionków. Rozmieszczenie króli znamy (rys. 1), a celem zadania jest ustalenie pozycji pionków. Klucz do rozwiązania stanowi informacja: każdy król atakuje tyle pionków, ile wynosi liczba, którą jest oznaczony (pomijamy fakt, że pionki mogą szachować króle). Wytrawni główkołamacze od razu zauważą, że to rodzaj zadania zwany saperem, polem minowym lub skarbami – ale przedstawiony w szachowym entourage’u. W oryginale pionkami są miny lub skarby ukryte w polach otaczających cyfry. Łamigłówka znana jest od blisko 30 lat. Wymyślona przez Czechów, na szerszym forum po raz pierwszy pojawiła się w roku 1993 na 2. Łamigłówkowych Mistrzostwach Świata w Brnie.

Na tej samej imprezie debiutowało podobne zadanie, które także można przenieść na szachownicę, a w konkretnym przypadku wystarczy nieco zmodyfikować sytuację z rys. 1: usuwamy siedem króli z cyframi, a pięć pozostałych zastępujemy wieżami, nie zmieniając cyfr (rys. 2). Teraz także chodzi o wskazanie pozycji pionków – w tym przypadku nie wiadomo, ilu – z których każdy atakowany jest przez co najmniej jedną wieżę. Liczba na wieży oznacza, ile pionków jest przez nią atakowanych. Należy jednak uwzględnić drobne odstępstwo od reguł szachowych: wieża atakuje każdy pionek stojący w rzędach (wierszu i kolumnie), na których przecięciu się znajduje, a więc także taki, który jest zasłonięty przez inny pionek. Ponadto obowiązuje dodatkowy warunek: musi być zachowany dystans, czyli żadne dwie bierki – wieża i pionek lub dwa pionki – nie mogą znajdować się na sąsiednich polach, także stykających się tylko rogiem. W oryginale wieże są latarniami morskimi, a pionki oświetlanymi przez nie statkami zakotwiczonymi na polach diagramu-akwenu.

Zadanie królewskie (rys. 1) w pierwszej chwili może się wydać trudne, bo na początku brak „pewniaków”, czyli pól, w których powinien pojawić się jakiś pionek. Jeśli jednak wpaść na właściwą metodę (warto spróbować), rozwiązywanie okaże się całkiem proste. Takie zadania w wersji minerskiej są dość popularne, zwłaszcza że ich protoplastą jest klasyczna gra komputerowa saper z roku 1989. Natomiast łamigłówki wieżowo-latarniowe są mniej znane, zajmiemy się więc nieco bliżej kulisami ich rozwiązywania.

Początek jest czysto manualny i schematyczny – należy wykreślić pola, które muszą pozostać puste. Są nimi oczywiście te, które otaczają wieże, oraz te, których żadna wieża nie atakuje. Po tej czynności aktywna część diagramu na rys. 2 znacznie się zmniejszy (rys. 3). Część ta obejmuje atakowane przez konkretne wieże pasy pól (kilka pasów oznaczono różowymi prostokątami na rys. 3), a więc podejrzane o „ukrywanie” pionków. Zwykle zamiast podejrzenia mamy pewność, choć z reguły początkowo nie można wskazać konkretnego pola z pionkiem. Pewność bywa jednak wystarczająca, aby wykreślić kilka pól w sąsiednich pasach.

Na rys. 4 znajdują się pasy złożone z 1≤p≤5 pól, a w każdym z nich powinien pojawić się przynajmniej jeden pionek. Jeśli p=1, to pionek obsadza jedyne pole, a w sąsiednich pasach znikają po trzy pola (a). Gdy p=2, to na razie nie wiadomo, na którym polu zagości pionek, ale niezależnie od tego, gdzie się znajdzie, można wykreślić po dwa pola z sąsiednich rzędów (b). Dla p=3 sytuacja jest podobna, jeżeli na przydział pola czeka tylko jeden pionek. Wtedy w każdym sąsiednim pasie do wykreślenia będzie jedno pole – sąsiednie względem każdego z trzech pól oferowanych pionkowi (c). Jeżeli jednak w tym pasie muszą się znaleźć dwa pionki, to ich ulokowanie jest jednoznaczne, a w sąsiednich pasach ubywa po pięć pól (d). Przy p=4 i obecności tylko jednego pionka nic się nie da zrobić, ale jeśli na miejsce czekają dwa, to rezultatem będzie wykreślenie czterech pól w obu sąsiednich pasach (e). Wreszcie gdy p=5, to sytuacja ulega niewielkiej zmianie, gdy na przydział czekają dwa pionki (f), albo radykalnej, gdy są trzy – wtedy meldują się wszystkie i wykreślonych zostaje po siedem pól w sąsiednich pasach (g). Analizując coraz dłuższe pasy, łatwo ustalić, że największa liczba pionków k_p, które można umieścić w pasie złożonym z p pól równa jest liczbie liczb nieparzystych w zbiorze p początkowych liczb całkowitych dodatnich. Liczby k_p tworzą więc ciąg: 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, … , czyli k_p=?p/2? – nawiasy kwadratowe bez dolnej kreseczki oznaczają tzw. sufit, tzn. konieczność zaokrąglenia liczby w nawiasach w górę, jeżeli nie jest całkowita.

Na marginesie warto zauważyć, że „powtórkowy” ciąg pojawia się także przy innych rekreacyjnych okazjach. Jeśli na przykład na liniach tworzących siatkę kwadratową, o jednostkowym boku kwadracika siatki, będziemy rysować spiralną linię łamaną (tak powstaje tzw. spirala Ulama), to długości kolejnych odcinków tej spirali będą kolejnymi liczbami ciągu (rys. 5). Inny przykład: jeśli mamy zapłacić za coś p złotych monetami jedno- i dwuzłotowymi (p≥3, kwota p nie może się składać z samych złotówek lub samych dwuzłotówek), to różnych sposobów zapłaty także jest k_p=?p/2?.

Wracając do wież i pasów, na rys. 3 łatwo zauważyć, że w każdym z dwóch 2-polowych pasów atakowanych przez górną wieżę z dwójką (b7, b8 i g5, h5) musi znaleźć się po jednym pionku, zatem odpowiednie pola sąsiednich pasów wypadną z gry, jak na rys. 4b. To z kolei spowoduje, że w zasięgu dolnej dwójki znajdzie się tylko pas e2-h2 i będzie można wykreślić sąsiednie pola zgodnie z wzorcem 4e. Dalej zaczyna się lokowanie pewniaków – najpierw na polach a1, e2, e6 i e8, a potem na b7, g2 i g5. I to koniec (rys. 6).

Szachowa oprawa zadania jest nietypowa, zarówno jeśli chodzi o figury, jak i o szachownicę 8×8. Tradycyjna i najczęstsza forma jest taka, jak w pierwszych zadaniach sprzed 28 lat: diagram-akwen 10×10 z umieszczonymi w niektórych polach latarniami morskimi, a praktycznie cyframi, oznaczającymi liczbę statków oświetlonych przez każdą latarnię. Standardem jest zachowanie dystansu – pola obsadzone przez statki nie mogą się stykać, nawet rogiem – ze sobą, a także z polami, na których są latarnie. Zmienna bywa natomiast wielkość akwenu oraz dodatkowe warunki.

W zadaniu z rys. 2 dodatkowy warunek brzmi: każdy statek oświetlony jest przez co najmniej jedną latarnię. W debiutanckich zadaniach z Mistrzostw w Brnie ten warunek uzupełniony był drugim: podano liczbę statków do ujawnienia. W późniejszych zadaniach zwykle występuje tylko drugi warunek. Warto się zastanowić nad obydwoma warunkami i nad zależnością między nimi. Inaczej mówiąc, czy i kiedy wystarcza podanie jednego z nich (którego?) albo czy może być tak, że konieczne będzie podanie obu – na przykład łącznie w postaci: oświetlony jest każdy z 10 statków – aby było rozwiązanie, oczywiście jedno.

Gdyby na diagramie 8×8 znajdowała się wyłącznie jedna latarnia, to zadanie formalnie miałoby sens tylko z dwoma połączonymi warunkami: wszystkie statki są oświetlone, a ich liczba jest największą z możliwych, równą X. Jednak ponadto, aby było jedno rozwiązanie, latarnia musiałaby stać na właściwym polu, na przykład b2, jak na rys. 7 z rozwiązaniem (latarnia – cyfra, statki – kółka). Takie „właściwe” pola są jeszcze trzy – położone symetrycznie względem b2, czyli b7, g2 i g7 – bo tylko w tych przypadkach latarnia oświetla dwa pasy 5 pól, na których można jednoznacznie ulokować po 3 statki, czyli X=6.

Na brneńskich Mistrzostwach były dwa zadania (rys. 8) – oba z dwoma warunkami. Potem okazało się jednak, że wystarczyłby jeden: każdy diagram zawiera 10 statków. To kluczowa, konieczna i dostateczna informacja, umożliwiająca zastosowanie w obu zadaniach prostej logiczno-rachunkowej metody rozwiązywania. Na rys. 8 są już wstępne oznaczenia: krzyżyki w polach, które nie mogą zawierać statków, czerwone kropki w polach oświetlanych tylko przez jedną latarnię.

Wspomniana prosta metoda zaczyna się od dodania wszystkich latarniowych liczb. W obu zadaniach suma wynosi 17. Teraz warto zauważyć, że każdy statek trafiony jest światłem jednej lub dwu latarń, bo w każdym rzędzie (wierszu lub kolumnie) stoi co najwyżej jedna latarnia. Jeśli przyjmiemy, że statków trafionych przez jedną latarnię jest x, a trafionych przez dwie y, to z elementarnego układu dwu równań z dwiema niewiadomymi

x + 2y = 17

x + y = 10

wynika, że x=3, y =7. Zatem na rys. 8 w każdym diagramie tylko w trzech polach z czerwonymi kropkami pojawią się statki. Na rys. 8a te trzy pola ujawniane są natychmiast jako pewniaki (b4, d9, f9), zatem pozostałe pola z kropkami można przekreślić (rys. 9a). Dalsza droga do celu jest bardzo prosta, a zaczyna się od obsadzenia statkami kratek a2, c6, i6.

Natomiast na rys. 8b do zamiany trzech kropek na statki dochodzi się stopniowo, w trakcie początkowego etapu typowego sposobu rozwiązywania, czyli oznaczania kółek i krzyżyków w jedynych możliwych polach. Przebieg tego etapu jest następujący:

1) Ο – g8, i6, i10 (pierwsza kropka).

2) × – a2, a4 (wg rys. 4f), g9, h10, j6, j10 oraz d6, e6, g4, g10 (bo górna dwójka jest już „obsłużona” statkami na g8 i i6).

3) Ο – b2, f2 (druga kropka), j2, h4.

4) × – b4 i f4 (bo dolna dwójka została już obsłużona statkami na h4 i j2), a1, a3, a9, b1, b3, c1, e1, f1, f3, j1.

5) Ο – b5 (trzecia kropka)

Teraz pozostałe kropki można przekreślić (rys. 9b), po czym dwa ostatnie statki automatycznie wpływają na swoje miejsca – b9 i d7.

Czy warunków dodatkowych może w ogóle nie być? Wszystko zależy oczywiście od liczby i rozmieszczenia latarń oraz wartości przyporządkowanych im liczb. Jeśli latarnia występuje w każdym rzędzie, to warunek (1), aby oświetlone były wszystkie statki, traci sens, bo staje się koniecznością. Wtedy przy danym rozmieszczeniu latarń liczby na nich łatwo tak dobrać, że w rozwiązaniu wystąpi konkretna liczba statków, czyli nie będzie potrzebny także warunek (2), określający liczbę latarń (zakładamy, że nie korzystamy z latarń zerowych, którymi bardzo łatwo wymusić jednoznaczność). Przykład z 9 latarniami na rys. 10a.

Gdy liczba latarń maleje, zwiększa się obszar niejednoznaczności, w którym mogą kotwiczyć nieoświetlone statki, a wtedy przydaje się warunek (1). Sposobem na pominięcie tego warunku są duże liczby latarniowe. Mimo to w całkiem bezwarunkowym zadaniu na akwenie 10×10 prawdopodobnie najmniejszą liczbą latarń jest 6 – przykład na rys. 10b. Oba przykłady warto rozwiązać jako ćwiczenie przed zmaganiami z zadaniami konkursowymi.

Zadania

1. Na nieco większym niż dotąd akwenie (11×11) jest 10 latarń (rys. 11). Reguły są standardowe (zachowanie dystansów), a dodatkowych warunków brak, czyli nie wiadomo, ile jest statków i czy każdy jest oświetlony. Jako rozwiązanie końcowe wystarczy podać liczbę wszystkich statków.

2. Dotychczas każdy statek zajmował jedną kratkę, czyli był – zgodnie z nazwą przyjętą w grze w bitwę morską – 1-masztowcem. Tym razem flota składa się z różnych statków, także 2- i 3-masztowców. Wszystkich jest 10 umieszczonych pod akwenem (rys. 12), na którym należy je rozmieścić zgodnie ze standardowymi regułami, a więc statki powinny zachowywać dystans między sobą i latarniami. Liczba oznacza, ile segmentów statków oświetla dana latarnia. Jeśli w tym samym rzędzie stoją dwie latarnie, to żadna nie blokuje światła drugiej, czyli każda sięga okrętu swoim światłem tak, jakby stała w rzędzie sama. Gwoli jasności nad diagramem znajduje się mini-przykład. W rozwiązaniu wystarczy podać pozycje (współrzędne) czterech 1-masztowców.

3. Skoro latarnik jest szachistą, zastąpienie latarń figurami szachowymi nie powinno dziwić. Na diagramie (rys. 13) należy rozmieścić nieco inną flotę niż w zadaniu 2, ale w podobny sposób, tzn. z zachowaniem dystansu między statkami, ale – uwaga – z figurami statki mogą, a w przypadku króla nawet muszą sąsiadować. Każda figura powinna „oświetlać” (atakować) dokładnie cztery statki – po jednym każdego rodzaju, przy czym – w przeciwieństwie do latarń – „światło” hetmana, wieży i gońca sięga tylko pierwszego z dwu lub więcej statków stojących na linii ataku (na przykład w małym przykładzie nad diagramem hetman „oświetla” tylko segment b5 3-masztowca, a nie sięga 1-masztowca na d3). Niebieska liczba nad lub obok rzędu oznacza, ile kratek w tym rzędzie zajmują statki. W rozwiązaniu wystarczy podać pozycje 1-masztowców.

Rozwiązania prosimy nadsyłać do 31 października br. pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 10/21. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Michio Kaku Boskie równanie. W poszukiwaniu teorii wszystkiego ufundowaną przez wydawnictwo Prószyński Media. 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 sierpniowego

1. Układając z płytek Trucheta kwadrat 2x2 można utworzyć 27 różnych wzorów – przy założeniu, że za jednakowe uznajemy dwa, z których jeden powstaje z drugiego w wyniku obrotu, lustrzanego odbicia lub zmiany negatyw-pozytyw. Wszystkie wzory na rys. 14

2. Liczba sposobów ułożenia z płytek Trucheta prostokątnej mozaiki m×n tak, aby trójkąty tego samego koloru nigdzie nie stykały się bokami (mozaiki, z których jedna powstaje z drugiej w wyniku obrotu lub odbicia lustrzanego uważamy za różne) – wyraża się wzorem 2^m+n.

3. 21/9 (kwadraty/prostokąty). Pełne rozwiązanie na rys. 15.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Rebekki Wragg Sykes Krewniacy. Życie, miłość, śmierć i sztuka neandertalczyków, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Bartosz Chroł, Roman Kusyk i Justyna Walicka – wszyscy z Warszawy, Janusz Niedźwiedzki z Zawiercia, Michał Różycki z Krakowa.