Il cubo è composto da 8 "vertici" (ognuno con tre faccette) e da 12 "spigoli" (con due faccette).
Il numero totale di possibili figure diverse è dato da dalle combinazioni di tutti i vertici con tutti gli spigoli,
contando anche le orientazioni dei cubetti, cioè: 8! * 38 * 12! * 212 =
5,19 * 1020.
È pertanto impensabile attaccare il problema direttamente con la forza bruta senza utilizzare della conoscenza.
D'altra parte é anche molto difficile costruire delle euristiche basate sulla distanza dei cubetti dal goal,
visto che sono sufficienti quattro mosse per portare fuori posto tutti i cubetti; inoltre con tre mosse è possibile
portare un cubetto alla massima distanza dalla posizione originale.
L'unica possibilità è contare il numero di cubetti fuori posto per avere una idea più o meno indicativa dello stato del cubo;
non è comunque detto che uno stato che abbia un numero maggiore di cubetti al posto giusto sia più vicino al goal:
spesso per riuscire a mettere a posto un ulteriore cubetto bisogna prima passare per uno stato in cui regna la confusione.
Ripeto che con sole tre mosse tutti i cubetti possono essere portati fuori posto!
Per un uomo la parte più difficoltosa nella risoluzione del cubo è quella finale: il problema è riuscire a sistemare gli
ultimi cubetti senza spostare quelli già a posto. Per far ciò si utilizzano delle sequenze di mosse che permettono,
alla fine della sequenza, di spostare solo un numero limitato di pezzi. Ad esempio è possibile, con dodici mosse elementari,
spostare reciprocamente quattro vertici lasciando tutti gli altri pezzi al loro posto (naturalmente durante la sequenza
anche gli altri pezzi vengono mossi, ma la sequenza è tale che alla fine si aggiusta tutto).
Ho pensato che sarebbe stato utile riuscire a trovare il maggior numero di queste sequenze "magiche".
Per trovare la soluzione finale è utile riuscire a scomporre il problema in sottoproblemi:
sistemare prima tutti i vertici, poi tutti gli spigoli o viceversa; questo è possibile se riesco a trovare due sequenze
magiche diverse che mi permettano di spostare solo un certo numero di vertici senza toccare gli spigoli, oppure spostare
alcuni spigoli senza muovere i vertici dal loro posto.
Con il programma "Cerca veloce.pl" (zip)
sono riuscito a trovare una combinazione che permette di spostare solo 3 spigoli in 10
mosse elementari (tempo di ricerca 37 secondi), oppure solo 4 vertici in 12 mosse (tempo di ricerca 300 secondi).
Era possibile muovere solo la faccia bianca e quella verde.
Se elimino le mosse da due ottengo delle prestazioni migliori e pressocché gli stessi risultati
pratici.
Ho provato anche a muovere 3 facce ("cerca3.x.pl": vedi in fondo a "cerca veloce.pl"), ma nessun nuovo risultato utile.
Mi sono ora concentrato solo sui vertici, sfruttando una delle sequenza di 12 mosse che mi permette di spostare solo 4 vertici: con "Cerca12.pl" (zip) ho avuto degli ulteriori risultati.
Finalmente, sfruttando le sequenze trovate, posso mirare ad una soluzione del cubo. Dopo alcune prove
(vedi "Risolvi0.pl" (zip)
: 50 minuti) sono approdato ad una soluzione discreta per i vertici.
Proprio analizzando le sequenze mi è venuto in mente di scomporre il problema ulteriormente:
in "Vertici.pl" (zip) ho fatto un
programma che, partendo da una configurazione in cui nessun pezzo è a posto, arriva a posizionare correttamente tutti i
vertici lasciando inalterati gli spigoli. La ricerca è stata scomposta in due parti: posizionamento dei vertici e
orientamento degli stessi, sfruttando due diversi set di sequenze. La soluzione arriva in meno di 2 secondi.
Benchè il programma esegua delle ricerche depth first, in realtà la filosofia generale è breadth first; ho fatto questa
scelta per due validi motivi:
Sono poi passato agli spigoli: prima ho tentato con sequenze di mosse da 10 che non modificavano i vertici, ma per una
soluzione ci voleva più di un'ora (quando ci arrivava in tempo utile). Così, visto che già riuscivo a sistemare i vertici
senza più toccare gli spigoli, ho pensato che fosse utile disinteressarmi dei vertici mentre sistemavo gli spigoli. Primi
risultati con "Spigoli.pl" (zip):
37 secondi per posizionarli.
In "Spigoli1.pl" (zip), con sequenze che spostano 2 soli spigoli
anziché 3, il tempo è passato a meno di 1 secondo.
Con "Spigoli3.pl" (zip) ho cercato di diminuire il numero di mosse
totali necessarie: posizionare i primi spigoli è molto più che posizionare quelli successivi, quindi è possibile utilizzare
solo mosse singole.
Con "Spigoli4.pl" (zip) ho perseverato su questa strada e pur
ottenendo delle prestazioni peggiori, ho migliorato di molto il numero di mosse necessarie. Ho anche seguito una
metodologia fin qui non provata: anziché pura ricerca di stati positivi dopo l'applicazione casuale di mosse diverse,
analizzo lo stato del cubo per applicare la sequenza di mosse adeguata.
Rubik.pl (zip) è il programma in versione definitiva in cui ho privilegiato
la velocità rispetto al numero di mosse. Ho inoltre aggiunto vari predicati per modificare manualmente o casualmente lo
stato del cubo.
Modifiche per migliorare l'algoritmo (in velocità e/o in numero di mosse) ce ne sarebbero a volontà:
Tutti i test sono stati realizzati con Sicstus prolog 3.6 su un processore Pentium a 166 MHz, RAM di 32 MB
(comunque ininfluente) e sistema operativo windows NT, di cui ho utilizzato il "task manager" per calcolare l'utilizzo
della CPU da parte di ogni simulazione.
Le notizie finali le ho ricavete da una pagina internet pubblicata da Jake Olefsky che a sua volta si riferisce a :
Discover, March 1986 v7 p81(8), Full Text COPYRIGHT Family Media Inc. 1986.
Per esplorare sul web: http://www.snipercade.com/cubeman/