This document is also available in English. Dieses Dokument ist auch auf Deutsch erhältlich.

Marko Mäkelä: ohjelmointi: Pentomino-palapelien ratkaiseminen

Pidän kombinatorisista ongelmista, mutta minulla on tapana ratkaista ne raa’alla voimalla. Selvitin 6×10-kokoisen Pentomino-palapelin kaikki ratkaisut parissa suoritinviikossa muutamalla 266 MHz:n Pentium II -työasemalla joskus vuoden 2000 aikoihin.

C-kielinen ratkaisuni käyttää syvyyshakua. Vuonna 2013 tekemäni yksinkertainen parannus karsii ne osaratkaisut, joissa laudalla on vapaita alueita, joiden koko ei ole viidellä jaollinen. Karsiminen onnistuu täyttämällä kukin vapaa alue ja laskemalla samalla niiden koko. Kokeilemassani 2,5 GHz:n kellotaajuudella toimivassa Intel Core i5-2520M -järjestelmässä optimoitu C-käännös käy läpi koko hakuavaruuden noin 4 minuutissa.

C++-kielinen ratkaisuni hyödyntää STL-kirjastoa. Kokeilemassani järjestelmässä optimoitu C++-käännös oli C-ohjelmaa hitaampi täyttörutiinin työjonon dynaamisen muistinhallinnan vuoksi. C-ohjelma käytti pinosta varattua taulukkoa, C++-ohjelma std::list-tietorakennetta.

Ajoajan ero poistui tammikuussa 2014, kun huomasin, että työjonon esittämiseen sopii luontevammin joukko. Alkuperäinen täyttöalgoritmin toteutus saattoi lisätä saman työalkion jonon perälle moneen kertaan. Joukko voidaan tässä tapauksessa esittää tehokkaasti bittikarttana, tarkemmin sanottuna yhdellä 64-bittisellä kokonaisluvulla siinä missä koko 60-alkioinen pelilautakin. C-kielisenkin ohjelman ajoaika lyheni vähän yli puoleen, kun keksin ennen seuraavan alkion hakemista poistaa bittikartan esittämästä työjonosta jo täytetyt alueet. Ajoaika lyheni lisää (kaikki 2 339 ratkaisua löytyvät 40 sekunnissa) poistettuani ensimmäisen palan symmetriset asennot. Peilikuvat poistettuani I-kirjaimen muotoisen palan 56 eri asennosta jäljelle jäi 14.

Joulukuussa 2016 muutin C++-toteutuksen käyttämään C++14-kielen constexpr-avainsanaa, niin että palojen bittikuviot (jopa 8 erilaista asentoa kullekin palalle) voidaan muuntaa käännösaikana. Kokeilin myös alustuttaa palojen kaikki 2 014 sijoittelua pelilaudalle. Se oli huono ajatus jo Kolmogorov-kompleksisuuden vuoksi (sijoittelut laskeva ohjelmakoodi on lyhempi kuin 2 014×64 bittiä). Lisäksi clang rajoittaa käännösaikaisen laskennan määrää.

clang 4.0.0:n kehitysversio käänsi valitsimia -O3 -DNDEBUG käytettäessä C++-ohjelman 10% nopeammaksi kuin C-ohjelman. GCC 6.2.1 samoilla valitsimilla käänsi C-ohjelmasta suunnilleen yhtä nopean kuin clang C++-ohjelmasta, mutta GCC:n kääntämä C++ oli 25% hitaampi. (Odotusteni vastaisesti GCC teki hieman nopeampaa koodia, kun std::array vaihdettiin std::vectoriin.)

Kokeilin myös 12-tasoisen rekursiopinon laventamista käännösaikana mallineiden (template) avulla, mutta ajoaika piteni hieman. Aion vielä kokeilla rekursion korvaamista silmukalla, jossa taulukko esittää hakupinoa.

Kolmiulotteisten palapelien ratkaiseminen

Vuoden 2014 alussa vaimoni löysi kirpputorilta 4×4×4-palapelin, jossa on yksi neljän tilavuusyksikön pala ja kaksitoista viiden tilavuusyksikön palaa eli yhteensä 4×4×4=4+12×5=64 tilavuusyksikköä. Toisin kuin Pentomino-palapelissä kyseessä eivät ole kaikki mahdolliset kyseisen tilavuiset palat. Ratkaisuja näyttäisi olevan 20 433. Pienin muutoksin sama ratkaisuperiaate on sovellettavissa:

  1. Esitetään palat yksinkertaisuuden vuoksi merkkijonoina.
  2. Muunnetaan palat pelilaudan esitysmuotoon (64-bittiseksi luvuksi).
  3. Muodostetaan jokaisesta palasta kiertämällä ja siirtämällä kaikki mahdolliset asennot pelilaudalla.
  4. Aloitetaan syvyyshaku 4 tilavuusyksikön palasta.
  5. Jos jokin vapaa tila ei ole jaollinen 5:llä, osaratkaisu on mahdoton, koska kaikki 5 tilavuusyksikön palat eivät voi sopia jäljellä olevaan tilaan.

Joulukuussa 2016 kirjoittaessani ratkaisimen hyödyntämään C++14-kielen ominaisuuksia huomasin tehneeni virheen symmetristen ratkaisujen poistamisessa. Kun palaa pyöräytetään kuinkin akselin ympäri, mahdollisia vaihtoehtoja on 4×4×4 eli 64. Palapelini pienelle palalle näistä 12 on erilaisia. Mutta monet näistä 12 asennosta ovat itse asiassa toistensa kanssa symmetrisiä, kun pala asetetaan kuution samaan nurkkaan ja pyöräytetään koko laatikkoa kaikilla 64 tavalla siirtämättä samalla palaa laatikon sisällä. Osoittautuu, että pieni pala voidaan asettaa laatikkoon vain 15 erilaisella tavalla eikä 261 tavalla, niin kuin virheellinen ratkaisuni teki.

Lataukset

pentomino.c
C-kielinen Pentomino-ratkaisija
pentomino.C
C++-kielinen Pentomino-ratkaisija
pentomino.png
kuva 6×10-kokoisen Pentomino-pelin kaikista 2 339 ratkaisusta
pentomino.pl
pieni apuohjelma kuvan koostamiseksi
puzzle3d.C
C++-kielinen 3-ulotteisen 4×4×4-palapelin ratkaisija
puzzle3d.txt.gz
4×4×4-palapelin kaikki 20 433 ratkaisua