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" 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 (vedi "cerca veloce 2.pl") e pressocché gli stessi risultati
pratici.
Ho provato anche a muovere 3 facce ("cerca3.x.pl": 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" ho avuto degli ulteriori risultati.
Finalmente, sfruttando le sequenze trovate, posso mirare ad una soluzione del cubo. Dopo alcune prove (vedi "Risolvi.0.pl"
e "Risolvi.pl": 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" 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: 1) Poiché la larghezza dell'albero cresce velocemente, parimenti cresce la memoria utilizzata,
ed una volta esaurita la RAM il processo di calcolo si rallenta notevolmente a causa degli swap tra RAM ed hard-disk; 2)
Per ogni ulteriore passo in profondità il numero di posizioni cresce enormemente (di un fattore che va da 8 a 24 ), per cui
le ricerche a profondità minori risultano trascurabili.
Un'altra cosa da notare è la ricerca per gradi: prima si posizionano alcuni vertici, poi si riparte la ricerca
di nuovi aggiustamento a partire da tale stato. Questo assomiglia all'algoritmo A*, che però non sarebbe adeguato nella
prossimità del goal, infatti per mettere a posto gli ultimi 2 vertici bisogna ritornare a configurazioni peggiori (forse
si otterrebbe una qualche soluzione con il Simulated Annealing). Uno dei miei intenti era anche quello di trovare il numero
minore di mosse, però alla fine nella ricerca considero con lo stesso peso una mossa singola o una sequenza da 12 mosse.
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: 37 secondi per posizionarli.
In Spigoli1.pl, con sequenze che spostano 2 soli spigoli anziché 3, il tempo è passato a meno di 1 secondo.
Con Spigoli3.pl 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 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 è 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.