Ik volg een opleiding tot meubelmaker op het HMC Next. Afgelopen donderdag kwam er iemand, laten we hem [de Boswachter] noemen, naar onze klas met de vraag “Wie kan deze puzzel oplossen?”. De puzzel bestaat uit 6 houten stukken die in elkaar geschoven moeten worden. Meerdere mensen hadden er uren aan gepuzzeld en konden geen oplossing vinden. [De Boswachter] zelf had “het hele internet en het hele darkweb afgezocht, maar nog geen oplossing gevonden”. Ik heb het zelfs nog aan een man op de hoek met een papegaai op zijn schouder gevraagd, die had enkele interessante schatkaarten in de aanbieding, maar helaas geen oplossingen voor deze puzzel.
De puzzel heet Escher’s Burr en is ontworpen door Ronald Kint-Bruynseels. Op deze site staat een diagram waarmee een bekwaam houtbewerker deze puzzel kan maken, maar geen manier om de puzzel in elkaar te zetten. Op een andere site vond ik dat deze puzzel 1 oplossing zou hebben en van level 3.13.5 zou zijn. Dit betekent dat er 3 bewegingen nodig zijn om de eerste plaat te verwijderen, 13 voor de tweede, en 5 voor de derde. Meer informatie over de levels vond ik in deze PDF.
De puzzel
De puzzel bestaat uit 6 “platen” van 5x9x1 eenheden groot. Drie platen (A,B en C) zijn van donker hout en 3 (D,E,F) zijn van lichter hout. Al deze platen hebben een grove “C”-vorm, waarbij drie zijden helemaal recht zijn, en een vierde zijde een inkeping heeft met een complexe vorm.
De opgeloste puzzel bestaat steeds uit een paar witte en zwarte platen, die in 3 richtingen 1 eenheid ten opzichte van elkaar verschoven tegen elkaar zitten, met de twee paren elk van de drie assen als normaal. Omdat ze getrapt in elkaar zitten, bestaat de volledige puzzel een volume van 10x10x10 eenheden.
Aantal oplossingen
Elk zwarte plaat kan op 3 posities geplaatst worden, maar als plaat A al op positie 1 zit, kan plaat B maar op 2 en plaat C maar op 1 positie. Er zijn dus 3×2×1=6 mogelijkheden om de zwarte platen op hun posities te plaatsen.
Per positie kan elke plaat in 4 orientaties (gedraaid over as x, as y, beide assen of niet).
Voor de witte platen geldt hetzelfde.
Maar de totale puzzel zou zo 3 oplossingen hebben, die gelijk zijn omdat de hele puzzel op 3 manieren gedraaid kan worden. Daarom definieer ik dat plaat A altijd op dezelfde positie zit (maar wel gedraaid over een as kan zijn)
Er zijn dus (6×4³)²÷3=49152 mogelijkheden om de puzzelstukken in elkaar te passen. Die wil ik eerst vinden. Hopelijk is er maar één manier om de stukken in elkaar te passen, dan kan ik vanaf daar uitvinden hoe de stukken passen.
Oplossing vinden
Ik besloot een programma in Java te schrijven, ook al is het jaren geleden dat ik dat voor het laatst gedaan heb. Hiervoor heb ik Eclipse geïnstalleerd, omdat dat enorm helpt met de foutopsporing.
De te volgen stappen lijken mij nu:
- Één plaat definieren
- Plaat positioneren, roteren en in een matrix plaatsen
- Meerdere platen in de matrix plaatsen en kijken of er overlap is
- Alle mogelijke combinaties proberen
Ik heb ervoor gekozen om snel en hackish te programmeren, dus geen controles op juiste groottes van arrays etc. Het wordt een programma om éénmalig een probleem op te lossen.
Definities
Voor de duidelijkheid heb ik de 6 platen A t/m F genoemd. De platen vormen een horizontale rechthoek, 9 eenheden breed langs de x-as, die naar rechts loopt, en 5 eenheden hoog langs de y-as, die naar beneden loopt. Elke plaat kan worden gedraaid. FlipX is geen draai over de X-as, maar dat de indices X omgedraaid wordt, de rechterkolom wordt dan links en de linkerkolom komt rechts. FlipY is dus dat de onderste rij boven wordt en vice versa. Ik noteer een geflipte plaat als fX en/of fY.
De platen kunnen (eventueel geflipt) elk op een van de 6 posities geplaatst worden, maar er zijn 3 posities (2,4,6) alleen bedoeld voor zwarte en 3 (1,3,5) alleen voor witte platen.
De matrix is een rechtshandig assenstelsel, met de x-as naar rechts, y naar voren en z naar beneden.
De platen moeten gezien worden vanuit de as, terugkijkend naar het nulpunt. Dus als een niet-geflipte plaat op positie 5 of 6 zit, zit de bovenkant van de plaat aan de onderkant van de puzzel.
Plaat definiëren
Ik heb een simpele class Plate gemaakt, die intern de plaat als een int 5×9-array van cellen opslaat, plus de naam en kleur van de plaat.
Deze class heb ik twee methods flipX en flipY gegeven, die de plate vooraf draaien over de x- of y-as van de plaat. Al zie ik nu dat ik de methodes verkeerdom gedefinieerd heb: flipX draait een plaat om een as parallel aan de Y-as en vice versa, maar het klopt met mijn kladtekening, dus dat laat ik zo. Dit zijn trouwens de lokale x- en y-as van de plaaat, die niet overeenkomen met de x- en y-as van de latere matrix.
Todo (foto kladtekening flipx/flipy)
Matrix definiëren
Het idee van de matrix lijkt mij simpel: Maak een driedemensionale int-array, waar ik de platen in plaats. Door de vorm van de platen en hoe ze verschoven zijn ten opzichte van elkaar is een 10×10×10-matrix voldoende.
Ik heb een method gemaakt waar ik een plaat in kan plaatsen, met de linkerbovenhoek van de (eventueel geflipte) plaat op de linkerbovenhoek (eenheid) van de matrix, en dan een aantal eenheden over elk van de assen verschoven kan worden.
Dit heb ik later versimpeld tot een method waarbij je een plate op een bepaalde positie plaatst, intern worden dan de juiste verschuivingen berekend.
Meerdere platen passen
Een plaat heeft een waarde 1 waar hout zit, en 0 waar dat niet zit. Per matrixcel tel ik de waarden van de daar geplaatste cellen op, als de eindwaarde 2 (of hoger) is dan is deze combinatie van plaatsingen onmogelijk omdat platen elkaar overlappen.
Alle combinaties aflopen
Van de zwarte platen hou ik plaat A altijd op positie 2 (maar deze kan in meerdere rotaties.
Dan kunnen platen B en C nog wisselen tussen positie 4 en 6.
Elk van de platen kan over de x- en over de y-as gedraaid zijn.
Ik heb daarbinnen een loop gemaakt die 2^12 keer loopt (12, want 6 platen, elk mogelijk flippen over 2 assen), die de bits van de binaire waarde gebruikt voor elk van deze 12 flips.
Het resultaat ziet er ongeveer zo uit:
...
Attempt 49150 z:1 w:5 i:4093 A.AYB.B.C.C.D.D.E.E.F.F.
(COLLIDING) P1:Fw P2:A.fYb P3:Ew P4:Cb P5:Dw P6:Bb
Attempt 49151 z:1 w:5 i:4094 AXA.B.B.C.C.D.D.E.E.F.F.
(COLLIDING) P1:Fw P2:A.fXb P3:Ew P4:Cb P5:Dw P6:Bb
Attempt 49152 z:1 w:5 i:4095 A.A.B.B.C.C.D.D.E.E.F.F.
(COLLIDING) P1:Fw P2:Ab P3:Ew P4:Cb P5:Dw P6:Bb
Dit betekent dat in de bovenste van deze pogingen, alleen A over Y geflipt is, dat positie 1 door plaat F(wit) bezet wordt, positie 2 door plaat A (b=black/zwart) die ge-y-flipt is, positie 3 door w(itte) plaat E enzovoorts. COLLIDING betekent dat de platen elkaar overlappen, en dat dit dus een ruimtelijk onmogelijke combinatie is. De eerste van deze drie non-oplossingen is als volgt:
Attempt 49150 z:1 w:5 i:4093 A.AYB.B.C.C.D.D.E.E.F.F.
Matrix (COLLIDING) P1:Fw P2:A.fYb P3:Ew P4:Cb P5:Dw P6:Bb
layer 0 layer 1 layer 2 layer 3 layer 4 layer 5 layer 6 layer 7 layer 8 layer 9
·········· ·········· ·········· ·········· ··11111··· ·········· ·········· ·········· ·········· ··········
·········· ·········· ·········· ·········· ··11111··· ···11111·· ·········· ·········· ·········· ··········
·········· ·····1···· ·····1···· ·····1···· ··1·121··· ···11111·· ·····1···· ·····1···· ·····1···· ·····1····
····1····· ····11···· ····11···· ·········· ··1··11··· ···12·11·· ····1····· ····1····· ····11···· ·····1····
····1····· ····11···· ·111121111 ·11··1··11 ·121·····1 ·112211211 ·1112··111 ····1····· ····1····· ·····1····
····1····· ·····1···· ·····1···· 111112111· 112113211· 1··111111· 11··1··11· 111·22111· ····11···· ·····1····
····1····· ····11···· ····11···· ····11···· ··1·121··· ···121·1·· ····1····· ····11···· ····11···· ·····1····
····1····· ····1····· ····1····· ····1····· ··11111··· ···121·1·· ····1····· ····1····· ····1····· ··········
·········· ·········· ·········· ·········· ··11111··· ···11111·· ·········· ·········· ·········· ··········
·········· ·········· ·········· ·········· ·········· ···11111·· ·········· ·········· ·········· ··········
Dit laat de 10 lagen (van boven af) naast elkaar zien. Het is wat ruw, maar ik kan dit inmiddels goed lezen. Op laag 4 is te zien dat zelfs 3 platen elkaar overlappen, dus dit is geen goede oplossing.
Oplossingen
Dit programma, dat alle 49152 mogelijke permutaties afloopt in ongeveer 1,5 seconden, kwam met 12 oplossingen waarbij de platen in elkaar pasten. Ik heb de laatste oplossing ongeveer een uur geprobeerd in elkaar te zetten, en kon duidelijk zien dat deze klopte, maar het lukte mij niet deze in elkaar te zetten.
De oplossingen waren:
(valid) P1:D.fX.fYw P2:A.fX.fYb P3:E.fX.fYw P4:C.fX.fYb P5:F.fYw P6:B.fYb (attempt 25605)
(valid) P1:D.fYw P2:A.fX.fYb P3:E.fX.fYw P4:C.fX.fYb P5:F.fYw P6:B.fYb (attempt 25669)
(valid) P1:D.fX.fYw P2:A.fX.fYb P3:Fw P4:C.fX.fYb P5:E.fXw P6:B.fYb (attempt 32261)
(valid) P1:D.fYw P2:A.fX.fYb P3:Fw P4:C.fX.fYb P5:E.fXw P6:B.fYb (attempt 32325)
(valid) P1:F.fX.fYw P2:A.fX.fYb P3:Dw P4:C.fX.fYb P5:E.fXw P6:B.fYb (attempt 33477)
(valid) P1:F.fYw P2:A.fX.fYb P3:Dw P4:C.fX.fYb P5:E.fXw P6:B.fYb (attempt 34501)
(valid) P1:E.fXw P2:A.fX.fYb P3:Dw P4:C.fX.fYb P5:F.fYw P6:B.fYb (attempt 38597)
(valid) P1:Ew P2:A.fX.fYb P3:Dw P4:C.fX.fYb P5:F.fYw P6:B.fYb (attempt 38853)
(valid) P1:E.fXw P2:A.fX.fYb P3:Fw P4:C.fX.fYb P5:D.fYw P6:B.fYb (attempt 44613)
(valid) P1:Ew P2:A.fX.fYb P3:Fw P4:C.fX.fYb P5:D.fYw P6:B.fYb (attempt 44869)
(valid) P1:F.fX.fYw P2:A.fX.fYb P3:E.fX.fYw P4:C.fX.fYb P5:D.fYw P6:B.fYb (attempt 45125)
(valid) P1:F.fYw P2:A.fX.fYb P3:E.fX.fYw P4:C.fX.fYb P5:D.fYw P6:B.fYb (attempt 46149)
De uitwerking van de laatste oplossing daarbij was:
Solution 11: Matrix (valid) P1:F.fYw P2:A.fX.fYb P3:E.fX.fYw P4:C.fX.fYb P5:D.fYw P6:B.fYb
layer 0 layer 1 layer 2 layer 3 layer 4 layer 5 layer 6 layer 7 layer 8 layer 9
·········· ·········· ·········· ·········· ··11111··· ·········· ·········· ·········· ·········· ··········
·········· ·········· ·········· ·········· ··11111··· ···11111·· ·········· ·········· ·········· ··········
·········· ·····1···· ·····1···· ·····1···· ··11111··· ···11111·· ·········· ·····1···· ·····1···· ·····1····
····1····· ····11···· ····11···· ····11···· ··11·11··· ···11111·· ····1····· ····11···· ····11···· ·····1····
····1····· ····11···· ·111111111 ·111·11111 ·1····1111 ·111111111 ·111111111 ····1····· ····1····· ·····1····
····1····· ····11···· ····11···· 11111·111· 1111··111· 111···111· 111111111· 111111111· ····11···· ·····1····
····1····· ····11···· ····11···· ····11···· ··11111··· ···11111·· ····11···· ····11···· ····11···· ·····1····
····1····· ····1····· ····1····· ····1····· ··11111··· ···11111·· ····1····· ····1····· ····1····· ··········
·········· ·········· ·········· ·········· ··11111··· ···11111·· ·········· ·········· ·········· ··········
·········· ·········· ·········· ·········· ·········· ···11111·· ·········· ·········· ·········· ··········
Zoals te zien: geen overlappingen.
De oplossing uitvoeren
Tsja, nu heb ik dus 12 mogelijke oplossingen, maar hoe zet ik ze in elkaar? Wellicht zijn enkele van deze oplossingen uberhaupt niet in elkaar te zetten.
Het lijkt mij het handigste om het probleem om te keren, dus vanuit de oplossing te kijken hoe ik de platen kan verwijderen. Dan omdraaiend kan ik later de oplossing weer in elkaar zetten.
Elke plaat kan in 6 richtingen bewegen: links, rechts, naar voor en achter en omhoog en omlaag — ofwel -x, x, y, -y, -z en z. Als ik elk van de platen nou 1 eenheid in een richting verplaats krijg ik een nieuwe matrix, waarbij dezelfde regels gelden: als een van de waarden weer 2 of hoger is, is er een overlap en is dus geen legale move. We gaan gewoon alle mogelijke moves door, maar hoe komen we er nou achter wanneer iets klaar is? Ik denk dat als je een onderdeel 5 kanten op kan bewegen, dat het dan “vrij” is en je het kan verwijderen en met de andere platen verder, totdat je een oplossing hebt.
Stappenplan:
- Beweeg elke plaat elk van de 6 richtingen op, één eenheid, en check of het een geldige move is.
- Sla de geldige beurten op in een lijst, en bij een volgende geldige move, kijk of deze niet al in de lijst voorkomt (ter voorkoming van in rondjes werken)
- Als een van de platen 5 van de 6 kanten op kan bewegen, is deze “vrij” en dan kan deze verwijderd worden
Platen bewegen
Dit zou hartstikke simpel moeten zijn, en dat was het ook. Maar bij het twee platen achter elkaar verplaatsen kwam ik erachter dat ik op verschillende schaakborden dacht te spelen, maar een schaakstuk van het ene bord oppakte en op de andere een hokje verder neerzette. Dat heeft met object-oriented programmeren te maken; de oplossing was diepe kopiën overal van maken, en dat gaat mij later nog erg tegenwerken denk ik … maar voor nu werkt het.
Toen ik bij de laatste van de 12 mogelijke passende oplossingen, elk van de 6 platen 1 eenheid in elk van de 6 richtingen had verschoven, bleek dat élk van die 36 moves een ongeldige matrix met overlap op te leveren. Dat is interessant: de eerste oplossing is dus geldig, maar kan op geen enkele manier uit elkaar gehaald worden (of dus in elkaar gezet worden). Op naar de volgende matrix!
Bij de eerste matrix heb ik hetzelfde geprobeerd, maar daar waren 3 bewegingen mogelijk!
De plaat op positie 1 kon 1 eenheid omlaag (+z) schuiven, de plaat op positie 3 naar rechts (+x) en de plaat op positie 6 kon naar voren (+y).
Verdere moves
Nu was het de bedoeling om van deze 3 mogelijke bewegingen te kijken of ik verder kon schuiven. Dus deze moesten opgeslagen worden in een lijst, en dan door.
Ik heb een lijst gemaakt met movesToExplore (not uit te zoeken moves) en een lijst met movesExplored (al onderzochte moves). Elke move die gevonden wordt, wordt eerst getest of deze niet al in de movesExplored zat, zo nee, wordt die toegevoegd aan de movesToExplore.
Ik kon zien dat dit niet helemaal goed ging.
Bij de eerste opgeloste matrix kreeg ik
Solution 0: Matrix (valid) P1:D.fX.fYw P2:A.fX.fYb P3:E.fX.fYw P4:C.fX.fYb P5:F.fYw P6:B.fYb
...
pos:1 localshift:0,0,1 valid:true
pos:3 localshift:1,0,0 valid:true
pos:6 localshift:0,1,0 valid:true
Valid moves:3
Moves to explore:3 movesExplored:1
pos:1 localshift:0,0,-1 valid:true
pos:1 localshift:0,0,1 valid:true
Valid moves:2
Moves to explore:4 movesExplored:2
In regel 8 move ik de plate op position 1 -1 op de z-as, maar de oorspronkelijke move op regel 3 was juist +1 op de z-as. Deze regel zou dus moeten aangeven dat deze move al in de movesExplored zit … Oh in dit geval hoeft dat niet, omdat de oorspronkelijke matrix niet in de movesExplored zit.
Intermezzo: valsspelen
Ik ontdekte het bestaan van BurrTools, een programma dat claimt burr puzzels op te kunnen lossen.
Om het te installeren moest ik eerst fltk, libpng en OpenGL installeren. Die eerste twee gingen prima, maar het ./configure-script bleef maar zeuren over OpenGL. Uiteindelijk heb in ./configure –without-x gedaan, maar toen kreeg ik rare foutmeldingen van gcc over voxels. Het helpt niet dat Burrtools in mei 2013 (bijna 11 jaar geleden) voor het laatst bijgewerkt is. (En na het zoeken van alle tips om het programma te installeren moest die onnodig laatst-geinstalleerde programma’s verwijderen… Via deze tip kon ik het achterhalen, een simpel sudo apt-get remove g++ libqt5opengl5-dev libglfw3-dev libglew-dev mesa-common-dev libfltk1.3-dev libgl-dev libopengl-dev libglu1-mesa-dev libpng-dev libgl-dev freeglut3-dev haalde alles weg.)
In de help van BurrTools stond dat kon wat PuzzleSolver 3D ook kon. Dat programma probeerde ik te vinden, via deze site vond ik dat het op puzzle.cx zou staan, maar die site bestaat niet meer. Gelukkig kon ik via de Wayback Machine het programma wel downloaden (directe link, installer .exe – klik op eigen risico!). Dit windows-programma, gemaakt door André van Kammen (wellicht deze op linkedin), is voor het laatst bijgwerkt in 2000, maar het werkt wel (de website niet meer sinds 2008). De gratis versie werkt gewoon, je kan het resultaat alleen niet opslaan.
Het programma werkt gewoon, het is redelijk intuitief, alleen moet je bij het invoeren van de blokken op de Z-as even bedenken dat de slider omlaag, een hoger niveau betekent. Je moet dus vanaf de onderste laag beginnen met opbouwen.
Hiermee was het relatief eenvoudig om de puzzel op te lossen:
En ik denk ook dat ik het probleem gevonden heb: voor sommige moves is het nodig 2 stukken tegelijk te bewegen, en dat is iets waar mijn programma tot nu toe géén rekening mee houdt!
Bij de video hierboven is trouwens plaat 1 gelijk aan A, 2 aan b enzovoorts.
Ik ga kijken of ik dat nog kan implementeren, maar ik heb nu de oplossing, dus dat staat even op een laag pitje. Ik denk dat ik eerder voor mijzelf een exemplaar van de puzzel ga maken!
