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.