Purand

PENTOMINO
NA SZACHOWNICY I KRATKOWNICY

W roku 1907 Henry Ernest Dudeney opisał w swojej książce "The Canterbury Puzzles and Other Curious Problems" łamigłówkę, którą nazwał złamaną szachownicą.

Wyobraźmy sobie, że szachownicę tworzy płyta sklejona z 64 sześcianów. Każdy o ściankach takich samych jak pola szachownicy. Jeśli odpowiednio pociąć taką szachownicę, tak aby pozostawić złączone bokami w różny sposób tylko po pięć sześcianów, to otrzyma się 12 tzw. kamieni pentomino (rys. 2). Szachownicę uzupełnia jeden kamień złożony z czterech sześcianów razem tworzących kwadrat - tetromino. Przykładowy sposób cięcia pokazuje rysunek 1. W centrum szachownicy zaznaczony jest kwadrat tetromino.


Rys. 1. Układ szachownicy z kamieni pentomina i tetrominem kwadratowym w centrum

Na kolejnym rysunku (rys. 2) pokazane są osobno uzyskane w ten sposób kamienie pentomina (12 × 5 = 60).

Rys. 2. Kamienie pentomina uzyskane z szachownicy

Kamienie te zwykle oznacza się literami przypominającymi ich kształt F, I, L, N, P, T, U, V, W, X, Y, Z. Dodatkowo w celu jednoznacznego zapisu położenia kamienia dodaje się współrzędne zaznaczonych punktów. Przykładowo położenie kamienia Y na rysunku 1 jest opisane przez: Yb1b4c2. Do jednoznacznego zapisu położenia kamienia X wystarczą współrzędne jednego punktu, dla kamienia I - wystarczą współrzędne dwóch punktów, a położenia pozostałych kamieni muszą być opisane współrzędnymi trzech punktów.

Kamienie pentomina uzyskane z szachownicy mogą mieć także odwróconą kolorystykę (rys. 3). Kwadratowe tetromino pozostaje wtedy niezmienione, bo jego negatyw powstaje przez obrót, a całość tworzy drugi układ szachownicy (rys.4).

Jeśli tetromino zachowa się w położeniu centralnym i pominięta zostanie kolorystyka pól, to matematycy zajmujący się grą w pentomino wyliczyli, że na szachownicy - kratkownicy, można uzyskać aż 65 różnych układów 12 kamieni pentomina, bez symetrycznych odbić i układów uzyskanych po obrotach (Dan E. Scott).

Rys. 3. Kamienie pentomina uzyskane z szachownicy o odwróconej kolorystyce

Rys. 4. Układ kamieni pentomina o odwróconej kolorystyce tworzący szachownicę

Zabawa z pentomino plega na tworzeniu zadanych układów płaskich (np. prostokąty rys. 5-8), brył (np. prostopadłościany rys. 9-11), a także na jego podstawie wymyślono różne warianty gier (np. klasyczne pentomino, rys. 12-14, albo Hokus-Blokus¹).

Wybrane układy kamieni pentomina



Rys. 5. Prostokąty o wymiarach 20 × 3 (możliwe 2 układy²)


Rys. 6. Przykładowy prostokąt o wymiarach 15 × 4 (możliwych 368 układów)

Rys. 7. Dwa przykłady prostokątów o wymiarach 12 × 5 (możliwych 1010 układów)

Rys. 8. Przykłady prostokątów o wymiarach 10 × 6 (możliwych 2339 układów)


Rys. 9. Prostopadłościan o wymiarach 10 × 3 × 2 (możliwych 12 układów)


Rys. 10. Prostopadłościan o wymiarach 6 × 5 × 2 (możliwe 264 układy)

Rys. 11. Prostopadłościan 5 × 3 × 4 w trzech rzutach po obrotach o 180° wokół osi poziomej i pionowej
(możliwych 3940 układów)


Wiele różnorodnych układów można znaleźć w książkach takich jak np. "Pentomina i tangramy. Zbiór łamigłówek", autorstwa Zdzisława Nowaka, wydawnictwo WH Horyzonty, Warszawa 1972, lub "Gry w figury" Roberta Hardego (właściwie Jacka Ciesielskiego), wydawnictwo KAW, Warszawa 1983.

Najprostsza gra dla dwóch zawodników polega na układaniu naprzemiennym kamieni na kratkowanej planszy 8 × 8 (kratkownicy). Wygrywa ten, kto ostatni zmieści na planszy kolejny kamień pentomino.

Do gry wystarczy prosty zestaw kamieni wycięty z kartonu. Wzorce kamieni można wydrukować wykorzystując np. rysunki 3 lub 5.

Przykład takiej rozgrywki pokazano na rysunkach od 12 do 14. Na każdy ruch składa się najpierw położenie kamienia przez gracza rozpoczynającego i dołożenie kamienia przez gracza kończącego ruch.


Rys. 12. Pozycja po trzecim ruchu zaczynającego (5 kamieni)

Na kratkownicy (rys. 12) wytworzyły się dwa jednakowe obszary wolne, w których można ułożyć każdy z pozostałych kamieni. Jeśli teraz gracz kończący trzeci ruch położy kamień Na2a4b5, to gracz zaczynający kolejny ruch może nadal utrzymać jednakowe obydwa pola, układając kamień Y jak na rysunku 13.


Rys. 13. Ułożenie kamieni N i Y przy zachowaniu jednakowych dwóch wolnych obszarów

Teraz ułożenie kamienia F lub T pozostawia jeszcze miejsce na kamień P, ale P położony w kolejnym ruchu na drugim wolnym obszarze daje już wygraną graczowi rozpoczynającemu. Użycie kamienia P przez gracza kończącego ruch czwarty, także przegrywa, bowiem w piątym ruchu gracz rozpoczynający może ułożyć na drugim polu wolnym kamień F albo T w zależności od ułożenia kamienia P i uniemożliwić dalsze dokładanie.


Rys. 14. Jedna z możliwości wygranej gracza rozpoczynającego

Po ruchu piątym jak pokazano na rysunku 14, pozostaje wolne pole dla kamienia P, ale kamień ten już jest wykorzystany, a z pozostałych kamieni Z, T, I, żaden już na planszy się nie zmieści. Wygrywa więc gracz rozpoczynający układanie kamieni. Trzeba jednak zauważyć, że przegrywa nieco inne położenie kamienia 5. Pd7d8f7 w sytuacji z rysunku 14, bo gracz dokładający mógłby wtedy jeszcze zmieścić kamień T.

Pokazana tutaj przykładowa partia kończy się po ułożeniu 9 kamieni albo - w przypadku wspomnianego błędu gracza rozpoczynającego - po ułożeniu 10 kamieni, co jest przeciętną tego rodzaju rozgrywek. Najdłuższa partia obejmuje 6 pełnych ruchów i ułożenie wszystkich dwunastu kamieni na kratkownicy.

Najkrótsza rozgrywka jest pokazana na rysunku 15. Składa się z trzech ruchów-ułożeń wykonanych przez rozpoczynającego i dwóch ułożeń wykonanych przez dokładającego.

          1. L, V
          2. U, Y
          3. I (rys. 15)

Wygrywa w tym przypadku zawodnik rozpoczynający grę.


Rys. 15. Najkrótsza rozgrywka pentomino

Jeśli jednak gracz rozpoczynający trzeci ruch położy kamień I o jedno pole dalej (Ig2g6), to wtedy wygra zawodnik dokładający, bo znajdzie jeszcze miejsce na kamień T.

Aktualna siła obliczeniowa komputerów pozwala na rozpoznanie strategii optymalnych4 w niektórych grach. Pentomino jest grą, w której gracz zaczynający, jeśli nie popełni błędu, to wygrywa (tab. 1).

Tab. 1. Wyniki strategii optymalnych

GraOszacowanie
przestrzeni
stanów
Wynik
zaczynającego
Autor/zy
rozwiązania
Rok
Kółko i krzyżyk103remis - -
Młynek1010remisR. Gasser1993
Czworaki1013wygrywaJ.D.Allen
V. Allis
1988
Pentomino1012wygrywaH.K.Orman1996
Warcaby angielskie5×1020remisJ. Schaeffer2007
Szachy1043???

Hilarie K. Orman podaje³, że gracz rozpoczynający, przyjmując strategię optymalną, powinien jako pierwszy położyć kamień Ne3e5f6.

www.purand.pl

¹ Penszko M., Łamigłówki. Podróże w krainę matematyki rekreacyjnej, Prószyński i S-ka, Warszawa 2009
² Pentominoes, https://web.ma.utexas.edu/users/smmg/archive/1997/radin.html (2019_04_26)
³ Hilarie K. Orman, Pentominoes: A First Player Win, Games of No Chance MSRI Publications Volume 29, 1996
4 T. Goluch, Zastosowanie komputerów w dziedzinie wyszukiwania strategii optymalnych w grach logicznych, Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej Nr 31, XXII Seminarium ZASTOSOWANIE KOMPUTERÓW W NAUCE I TECHNICE’ 2012