I cubettàti

Marco Beri non si è accontentato di sviluppare una preoccupante dipendenza dal progetto Eulero: quando non è impegnato a risolvere quesiti matematici, si diletta a porne. Non molto tempo fa ha proposto ai lettori di Stacktrace il problema del cubetto, un puzzle tridimensionale formato da sei pezzi con i quali è possibile formare un cubo, riuscendo ad incastrare tutti i pezzi tra loro.

Quante soluzioni esistono? Esistono soluzioni con tutte le facce esposte? Per quanto tempo ancora i familiari sopporteranno Marco, prima di cacciarlo di casa? Ad alcuna di queste domande possiamo finalmente dare una risposta!

Qualcuno dei lettori ha accettato la sfida: più persone hanno imbracciato il loro editor e affrontato il problema.

Il primo a dare una risposta è stato Riccardo Vianello, che ha inviato la sua soluzione il 28 febbraio. Si tratta di uno script Python che effettua la ricerca con backtrack ma non sullo stack di chiamate: la funzione di ricerca non è ricorsiva ma iterativa e lo stack è esplicito:

def search(edge_matrix, flipped):
    solutions = []
    stack = [[edge_matrix, -1, -1, {}, 0]]
    while len(stack) > 0:
        state = stack[-1]
        if done(state):
            solutions.append(state[3])
            stack.pop()
        elif dead(state):
            stack.pop()
        else:
            if has_child(state):
                child_state = build_child(state)
                if valid(child_state, flipped): stack.append(child_state)
            else:
                stack.pop()
    return solutions

L’implementazione della collisione è piuttosto complessa.

L’11 marzo giunge la soluzione di Fabio Fabbri che, come anticipato in un suo commento, ha deciso di implementare la sua soluzione in Prolog. Scelta interessante: il Prolog è in effetti un risolutore di problemi. I suoi programmi sono descrizioni dichiarative di sistemi logici, fatti di assiomi e produzioni logiche:

mortale(X) :- uomo(X)      % X è mortale se X è un uomo.
uomo(socrate).             % Socrate è un uomo.

e il linguaggio è in grado di verificare la validità di un predicato all’interno del sistema descritto:

?- mortale(socrate).       % Socrate è mortale?

Fabio è andato molto oltre i sillogismi, fornendoci una soluzione in Prolog al cubetto. Come per la soluzione di Riccardo, le relazioni tra gli spigoli delle facce ruotate sono esplicitate nel codice, con controlli simili a:

1 =:= X7+R20,
1 =:= X8+R19,
1 =:= X9+R18,
1 =:= X10+R17,

che verificano se per ogni posizione sullo spigolo ci sia un un solo cubettino tra le due facce.

Ma… colpo di scena! Il 13 marzo ci scrive nuovamente Riccardo ammettendo che:

con un certo disappunto mi tocca constatare di averti inviato uno
script bacato. Di fatto pare abbia determinato la soluzione corretta
senza accorgermi del problema per puro caso. Con la particolare
configurazione iniziale dell’input il baco non si e` manifestato, ma
si e` reso evidente permutando le tessere e modificando cosi` le
condizioni inziali della ricerca…

eh, già, la risposta in effetti è corretta, ed era quanto si richiedeva… ma ancora più corretto è stato l’autore. Bravo 😉

Il 22 marzo è anche giunta la soluzione di Matteo Bertini, anch’essa sviluppata in Python. Matteo ha perfino usato doctest per documentare le sue funzioni, in modo da trasformare gli esempi in test di regressione.

Il cubetto rimontato

Allora, quante soluzioni ha il cubetto? Beh… dipende!

Come è ovvio la stessa soluzione (intesa come disposizione reciproca dei pezzi) sarà "trovata" da un programma in diverse posizioni assolute: il cubetto può mostrare ognuna delle sue facce rivolta verso l’alto e per ogni faccia essere ruotato in 4 diverse posizioni, per cui ogni soluzione può essere "vista" in 24 modi diversi. Tutti i nostri eroi hanno risolto il problema con un semplice accorgimento: fissando la prima faccia in una certa posizione e cercando di incastrare i restanti cinque pezzi nei modi possibili. Questo accorgimento previene un’altra fonte di simmetria: quella interno-esterno per cui, data una soluzione, se ne può facilmente trovare un’altra che ha tutte le facce invertite. Se si escludono queste simmetrie, il problema risulta avere 6 soluzioni.

Si osserva però che uno dei pezzi è simmetrico, quindi ogni soluzione viene trovata due volte distinte (con la faccia del pezzo rivolto all’interno o all’esterno). Potrebbe dunque essere corretto considerare 3 le soluzioni distinte. Ma allo stesso modo potrebbero essere considerate "non banali" le inversioni complete interno-esterno, portando le soluzioni a 12…

C’è una risposta certa al quesito? Forse ci sarebbe stata con dei vincoli più stringenti, imponendo delle specifiche più rigide, con una raccolta di casi di uso puntigliosa e tanti pupazzetti disegnati con le loro nuvolette… ma preferiemo restare col dubbio e col piacere di aver avuto un bel problema con cui giocare e la possibilità di scrivere codice divertente.

Non ci sono soluzioni che presentano tutte le facce dei pezzi all’esterno: ce n’è solo una in cui la faccia è mostrata su 5 pezzi: sufficienti per i fini pubblicitari a cui il cubetto era destinato (prima di diventare feticcio e luogo di culto di accaniti smanettoni).

Nonstante l’ambiguità, avevamo promesso una classifica, e il giudizio insindacabile della redazione è quello di attenersi all’ordine di arrivo delle risposte, dunque:

  1. Riccardo Vianello
  2. Fabio Fabbri
  3. Matteo Bertini

Sappiate che non saranno ammessi reclami contro il giudizio: vista l’esiguità del premio (proprio nulla) direi che non vale la pena affrontare il nostro nutrito staff legale. Teniamo i nostri avvocati a digiuno proprio per queste occasioni!

La storia del cubetto non finisce qui: a breve scopriremo un altro frutto inaspettato prodotto dal quesito…

Comments

  1. …a proposito di dipendenze da progettoEuler…o ne sono diventato quasi diependente….a causa vostra…
    …adesso ne sono un pò uscito comunque…;-)
    grazie

Policy per i commenti: Apprezzo moltissimo i vostri commenti, critiche incluse. Per evitare spam e troll, e far rimanere il discorso civile, i commenti sono moderati e prontamente approvati poco dopo il loro invio.