Rubik's Illusions

Il metodo PBF (Partial Brute Force) è un metodo sperimentale per il risolutore automatico.

Mentre un metodo Brute Force totale richiederebbe migliaia di anni di calcoli per trovare la soluzione minima di un singolo Cubo di Rubik, il metodo parziale è un approccio metà algoritmico e metà Brute Force in sperimentazione in tempo reale su questo sito web, il cui obiettivo è quello di ridurre il risolutore automatico a calcolare un numero di mosse più accettabile dell'attuale, anche se non minimo.

L'idea è quella di riempire delle tabelle che interrogate restituiscono il numero minimo di mosse da una posizione a un'altra del Cubo di Rubik.

Per esempio la tabella completa che è stata fin'ora realizzata è quella che dal Cubo di Rubik in qualunque posizione porta alla soluzione della Croce, usata nel metodo algoritmico a strati.

Per creare questa tabella sono stati usati diversi strumenti software che hanno consentito di scandagliare tutte le possibili sequenze di mosse fino a completare la tabella. Questi strumenti saranno discussi e pubblicati su questo sito web.

La tabella realizzata è interrogabile nel Risolutore automatico attraverso il pulsante Solve the Cross.

Considerazioni generali

Un metodo di risoluzione per il Cubo di Rubik consiste, partendo dal Cubo completamente mischiato, nel passare attraverso un insieme di configurazioni stabilite fino alla configurazione Cubo risolto. Possiamo chiamare il passaggio da una configurazione all'altra sottometodo. Per ogni sottometodo l'autore del metodo sviluppa una serie di sequenze di mosse (o algoritmi) che risolvono il sottometodo in ogni caso, cioè in qualunque modo siano posizionate le piastrelle.

In una sequenza di sottometodi contigui che costituiscano un metodo di soluzione, il primo sottometodo non ha vincoli da rispettare, ma a mano a mano che si avanza nella soluzione aumentano i vincoli, dettati dalle piastrelle che sono state definitivamente sistemate fino a giungere all'ultima configurazione di vincolo completo e quindi di Cubo risolto.

L'obiettivo da raggiungere è quello di creare per ogni sottometodo una tabella completa di tutte le possibili configurazioni di partenza, che fornisce per ognuna di esse la soluzione più breve per completare il sottometodo.

L'idea è quella di partire, per ogni sottometodo, dalla configurazione di arrivo, applicare tutte le possibili sequenze di mosse e tenere nella tabella quelle sequenze che rispettano il vincolo d'inizio del sottometodo per le quali le piastrelle interessate nel vincolo di fine abbiano posizioni non già rilevate.

Per fare questa operazione in modo efficiente abbiamo bisogno di un elenco di sequenze di mosse ordinate lessicograficamente, che sia però generabile parzialmente senza la necessità di partire dal primo elemento della lista.

Posizione lessicografica delle sequenze di mosse

Come ben sappiamo sul Cubo di Rubik è possibile evidenziare 18 tipi di mosse differenti che possono essere effettuate. È utile, per la creazione del nostro metodo, definire un algoritmo che faccia corrispondere a ogni numero intero una sequenza di mosse, in modo che le sequenze più corte vengano sempre prima di quelle più lunghe, e in modo che sia un insieme completo e il meno possibile ripetitivo.

Tutte queste caratteristiche sono necessarie per fare in modo che la corrispondenza contenga il minor numero di elementi inutili, perché sia possibile creare l'algoritmo Brute Force che provi tutte le possibili sequenze di mosse nel minor tempo possibile.

Quest'ordine lessicografico è inoltre necessario per permettere di poter calcolare in spazi e tempi separati diversi gruppi di elementi della lista, in modo da sfruttare i moderni processori multicore e la programmazione distribuita.

Come unico vincolo per far sì che molte sequenze inutili non siano presenti nell'elenco poniamo che le sequenze non devono contenere mosse ripetute due volte di seguito, o, più in generale, due mosse consecutive che interessano lo stesso oggetto.

Possiamo concludere che l'elenco che vogliamo, se costituito da 6 mosse differenti rappresentate dai numeri da 1 a 6 sia di questo tipo:

Per risolvere questo problema bisogna prima risolvere un problema più semplice, cioè calcolare l'ordine lessicografico delle sequenze di una lunghezza data m.

Il ragionamento che facciamo per risolvere questo problema è: ho 6 possibilità di scelta per il primo elemento e cinque per tutti quelli successivi, poiché non posso ripetere una mossa appena fatta.

Questo approccio è stato adottato per generare le sequenze di mosse considerando le 18 mosse possibili nel Cubo di Rubik.

Il seguente metodo Java ricorsivo prende come parametri il numero della sequenza, n, e il numero di mosse della sequenza, m.

public static int[] getSequence(long n, int m) {
    int[] sequence = new int[m];
 
    if (m == 1) {
        sequence[0] = (int)(n + 1);
    } else if (m > 1) {
        int[] subsequence = getSequence(n / 15, m - 1);
     
        for (int i = 0; i < subsequence.length; i++)
            sequence[i] = subsequence[i];
     
        int new_coeff = (int)(n % 15) + 1;
    }
}

Questo metodo non tiene conto del fatto che una mossa non può essere ripetuta ma soltanto del fatto che ci sono solo 15 possibili scelte nelle mosse successiva alla prima. Una opportuna tabella può aiutarci a trasformare le sequenze generate da questo algoritmo in sequence utili.

A questo punto risolvere il caso generale richiede soltanto l'applicazione di una correzione. Per ogni numero di sequenza sappiamo che esso slitta in avanti di x posizioni quante sono le combinazioni totali di lunghezza minore. Allo scopo può essere utile una tabella già calcolata per ogni profondità m.