This document is also available in English. Dieses Dokument ist auch auf Deutsch erhältlich.
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ää.
Elokuussa 2019 korvasin ohjelmallisen rekursion silmukalla, jossa
taulukko esittää hakupinoa. Kiinteästi varatulla pinolla se on hieman
nopeampi kuin alkuperäinen ohjelmallinen rekursio
(-DRECURSION). Dynaamisesti varattu pino
(-DHEAP_STACK, vain C++-toteutus) on odotetusti hieman
hitaampi kuin kiinteästi varattu. Huomio: ohjelmallinen rekursio
(-DRECURSION) käy hakuavaruuden läpi eri järjestyksessä
kuin hakupino.
Aiemmin kokeilin 12-tasoisen rekursiopinon laventamista käännösaikana
mallineiden (template) avulla, mutta ajoaika piteni hieman.
clang 8.0.1 käänsi valitsimia -O3 -DNDEBUG -mtune=native
-march=native käytettäessä
C++-ohjelman 8% nopeammaksi kuin C-ohjelman.
GCC 9.2.1
samoilla valitsimilla käänsi C-ohjelmasta suunnilleen 3% nopeamman kuin
C++-ohjelmasta. Ohjelmat ovat keskenään suunnilleen yhtä nopeita, mutta
clang-käännetty C-ohjelma on selkeästi muita hitaampi.
| ohjelma | GCC 9.2.1 | clang 8.0.1 |
|---|---|---|
C -DRECURSION |
27,7 s | 31,2 s |
C++ -DRECURSION |
28,7 s | 27,6 s |
| C | 26,9 s | 29,4 s |
| C++ | 27,6 s | 27,1 s |
C++ -DHEAP_STACK |
27,7 s | 28,1 s |
Kokeemme perusteella GCC tuottaa usein nopeampaa C-koodia kuin
clang ja clang nopeampaa C++-koodia kuin GCC. Ero pieneni, kun poistin
tehottoman viitteen const Board& 64-bittiseen arvoon.
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 434. Pienin muutoksin sama ratkaisuperiaate on sovellettavissa:
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.
GCC 9.2.1 tuottaa ratkaisimelleni selvästi nopeamman AMD64-koodin kuin clang 8.0.1. Kokeillessani elokuussa 2019 haku valmistui 14 063 sekunnissa (3 tunnissa, 54 minuutissa ja 23 sekunnissa) GCC:n kääntämällä ja 15 599 sekunnissa (4 tunnissa, 19 minuutissa ja 59 sekunnissa) clang:in kääntämällä ohjelmalla.
Maaliskuussa 2024 en osannut koota kuudesta suorakulmaisen särmiön muotoisesta 2×2×8-mittaisesta puutikusta muodostuvaa palapeliä, joten tein ohjelman ratkaisujen etsimiseksi. Yksi puutikku on kokonainen, ja muista tikuista puuttuu kuution muotoisia paloja 2×2×4-kokoiselta keskialueelta. Vaikka en toteuttanut minkäänlaista hakuavaruuden karsintaa, ratkaisut löytyvät noin 0,2 sekunnissa.