Pentomino

Pentomino (bildat av grekiska: pente (fem) och ordet domino) är en plan polygon i en form som bildas av precis fem lika stora kvadrater, vilka är sammansatta så att varje kvadrat delar en kant med minst en annan kvadrat. Oräknat rotationer, och reflektioner går det att bilda 12 olika sådana polygoner. Av dessa är 6 spegelsymmetriska – alltså de ser likadana ut om de vänds upp och ner. Pentomino är ett specialfall av polyomino. Det är ett begrepp som täcker alla polygoner som är bildade av ett antal kvadrater på det sätt som beskrivs ovan. Termerna polyomino och pentomino myntades av Solomon Golomb som ett derivat av domino där formen på spelbrickorna då får samma namn som spelet domino. De olika polyominoerna ges prefix baserade på de grekiska räknetalen.^[1]

Pentomino förekommer i en mängd problem och spel inom nöjesmatematik och i några datorspel och några av dessa har använts som exempel för att utveckla datoralgorimter i kombinatorik. Sådana problem presenterades i schacktidningar som the Problemist och Fairy Chess Review men kom till en större målgrupp framför allt genom Martin Gardner som tog upp pentominoer i sin kolumn i Scientific American.

Pussel av pentominoformade brickor förekommer i flera former. Pussel skapade av polyominoer kallas kvadratpussel.^[2]. Eftersom de 12 olika brickorna tillsammans täcker 60 areaenheter är de mest uppenbara formerna rektanglar av den storleken. Det går att göra lösningar för storlekarna 6×10, 5×12, 4×15 och 3×20. Rektanglarna 2×30 1×60 går inte att pussla för att de är för smala för de enskilda brickorna att passa i den formen.

Spelet går ut på att placera ut brickorna så att de bildar en hel rektangel utan hål mellan brickorna. Man måste använda alla typerna av pentominobrickor i varje uppgift, och varje bricka får endast vara med en gång. Man får vrida och vända brickorna hur man vill.

En annan populär variant är att placera de 12 brickorna i en kvadrat med 8×8 areaenheter. Eftersom det är 64 areaenheter finns olika varianter på detta pussel som att undanta hörnen eller lägg till en tetromino. En variant av det senare problemet med den kvadratiska tetrominon som extra bricka presenterades som problemet "The broken chessboard" i The Canterbury Puzzles 1907^[3], där det presenteras som att man ska reparera ett trasigt schackbräde varför brickorna har målade svarta och vita kvadrater.

En variant till pussel som lades fram av Raphael M. Rubinson inte använder alla pentominoer är triplikationsproblemet. Det går ut på att bygga en skalmodell i skala 3:1 av en pentomino med 9 andra pentominoer.^[2]

Ett av de tidigaste exemplen på en backtrace-algortim skrevs av Dana Scott 1958^[4] för att lösa kvadratpussel. Han kunde visa att de två kända lösningarna för att bygga en 3×20 rektangel av de 12 pentominoerna var de enda möjliga^[5] och fortsatte ta fram alla lösningar för specialfallet med kvadratiskt pussel 8×8 areaenheter med den kvadratiska tetrominon som extra bricka i mitten. Det är ett fall med hög grad av symmetri som gör det enklare att beräkna. Trots det fick han placera ut x-brickan manuellt och köra algoritmen på vart och ett av de tänkbara fallen för att det skulle gå att lösa på MANIAC som han använde. Scott visade att det finns 65 lösningar på problemet, spegelvändningar och rotationer oräknade, med 3,5 timmars beräkningstid på MANIAC med 5120 byte minne.^[6]

Problemet löses bäst med djup-först-sökning. Donald Knuth har visat att genom att använda en idé av Hirosi Hitotumatu and Kohei Noshita^[7] för att effektivisera djup-först-sökning gick det att ta fram en algoritm betydligt effektivare än tidigare för att lösa pentomiopussel och en rad andra relaterade problem kallad dancing links (DLX). Med DLX algorimen kunde han visa att det mer generella fallet att placera de 12 pentominoerna och den kvadratiska tetrominon på 8×8 areaenheter har 16 146 lösningar, spegelvändningar och rotationer oräknade.^[6]

En generalisering av att bygga rektangelformade kvadratpussel är att låta ett motstående par av sidor anta en annan form än en linje men där båda sidorna har samma form. En sådan form bildar ett periodiskt mönster som liksom rektanglar går att sammanfoga kopior av till ett oändligt band. Ett annat sätta att åskådliggöra ett sådant periodiskt mönster är att tillåta brickorna vara böjliga och sammanfoga sidorna med varandra till att bilda mantelytan för en cylinder.

Vidare generalisering är att alla långsidorna bildar periodiska mönster så att motstående sidor passar ihop på motsvarnade sätt. Sådana periodiska mönster bildar en polygon som repeterade i räta rader och kolumner i det underliggande rutmönstret tessellerar planet. En sådan lösning kan också åskådliggöras genom att låta kanterna för lösningen mötas i båda riktningarna för att bilda en torus. Det räcker då inte som i cylinderfallet att pentominoerna är böjliga utan de behöver dessutom kunna sträckas ut.

En tredimensionell variant kan skapas genom att de 12 pentominoerna sätts ihop av enhetskuber. Bitarna är fortfarande tvådimensionella, men kan nu pusslas samman till tredimensionella figurer. Det går att göra lösningar för rätblocken 3 x 4 x 5, 2 x 5 x 6 och 2 x 3 x 10. Man kan även försöka bygga större versioner av bitarna med dubbel längd x bredd och trippel höjd. Alla bitar är möjliga utom w och x, f är okänt.

Ett spel kallat Pentominoes presenterades av Solomon W. Golomb går ut på att två eller tre spelare turvis placerar brickor ur ett set av de tolv pentominoerna enligt samma principer som i ett kvadratpussel. Den som kan lägga den sista biten vinner. Spelet kommer att omfatta 5 till 12 drag. Hilarie K. Orman kunde 1996 genom datorberäkningar visa att det finns en strategi som kan garantera den första spelaren vinst i spelet i tvåspelarfallet.^[8]

Såväl Pentominoes som varianter där två spelare får slumpvis tilldelade brickor (Pentomino), större spelplan och var sin uppsättning av 12 pentominoer (Pan-Kai) och utvidgning av Pan-Kai till fyra spelare med större plan och fyra uppsättningar pentominoer (Universe) har lanserats kommersiellt som fysiska spel.^[9]

Blokus grundas också på idéerna om kvadratpussel och har brickor av alla polyominoer till grad 5 så över hälften av spelbrickorna utgörs av pentominoer.

Pentominoer har en betydande roll i boken "Konstmysteriet!"^[10] av Blue Balliet.

Pentominoer har en viktig roll i Arthur C. Clarkes roman Imperial Earth.^[11] Clark skriver i sin självbiografi^[12] att han blev introducerad till pentominoer av Stanley Kubrick under inspelningen av År 2001 – ett rymdäventyr där de filmade ett spel mellan en astronaut och AIn HAL 9000. Enligt Kubrick ersattes scenen av ett schackspel av rättighetsskäl men han själv blev faschinerad av både kvadratpussel och spel med pentominoer. Han hade ofta med sig en uppsättning med en 6×10 rektangulär spelplan som han sökte nya lösningar till det kvadratpusslet tills han fick utskrifter av alla 2339 lösningar som kollegor till honom tagit fram med ett datorprogram varefter han tappade intresset.^[12]