A treasure chest as an interlocking puzzleUn baule del tesoro come rompicapo a incastro

A chest made of cubes is split into pieces so that, as long as the chest is whole, only one piece can move, the key, which slides out along one direction; once it is out, another single piece becomes the key of what is left, and so on until two pieces remain. The chest then comes apart in one order only, and every intermediate assembly is itself a puzzle that holds together: these are the recursive interlocking puzzles of Song, Fu and Cohen-Or (2012), here on a grid of 5 or 6 cubes across, searched in the browser and checked exactly at every stage.

Un baule fatto di cubi è diviso in pezzi in modo che, finché il baule è intero, uno solo possa muoversi, la chiave, che esce scorrendo lungo una direzione; quando è fuori, un altro solo pezzo diventa la chiave di ciò che resta, e così via finché restano due pezzi. Il baule allora si smonta in un solo ordine, e ogni insieme intermedio è a sua volta un rompicapo che sta insieme: sono i rompicapi a incastro ricorsivi di Song, Fu e Cohen-Or (2012), qui su una griglia di 5 o 6 cubi di larghezza, cercati nel browser e verificati in modo esatto a ogni passo.

The pieces in their colours, each sliding out after the one before; drag to turn, use the wheel or pinch to zoom.I pezzi nei loro colori, ognuno esce dopo il precedente; trascina per ruotare, usa la rotella o il pizzico per lo zoom.

The order of disassemblyL'ordine di smontaggio

    For a direction e among the six of the grid, the blocking graph has an arc from piece a to piece b when a, moved by one cube along e, would enter b. A set of pieces can move along e without the others exactly when no arc leaves it, so that the smallest set that must move with a piece p is the set of the pieces reachable from p (its closure). A stage with key K is interlocked when, for each of the six directions and each piece p other than K, the closure of p holds every piece but K: then the only sets that can move are K alone and the rest, which is K moving the other way. To this test the scene adds that K can slide along its direction to infinity, cube after cube, without meeting another piece. It is a test of translations by whole cubes along the axes, the moves that voxel pieces allow; the same graphs underlie the later analysis of Wang, Song and Pauly (2018).

    Per una direzione e fra le sei della griglia, il grafo di blocco ha un arco dal pezzo a al pezzo b quando a, spostato di un cubo lungo e, entrerebbe in b. Un insieme di pezzi può muoversi lungo e senza gli altri esattamente quando nessun arco ne esce, così che il più piccolo insieme che deve muoversi con un pezzo p è l'insieme dei pezzi raggiungibili da p (la sua chiusura). Un passo con chiave K è a incastro quando, per ognuna delle sei direzioni e ogni pezzo p diverso da K, la chiusura di p contiene tutti i pezzi tranne K: allora i soli insiemi che possono muoversi sono K da solo e il resto, cioè K che si muove nel verso opposto. A questo test la scena aggiunge che K possa scorrere lungo la sua direzione fino all'infinito, cubo dopo cubo, senza incontrare un altro pezzo. È un test di traslazioni di cubi interi lungo gli assi, le mosse che i pezzi di voxel permettono; gli stessi grafi sono alla base dell'analisi successiva di Wang, Song e Pauly (2018).

    Song et al. build the pieces one at a time, from the key inwards, with rules that make each new piece removable along one direction and blocked in the others by the pieces already made, so that the property holds by construction on grids of hundreds of cubes. The scene uses a simpler search that suits grids of 70 or 84 cubes: the pieces are first grown at random from the seed, each made of columns of cubes that run out of the remaining chest along its direction; then simulated annealing moves one cube at a time to a neighbouring piece, keeping every piece connected and of 3 cubes at least, and lowers a score that counts, at every stage of the best order found, the pieces left out of a closure and a key that cannot slide out. A split is shown as interlocked only when the score is 0, i.e., when the test above passes at every stage. The search is deterministic given the seed; for 3 to 7 pieces it has always ended at 0 in the cases I tried (a few seconds at most), but it is not a proof that it always will, and the page says so when it stops short after 20000 moves.

    Song e gli altri costruiscono i pezzi uno alla volta, dalla chiave verso l'interno, con regole che rendono ogni nuovo pezzo estraibile lungo una direzione e bloccato nelle altre dai pezzi già fatti, così che la proprietà vale per costruzione su griglie di centinaia di cubi. La scena usa una ricerca più semplice, adatta a griglie di 70 o 84 cubi: i pezzi sono prima fatti crescere a caso dal seme, ognuno fatto di colonne di cubi che escono dal resto del baule lungo la sua direzione; poi un algoritmo di ricottura simulata sposta un cubo alla volta a un pezzo vicino, tenendo ogni pezzo connesso e di almeno 3 cubi, e abbassa un punteggio che conta, a ogni passo del miglior ordine trovato, i pezzi lasciati fuori da una chiusura e una chiave che non può uscire. Una divisione è mostrata come a incastro solo quando il punteggio è 0, cioè quando il test qui sopra passa a ogni passo. La ricerca è deterministica dato il seme; da 3 a 7 pezzi è sempre arrivata a 0 nei casi che ho provato (al più qualche secondo), ma questo non prova che ci arrivi sempre, e la pagina lo dice quando si ferma prima, dopo 20000 mosse.

    Download for 3D printingScarica per la stampa 3D

    A 3D print of this chestUna stampa 3D di questo baule

    The chest can be ordered as a 3D print, as separate pieces to put together. The request sends the link to the chest as it is on the screen, with its split.

    Puoi ordinare il baule come stampa 3D, in pezzi separati da montare. La richiesta manda il link al baule così com'è sullo schermo, con la sua divisione.

    One closed solid per piece, side by side on the bed, each turned onto the face that leaves the fewest cubes with nothing of the piece below them; the status line gives how many such cubes remain, which need supports. Every piece is shrunk by half the clearance on each face, so that two pieces that touch in the chest are the clearance apart (0.2 mm by default). Two iron bands and a keyhole are cut 0.6 mm deep into the outer faces only, so that they never add material where two pieces slide.

    Un solido chiuso per pezzo, affiancati sul piatto, ognuno girato sulla faccia che lascia meno cubi senza niente del pezzo sotto di loro; la riga di stato dice quanti di questi cubi restano, che richiedono supporti. Ogni pezzo è ridotto di metà del gioco su ogni faccia, così che due pezzi che si toccano nel baule distano quanto il gioco (0.2 mm come default). Due bande di ferro e un buco della serratura sono incisi per 0.6 mm solo sulle facce esterne, così da non aggiungere mai materiale dove due pezzi scorrono.