Zakazany kwadrat

Pokratkowany kwadratowy diagram jest „miejscem akcji” większości współczesnych łamigłówek logicznych, także tej najpopularniejszej, czyli sudoku. Sporą grupę stanowią wśród nich takie, które polegają na dzieleniu diagramu wzdłuż boków kratek na części. Zapewne najbardziej znanymi z tej grupy, uchodzącymi za niemal „klasyczne”, są cztery rodzaje zadań o nazwach, podobnie jak sudoku, japońskojęzycznych, wskazujących na ich pochodzenie – shikaku, fillomino, nurikabe i yin-yang. W regułach dwóch ostatnich występuje specyficzny warunek, obecny także w kilkunastu innych, mniej znanych rodzajach łamigłówek: niektóre lub wszystkie wydzielane części nie mogą zawierać kwadratu 2×2 kratki.

W nurikabe (nazwa dotyczy konkretnego obiektu, ale można ją przetłumaczyć jako „kolorowanie ściany”) diagram dzielony jest na wielokąty – „stawy” i „groblę”. Klucz do rozwiązania stanowią pola z liczbami – każde jest częścią stawu złożonego z tylu pól, jaka jest wartość liczby. Stawów jest dokładnie tyle, ile liczb, więc ujawniony jest fragment każdego (albo cały, jeśli liczbą jest jedynka). Stawy mogą się stykać tylko rogami, a rozdzielone są groblą utworzoną z pól, które należy zaczernić. I właśnie grobla powinna tworzyć wielokąt bez kwadratu 2×2 – jeden spójny i zwykle mocno rozgałęziony. Zadanie polega na zaczernieniu grobli i zaniebieszczeniu stawów.

Tok rozwiązywania przykładowego zadania (rys. 1a) obrazuje elegancką, klarowną logikę ujawniania stawów i grobli: najpierw (rys. 1b) zaczerniane są pola rozdzielające stawy (A), potem te, których stawy na pewno nie sięgną (B), oraz zaniebieszczane te, których stawy muszą sięgnąć, aby miały właściwą wielkość (C); a wreszcie te, których stawy powinny sięgnąć, aby na grobli nie pojawił się kwadrat 2×2 (D). Na koniec nietrudno zadbać o rozmiary wszystkich stawów oraz o spójność grobli – aż do wypełnienia całego diagramu (rys. 1c). Oczywiście, droga do rozwiązania bywa czasem bardziej wyboista, wymagająca nawet błądzenia, czyli korzystania z metody prób i błędów.

W yin-yang, drugim „klasycznym” rodzaju zadania z zakazem 2×2, kwadratowe ograniczenie dotyczy każdej z dwóch części, na które dzielony jest diagram. W praktyce kratki wypełnia się białymi i czarnymi kółkami (niektóre z nich są na początku ujawnione) tak, aby pola z białymi wyznaczały kształt jednej części, a pola z czarnymi – kształt drugiej. W przeciwieństwie do nurikabe metody rozwiązywania yin-yang bywają dość skomplikowane (ich opis można znaleźć w „Umyśle giętkim” ze stycznia 2016 roku), ale przykład na rys. 2a jest raczej prosty, zwłaszcza jeśli skorzysta się na początku z tzw. metody brzegowej (zwykle skutecznej, aczkolwiek nie zawsze), polegającej na łączeniu znajdujących się przy brzegu par kółek jednakowego koloru ciągiem takich samych kółek biegnącym wzdłuż brzegu (rys. 2b). Dalej wystarczy uwzględniać warunek 2×2 i spójność każdej części, aby bez trudu dotrzeć do celu (rys. 2c).

We wszystkich rodzajach zadań z zakazem 2×2 korzyść jest oczywista – zakaz ten zapewnia jednoznaczność, czyli unikatowe rozwiązanie. Jeśli nie wprowadziłoby się takiego ograniczenia, grobla na rys. 1c mogłaby być miejscami grubsza, a rozwiązań byłoby aż 88 (proszę sprawdzić), zaś w yin-yang zapanowałby kompletny chaos.

Zarówno grobla, jak i obydwie części w yin-yang są wielokątami złożonymi z kratek, czyli małych kwadratów, i ogólnie zwane są poliminem. W zależności od liczby kwadratów (k), tworzących dane polimino, w nazwie zmienia się cząstka przed „-mino”. Jest więc jedno monomino i jedno domino, dwa trimina, pięć tetromin, 12 pentomin (rys. 3) itd., aż do 4665 10-kwadratowych dekamin. Dalej, gwoli jasności, korzysta się zwykle z liczb zamiast przedrostków. Grobla na rys. 1c jest więc 23-minem (z przedrostkiem byłaby trikozaminem), a w rozwiązaniu yin-yang (rys. 2c) pojawiają się czarne 16-mino i białe 20-mino.

Większość małych polimin na rys. 3 nie zawiera kwadratu 2×2. Nie ma go w 4 tetrominach oraz w 11 pentominach, czyli w ponad 90% tego kompletu złożonego z 12 figur. W przypadku liczniejszych kompletów większych polimin udział tych bez kwadratu 2×2 stopniowo maleje, gdy wzrasta liczba k, ale nie wiadomo do jakiej wartości. Wśród dekamin stanowią one już 61%. Wydaje się jednak, że od dostatecznie dużego k tempo malenia tego udziału wyraźnie zwalnia, co wiąże się pośrednio z różnicą między groblą w nurikabe, a dwiema częściami w yin-yang. Wprawdzie polimina w obu zadaniach należą do tej samej rodziny, którą wyróżnia brak kwadratu 2×2, ale w istocie są to raczej dalsi krewni.

Części w yin-yang są poliminami o największym obwodzie dla danego k równym 2k+2. Część wyznaczona przez 16 czarnych kółek na rys. 2c ma więc obwód 2×16+2=34, a obwód części pokrytej 20 białymi kółkami wynosi 2×20+2=42 (jednostką jest oczywiście bok kratki). Wiąże się to z faktem, że każda część stanowi jakby układ alejek, na których każde dwa kwadraty łączy tylko jedna droga. Inaczej mówiąc, nigdzie nie ma trasy okrężnej.

Grobla na rys. 1c także ma tę własność, ale w tym rodzaju zadania tak być nie musi, o czym łatwo się przekonać, rozwiązując nurikabe z rys. 4. Kto dotrze do rozwiązania, zauważy, że choć na grobli, która jest 33-minem, nie ma kwadratu 2×2, to tworzy ona kilka tras okrężnych, a jej obwód wyraża się wzorem: 2k-2s+2, gdzie s jest liczbą stawów szczelnie przez groblę otoczonych (żaden nie styka się z innym nawet tylko rogiem; w tym wzorze grupa stawów stykających się rogami uważana jest za jeden staw), czyli w tym przypadku (s=3) wynosi 66–6+2=62.

Można by sądzić, że w yin-yang trasa okrężna również nie jest wykluczona, ponieważ teoretycznie jedna poliminowa część może całkowicie otaczać drugą – wewnętrzną. Jednak taka sytuacja jest incydentalna i osobliwa, bo wówczas, aby było jedno rozwiązanie, należałoby na początku ujawnić wszystkie kółka znajdujące się przy brzegu diagramu i byłyby to oczywiście kółka jednego koloru należące do części otaczającej, zewnętrznej. Bez takiego wstępnego pełnego okrążenia kolor dowolnego kółka brzegowego (oprócz narożnych) mógłby „oscylować” między białym a czarnym bez sprzeczności z regułami zadania. Poza tym, aby istniało rozwiązanie, musiałby być spełniony jeszcze jeden warunek: nieparzysta powinna być liczba pól diagramu, czyli w diagramie n×n n byłoby nieparzyste.

To konieczne, bo przy parzystym n liczba węzłów siatki kwadratowej wewnątrz diagramu jest nieparzysta, a skoro linia rozdzielająca części musi (w związku z brakiem kwadratu 2×2) przebiegać przez wszystkie te węzły, przez każdy tylko raz, więc obwód wewnętrznego polimina także wyrażałby się liczbą nieparzystą – a to niemożliwe, bo liczba boków kratek na obwodzie polimina jest zawsze parzysta. W nurikabe takie ograniczenia nie występują, ponieważ fragmenty brzegu grobli mogą znajdować się na brzegu diagramu, a ponadto kwadraty 2×2 w stawach nie są wykluczone, czego przykładem jest (a właściwie będzie) rozwiązanie pierwszego zadania konkursowego.

Układ dwu części w yin-yang, w którym jedna część całkowicie otacza drugą, byłby do przyjęcia, gdyby zakaz 2×2 dotyczył tylko części wewnętrznej. Wówczas jednak byłoby to właściwie odmienne zadanie, przypominające inną dość popularną łamigłówkę – slitherlink, czyli pokropkę, a więc stanowiące jakby jej odmianę. Kluczem do wyznaczenia linii łamanej zamkniętej, w przybliżeniu odpowiadającej brzegowi wewnętrznej części w yin-yang, są w pokropce zamiast ujawnionych kółek liczby – 0, 1, 2, 3. Każda oznacza, ile boków kratki z daną liczbą powinno stanowić fragment wykreślanej linii. W rozwiązaniu przykładu na rys. 5 uwzględniony jest zakaz braku kwadratu 2×2 wewnątrz pętli. Łatwo zauważyć, że po pominięciu tego zakazu pojawi się więcej rozwiązań (ile konkretnie?).

Jak wynika z powyższych rozważań, polimina można podzielić na dwie grupy, uwzględniając drogi, łączące środki tworzących je kwadratów, stykających się bokami (czerwone linie na rys. 6; k=15, czyli 15-mina). Jedne zawierają układ mniej lub bardziej rozgałęzionych dróg, nigdzie nietworzących cyklu (np. rys. 6a); w drugich występuje przynajmniej jeden cykl. W poliminach bez cyklu nigdy nie ma kwadratu 2×2, bo jest on cykliczny. Natomiast w poliminach z cyklem kwadrat 2×2 może się pojawić (rys. 6b), ale nie musi (rys. 6c).

Wspomniane na początku „klasyczne” fillomino też może być – podobnie jak pokropka – uzupełnione warunkiem wykluczającym kwadrat 2×2. W tym rodzaju zadania diagram dzielony jest na polimina wzdłuż brzegów kratek (linii przerywanych). Kluczem do rozwiązania są liczby. Każda określa wielkość (liczbę kratek) polimina, w którym się znajduje, ale – w przeciwieństwie do nurikabe – w tym samym poliminie może być ujawnionych więcej niż jedna liczba. Ponadto istotne jest, że polimina takiej samej wielkości nie mogą stykać się bokami.

Praktycznie rozwiązywanie polega na wpisywaniu w kratki liczb – każda powinna być równa wielkości polimina, w którym się znajduje. Na rys. 7 jest miniprzykład z dwoma rozwiązaniami z kwadratem 2×2 w septominie (prawy górny róg) – w drugim rozwiązaniu są nawet dwa takie kwadraty. Znalezienie jedynego rozwiązania bez kwadratu 2×2 nie powinno być trudne.

Z innych zadań z zabronionym kwadratem na uwagę zasługują te, w których kwadrat ten pojawia się jakby w innej formie. Zapewne najciekawszym z tej grupy jest japońskie nanro, czyli „droga liczbowa”. Do niektórych lub wszystkich pól każdej działki, na które podzielony jest diagram, należy wpisać liczby. Wszystkie liczby w danej działce powinny być jednakowe i powinno ich być tyle, ile wynosi wartość każdej z liczb (jedna jedynka, dwie dwójki, trzy trójki itd.). W sąsiednich polach (stykających się bokiem) nie mogą znaleźć się takie same liczby, jeśli pola te należą do różnych działek. Pola z liczbami muszą tworzyć – jak grobla w nurikabe – jeden spójny wielokąt (polimino), ale oczywiście niezawierający kwadratu 2×2. Na początku kilka liczb jest ujawnionych. Na rys. 8 jest miniprzykład z rozwiązaniem, a obok nieco trudniejsze nanro – „treningowe” przed zadaniami konkursowymi.

Zadania

1. Zadanie jest typowym nurikabe (rys. 9), więc reguły są zgodne z opisem zamieszczonym w artykule. W rozwiązaniu wystarczy podać, ile pól na obu przekątnych diagramu zajętych jest przez groblę.

2. To nietypowe, „incydentalne” yin-yang (rys. 10), czyli takie, w którym jedna z wyznaczanych części całkowicie otacza drugą, więc ujawnione zostały wszystkie brzegowe białe kółka zewnętrznej części. Zasady rozwiązywania opisane są w artykule. W rozwiązaniu wystarczy podać, ile czarnych i białych kółek jest na obu przekątnych diagramu.

3. Z ośmiu figur – czterech różnych tetromin i czterech różnych pentomin – należy ułożyć kwadrat 6×6 (rys. 11). Pola z literą T powinny być pokryte przez tetromina, a pola z literą P – przez pentomina. Żadna z figur nie może zawierać kwadratu 2×2, czyli wykluczone są dwie jasnoniebieskie figury z rys. 3. W układance należy więc użyć czterech ciemnoniebieskich tetromin i czterech pentomin wybranych z jedenastu ciemnoniebieskich – w tym obowiązkowo pentomina w kształcie krzyża.

4. Archipelag to „bliźniak” nurikabe, ale z jego nazwą wiąże się inny entourage – grobla jest pocięta i tworzy wyspy, a stawy zmieniają się w laguny między wyspami (przykład i zadanie na rys. 12). Każde pole z liczbą jest częścią prostokątnej laguny złożonej z tylu pól, jaka jest wartość liczby. W odróżnieniu od nurikabe liczb może być mniej niż lagun, czyli nie każda laguna musi być ujawniona dzięki liczbie, ale też żadnej laguny nie może oznaczać więcej niż jedna liczba. Wszystkie laguny tworzą jedną całość – są połączone wąskimi przesmykami, znajdującymi się w niektórych ich rogach, zatem z każdej laguny można przedostać się przez te rogi „drogą morską” na dowolną inną lagunę. Zadanie polega na zaczernieniu wysp i zaniebieszczeniu lagun. Na wyspach kwadraty 2×2 są zabronione, ale w lagunach mogą się pojawić. W rozwiązaniu wystarczy podać, w ilu i jakiej wielkości lagunach nie została ujawniona cyfra.

Rozwiązania prosimy nadsyłać do 28 lutego 2023 roku pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 02/23. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Smak trucizny Neila A. Bradbury’ego ufundowaną przez Wydawnictwo REBIS. 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 grudniowego

Rozwiązania wszystkich zadań (podziały figur) na rys. 13.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Dziesięć leków, które ukształtowały medycynę Thomasa Hagera, ufundowaną przez Wydawnictwo REBIS otrzymują: Bartosz Chroł z Warszawy, Agata Ciołek z Bukowna, Bartłomiej Goldman z Nadarzyna, Sabina Kowal z Warszawy, Krystyna Kruszy z Olkusza.

***

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”.