Umysł giętki: Garde passé, czyli zgoda w hetmanii

Hetmania, czyli strefa opanowana wyłącznie przez hetmany, pojawiła się po raz pierwszy we wrześniu 1848 roku w berlińskim miesięczniku „Schachzeitung” jako tło jednego z najbardziej znanych problemów szachowo-matematycznych.

Max Bezzel, problemista niemiecki – a właściwie bawarski, bo Bawaria była wtedy odrębnym państwem – postawił pytanie: ile najwięcej hetmanów i w jaki sposób można umieścić na pustej szachownicy 8×8, aby żadne dwa się nie atakowały, czyli nie stały w tym samym wierszu, kolumnie ani na żadnej linii ukośnej złożonej z przekątnych pól? Łatwo sprawdzić, że osiem da się ulokować, a więcej na pewno nie, więc wystarczy zapytać o liczbę różnych ustawień.

W ciągu kilku następnych lat na łamach „Schachzeitung” sporadycznie pojawiały się rozwiązania – w sumie zebrało się ich około 40. W międzyczasie w połowie roku 1850 w dziale szachowym lipskiego tygodnika „Illustrirte Zeitung” znalazło się zadanie nadesłane przez niejakiego Franza Naucka, lekarza ze Schleusingen: na pustej szachownicy stoją dwa hetmany na polach b4 i d5; gdzie postawić jeszcze sześć tak, aby żaden z ośmiu hetmanów nie atakował żadnego z pozostałych. Inspiracja była widoczna, ale Nauck nigdy nie potwierdził, że wzorował się na zamieszczonym w niszowym miesięczniku problemie Bezzela. Traf chciał, że czytelnikiem popularnego i wysokonakładowego jak na owe czasy tygodnika był 73-letni wówczas „książę matematyków” Carl Friedrich Gauss, któremu zadanie przypadło do gustu. Rozwiązał je (są 2 rozwiązania), a przy okazji znalazł 76 rozwiązań ogólnego zagadnienia, czyli problemu Bezzela, zastrzegając, że może ich być więcej. Informacją tą podzielił się z astronomem Heinrichem Schumacherem, zachęcając go do zajęcia się ogólnym problemem. Korespondencję między uczonymi, w której padały różne liczby (obaj niezbyt przykładali się do rozwiązywania), przerwał zamieszczony w „Illustrirte Zeitung” zapis kompletu 92 rozwiązań autorstwa doktora Naucka. Dopiero wtedy Gauss zabrał się do solidnej pracy: zaczął sprawdzać, analizować i szukać eleganckiego sposobu rozwiązywania.

Nauck doszedł do wszystkich możliwych 92 ustawień niezbyt elegancko, korzystając ze schematycznej, dość żmudnej metody prób i błędów. Współcześnie odpowiada jej „siłowy” algorytm z nawrotami zwany też backtrackingiem, który po zaaplikowaniu szybkiemu komputerowi błyskawicznie daje komplet rozwiązań. Algorytm polega na lokowaniu hetmanów na przykład w kolejnych wierszach, zaczynając od dolnego – zawsze na najbliższym lewego brzegu nieatakowanym polu. Gdy takiego pola nie ma, trzeba korygować pozycję hetmana w poprzednim wierszu, zaś jeśli i to nie wystarcza, w kolejnym poprzednim, ewentualnie w jeszcze niższym – i tak dotąd, aż możliwy będzie ruch „ku górze”. Po wykonaniu w ten sposób sześciu początkowych ruchów (rys. 1) dla siódmego hetmana zabraknie pola w siódmym wierszu, więc konieczna będzie pierwsza korekta: usunięcie hetmana z g6, przesunięcie z d5 na h5 i znowu trzeba korygować: usunięcie z h5, przestawienie z b4 na g4, nowe na b5, d6 i f7 i… następna korekta itd.

Po około 10 minutach pojawia się pierwsze rozwiązanie (rys. 2a), zaś po paru godzinach ujawniane są wszystkie, a praktycznie połowa, bo zabawę w żywy komputer można zakończyć na ustawieniach zaczynających się od hetmana na a4. Druga połowa – z pierwszym hetmanem lokowanym na polach od a5 do a8 – będzie zbiorem lustrzanych odbić pierwszej. Jednak wśród otrzymanych rozwiązań są także grupy „bliźniaczych” – w każdej grupie każde ustawienie można otrzymać z innego w wyniku obrotu lub/i lustrzanego odbicia. Takich grup jest tuzin: 11 z nich zawiera po cztery ustawienia, a jedna dwa, ponieważ są one symetryczne (rys. 2j). A zatem całkowicie różnych rozwiązań problemu Bezzela jest 12. Wszystkie przedstawiono na rys. 2 w takiej kolejności, w jakiej pojawiają się w trakcie stosowania opisanego wyżej algorytmu z nawrotami. Testem spostrzegawczości i wyobraźni może być poszukanie wśród nich dwóch rozwiązań zadania Naucka z hetmanami na b4 i d5 – obróconych lub/i odbitych.

Gauss zauważył możliwość przekształcenia zadania szachowego, a właściwie geometrycznego – w arytmetyczne. Zaczął od zastąpienia liter, oznaczających kolumny szachownicy, kolejnymi liczbami od 1 do 8 – podobnie jak oznaczone są wiersze. Po takiej zmianie położenie każdego pola wyznaczają dwie współrzędne liczbowe (w, k), które są odpowiednio numerami wiersza i kolumny. Jeśli dwa hetmany znajdą się na tej samej przekątnej, czyli będą się atakować, co nie jest dozwolone, wówczas są dwie możliwości. Gdy przekątna opada w prawo (szara na rys. 3), to suma współrzędnych (w+k) jednego hetmana będzie taka sama jak drugiego. Gdy przekątna wznosi się w prawo (czerwona na rys. 3), to wspomniane sumy także są jednakowe, ale tylko wtedy, gdy wiersze ponumerujemy w odwrotnej kolejności (czerwone liczby przy prawym brzegu szachownicy). Stąd dwa bliźniacze warunki bezkonfliktowego ustawienia ośmiu hetmanów: osiem sum ich współrzędnych powinno być różnych zarówno dla rosnącej (od dołu planszy) numeracji wierszy (w_R), jak i dla malejącej (w_M).

W tabeli na rys. 4b znajdują się sumowania współrzędnych dla ustawienia hetmanów z rys. 2a uzupełnionego współrzędnymi liczbowymi kolumn (rys. 4a). Środkowa żółta kolumna tabeli zawiera współrzędne kolumn diagramu, odpowiadające kolejnym wierszom. Na lewo od tej kolumny są czarne sumowania z liczbami w_R zapisane wspak, na prawo – sumowania czerwone z liczbami w_M. Jak widać, wszystkie sumy w każdej z zielonych kolumn są różne, co potwierdza poprawność ustawienia.

Przekształcenie Gaussa sprowadza zadanie szachowe do kombinatorycznego: do żółtej kolumny tabeli na rys. 5 należy wpisać taką czarno-czerwoną permutację zbioru liczb od 1 do 8, aby w zielonych kolumnach pojawiło się osiem różnych sum czarnych dodawań i osiem różnych sum dodawań czerwonych. Zadanie formalnie jest nieco bardziej eleganckie niż pierwowzór, a rozwiązywanie nieco prostsze, choć oczywiście metoda prób i błędów odgrywa główną rolę. Słabą stroną tego wariantu jest trudność wskazania wśród 92 permutacji tuzina tych, które odpowiadają podstawowym ustawieniom hetmanów z rys. 2.

Warto zauważyć, że tuzin różnych ustawień można ograniczyć, jeśli za jednakowe uznać ustawienia, będące efektem przekształcenia, polegającego na przesunięciu wszystkich hetmanów o p pól w poziomie (w wierszach) lub w pionie (w kolumnach). Przesuwając hetmany np. w prawo, zakładamy, że szachownica umieszczona jest na walcu pionowym, czyli każda figura wysuwana poza planszę na prawo wchodzi na nią z lewej strony. Podobnie przesunięciu w dół odpowiada walec poziomy, czyli każdy hetman spadający w dół wskakuje na szachownicę w tej samej kolumnie od góry. Efektem takich przesunięć, uzupełnionych ewentualnie innymi przekształceniami, są dla rozwiązania a (rys. 2) rozwiązania f (p=1), h (p=2 i lustro poziome) oraz k (p=3 i obrót o 180). Niestety, w przypadku rozwiązań b, e, g, i, j oraz l taki sposób przekształceń nie działa, czyli nie prowadzi do innych rozwiązań, więc ograniczenie tuzina podstawowych jest niewielkie – do ośmiu; poza podanymi sześcioma nieprzekształcalnymi są to np. a i c.

Wprawdzie figury w trakcie powyższego przekształcania przesuwane były tak, jakby znajdowały się na walcu, ale praktycznie powierzchnia walcowa była cały czas rozpłaszczona. Gdyby natomiast hetmany rzeczywiście tkwiły na walcu, to rozwiązań w ogóle by nie było, bo wówczas liczba przekątnych byłaby mniejsza, a zasięgi stojących na nich figur większe; przekątne walcowej planszy są jednakowej długości – każda obejmuje 8 kratek.

Gauss zaproponował rozszerzenie problemu hetmanów z ośmiu do n, czyli szukanie sposobów rozmieszczenia n hetmanów na planszach n×n. Ściślej, chodzi o dwa podproblemy: pierwszy dotyczy dowodu, że rozwiązanie istnieje dla każdego n, drugi polega na znalezieniu wszystkich rozwiązań, a przede wszystkim formuły albo metody pozwalającej określać ich liczbę dla danego n. Z pierwszym uporano się dość szybko na kilka sposobów. Ogólnie mówiąc, znaleziono schemat, który przekształca określone rozwiązanie dla n≥4 (dla mniejszych n nie ma rozwiązań) w rozwiązanie dla n+1. Drugi podproblem pozostaje nierozstrzygnięty, tzn. jedyną praktyczną metodą szukania rozwiązań i określania ich liczby dla n>8 pozostaje skorzystanie z komputera. Ograniczeniem tej metody jest jednak złożoność obliczeniowa; w związku z tym n=27 wyznacza obecnie kres możliwości najmocniejszych komputerów. Przed pięciu laty po ponad roku pracy komputerów na Technische Universität Dresden ustalono, że 27 hetmanów można rozmieścić bezkonfliktowo na planszy 27×27 na S₂₇=234 907 967 154 122 528 (blisko 235 biliardów) sposobów, z czego całkowicie różnych jest prawie ośmiokrotnie mniej – 29 363 495 934 315 694. Na wynik dla n=28 przyjdzie zapewne poczekać, aż do akcji wkroczą komputery kwantowe. Wartości S_n (wszystkie rozwiązania) i S_Rn (całkowicie różne, czyli bez obrotów i odbić lustrzanych) dla 4≤n≤26 podane są w tabeli na rys. 6.

W minionym roku zatrudniony na Harvard University izraelski matematyk Michael Simkin sformułował przybliżony wzór na liczbę ustawień dla dużych n: S_n≈(0,143n)ⁿ. Propozycję (publikacja wymaga jeszcze zweryfikowania przez innych matematyków) poprzedziła wnikliwa analiza cech wspólnych ustawieniom hetmanów dla różnych wartości n oraz badanie ustawień na planszy umieszczonej na torusie, na której, podobnie jak na walcu, nie tylko wiersze i kolumny, ale także przekątne są takiej samej długości. Ściśle rzecz biorąc, wartość wynikająca ze wzoru Simkina jest tym bliższa rzeczywistej, im większe jest n, jednak zbliżanie się jest bardzo wolne, więc dla kilku- a nawet kilkunastocyfrowych n wynik obarczony jest znacznym błędem. Jako przykład skuteczności wzoru zwykle podaje się wartość S_n dla n równego milion, która jest liczbą złożoną z ponad pięciu milionów cyfr.

O sięgającym w okolice nieskończoności wzorze Simkina było głośno w mediach, choć nie został on jeszcze sprawdzony, ani nie jest pierwszym z grubsza dyscyplinującym wartości S_n. Tymczasem bez echa przeszedł najtrafniej obsługujący małe n wzór zaproponowany w 2000 roku przez duńskiego matematyka Birgera Nielsena: S_n≈n!(0,3885)^n-1. Ta formuła działa zaskakująco dokładnie dla n=10 i 13 oraz n>14 – ze średnim błędem poniżej 1%, oczywiście dla znanych S_n. Czy równie dobrze spisuje się dla n>27, na razie nie wiadomo.

Z perspektywy matematyki rekreacyjnej w problemie n hetmanów najciekawsze są osobliwe cechy różnych konfiguracji oraz oryginalne warianty podstawowego zagadnienia. Osobliwe, a przynajmniej wyróżniające się ustawienia można znaleźć choćby wśród tuzina podstawowych na rys. 2. Łatwo zauważyć jedyną konfigurację symetryczną (symetria środkowa), która wyróżnia się także niezawierającym hetmanów centralnym kwadratem 4×4, a ponadto jest jedną z dwóch bez hetmanów na przekątnych. Nieco trudniej znaleźć jedyne ustawienie, w którym żadne trzy hetmany, a ściślej środki zajmowanych przez nie pól, nie leżą na linii prostej (chodzi oczywiście o dowolną prostą, a nie tylko wyznaczoną przez przekątne kratek).

Kilka ciekawych zagadnień pojawia się, gdy wyobrazimy sobie rozwiązania z rys. 2 narysowane na przezroczystej folii. Pierwsze sprowadza się do pytania: jeśli będziemy wybierać i równo ze sobą składać na wszystkie możliwe sposoby po 2 różne rozwiązania, to ile najwięcej hetmanów zostanie zasłoniętych (pokrytych) przez inne hetmany i dla której pary lub których par rozwiązań wystąpi taka sytuacja? Inaczej mówiąc: ile co najwyżej hetmanów może znaleźć się w dwu rozwiązaniach na tych samych polach?

Zadanie praktyczne jest bardzo żmudne, bo, jeśli uwzględnić odbicia i obroty, są 444 pary, które trzeba by ze sobą składać. Teoretycznie niemożliwe jest pokrycie się n-1 hetmanów, bo wtedy pokryłyby się także n-te, czyli rozwiązania nie byłyby różne. Pokrywanie się n-2 figur nastąpi wtedy, gdy możliwe będzie przesunięcie pary niepokrywających się, stojących na polach tego samego koloru o współrzędnych (x₁, y₁) i (x₂, y₂) – na pola (x₁, y₂) i (x₂, y₁), zaś po takich przesunięciach powstanie poprawne rozwiązanie, czyli żadne hetmany nadal nie będą się atakować. Taka sytuacja występuje np. dla n=7: na rys. 7 są dwa rozwiązania z pięcioma czarnymi hetmanami identycznie ulokowanymi, a dwa czerwone są przesunięte równolegle w przeciwnych kierunkach. Dla n=8 w żadnym rozwiązaniu nie uda się tak przesunąć dwóch hetmanów, aby powstało inne rozwiązanie, natomiast łatwo zauważyć – bez uwzględniania obrotów i odbić – że w rozwiązaniach 2j i 2k (rys. 2) pięć hetmanów zajmuje te same pola. Czy na szachownicy 8×8 są inne pary rozwiązań ze stabilną piątką? Pytanie pozostaje otwarte.

Odwrotny problem z rozwiązaniami-przezroczami jest nieco trudniejszy: czy można nałożyć na siebie n niekoniecznie różnych rozwiązań tak, aby hetmany nigdzie się nie zdublowały, czyli aby wszystkie pokryły całą planszę n×n? W matematyce takie zagadnienie zwane jest kolorowaniem grafu – w tym przypadku grafu hetmańskiego. Inaczej mówiąc, chodzi o takie pokolorowanie n kolorami pól szachownicy n×n, aby żadna para hetmanów umieszczonych na dwu polach tej samej barwy nie atakowała się. Łatwo dowieść, że dla n=8 jest to niemożliwe. Wystarczy zauważyć, że w każdym z ośmiu składanych rozwiązań powinny znajdować się dwa hetmany na głównych przekątnych, aby zapełnić hetmanami obie te przekątne. Skorzystać można więc tylko z rozwiązań (a, b, c, h, k, l) na rys. 2. Cztery z nich muszą należeć do zestawu (a, b), aby zapełnić rogi planszy, ale to oznacza równoczesne zapełnienie czterech pól na przekątnych sąsiadujących z narożnymi, a niestety – w każdym z pozostałych rozwiązań (c, h, k, l) hetman znajduje się już na drugim polu od końca przekątnej. Bez dubla uda się spasować ze sobą najwyżej sześć rozwiązań (rys. 8). W ogólnym przypadku zapełnienie n rozwiązaniami planszy n×n możliwe jest tylko dla n<12 i niepodzielnych przez 2 lub 3, czyli {1, 5, 7 (rys. 9), 11} oraz dla każdego n z przedziału [12,26]. Dla n>26 temat pozostaje zagadką.

Problem zgody w hetmanii inspirował także autorów gier. O efektach tej inspiracji – w następnym numerze.

Zadania

1. Na nie zajętych przez cyfry polach szachownicy 6×6 (rys. 10) należy ustawić cztery nieatakujące się hetmany. Ich rozmieszczenie powinno być takie, aby cyfra w danym polu oznaczała liczbę hetmanów atakujących to pole.

2. Dziewięć hetmanów panuje zgodnie w hetmanii 9×9 (rys. 11). Zadanie polega na przesunięciu trzech z nich – zgodnie z zasadą poruszania się tych figur – tak, by zgoda została zachowana, czyli by żaden hetman nadal nie atakował innego. Ponadto łączny dystans trzech przesunięć powinien być jak najkrótszy. Rozwiązaniem jest zapis trzech wykonanych ruchów.

3. Wbrew pozorom ulokowanie na szachownicy 7×7 ośmiu nieatakujących się hetmanów jest możliwe, ale w szczególnej sytuacji – w obecności pionka-rozjemcy. Na rys. 12 znajdują się dwa przykłady takiego ustawienia, w którym rola pionka rozdzielającego agresywne figury jest wyraźnie widoczna. Zadanie polega na znalezieniu jeszcze jednego takiego ustawienia – nieutworzonego w wyniku obrotu lub/i odbicia któregoś z dwu podanych. Rozwiązaniem są współrzędne pozycji hetmanów i pionka.

Rozwiązania prosimy nadsyłać do 31 marca br. pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 03/22. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Łukasza Mieszkowskiego Największa. Pandemia hiszpanki u progu niepodległej Polski ufundowaną przez wydawnictwo Polityka. 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 tutaj.