Modo per calcolare la torsione tetrade totale di un cubo di rubik
Sto lavorando a un'implementazione dell'algoritmo di Thistlewaite per risolvere un cubo di Rubik e ora sto affrontando il problema dei colpi di scena tetradi. Grazie a questa risposta , capisco cosa sono e come riducono la quantità di stati nella fase 3, ma il problema che ho è trovare un modo per calcolare la torsione tetradica totale di un cubo solo dal suo stato.
Il modo in cui sto implementando questo algoritmo non è con una ricerca in ampiezza e quindi non posso semplicemente utilizzare la condizione più forte trovata qui e qui per sapere se ho finito con la fase 3 poiché non è utile per me. Il modo in cui lo sto facendo è precalcolare le tabelle di ricerca e cercarle per sapere come risolvere un certo stato. Per questo motivo ho bisogno di caratterizzare completamente le informazioni necessarie per distinguere i diversi stati della fase 3. Ho già fatto tetradi d'angolo, fette di bordi e parità, l'ultima cosa di cui ho bisogno è un modo per esprimere la torsione tetradica di uno stato (o qualsiasi informazione equivalente). La cosa migliore sarebbe semplicemente essere in grado di dare un valore compreso tra 0, 1 o 2 e usarlo per descrivere la torsione totale.
Spero che la mia domanda sia chiara e, in caso contrario, sentiti libero di porre domande nei commenti, farò del mio meglio per spiegarla ulteriormente.
Risposte
È piuttosto difficile estrarre queste informazioni direttamente dalle posizioni attuali dei pezzi d'angolo. Il modo di gran lunga più semplice è provare effettivamente a risolvere quei pezzi d'angolo usando solo mezzi giri (ignorando i pezzi di bordo) e vedere fino a che punto arrivi.
Per ora presumo che i pezzi d'angolo siano già posizionati nelle loro orbite tetradiche corrette {UFR, UBL, DFL, DBR} e {UFL, UBR, DFR, DBL}. Puoi risolvere i pezzi di una tetrade molto facilmente, non più di mezzo giro per ogni pezzo, al massimo 3 mosse in totale. Ad esempio, risolvi DBR utilizzando al massimo uno tra {D2, B2, R2}, quindi DFL utilizzando al massimo uno tra {F2, L2} e infine UBL utilizzando {U2} se necessario, il che lascia risolto anche UFR.
Quindi risolvi un pezzo della seconda tetrade, ad esempio DBL, utilizzando una delle sequenze di mosse {F2 L2 F2 U2, U2 F2 U2 L2, L2 U2 L2 F2}. Queste sequenze di mosse eseguono un doppio scambio sui quattro pezzi della seconda tetrade e sono le uniche permutazioni possibili che mantengono fissa la prima tetrade.
Questo lascia tre pezzi irrisolti, {UFL, UBR, DFR}. Questi possono essere in una qualsiasi delle 3!=6 permutazioni. Queste 6 possibilità rappresentano il tetrad twist in combinazione con la parità di permutazione, quindi se mappi questa permutazione su un numero compreso tra 0 e 5, hai codificato sia la parità di permutazione che il tetrad twist in un unico numero.
Per l'algoritmo Thistlethwaite probabilmente vorrai codificare una posizione arbitraria del terzo stadio dell'algoritmo. Questo deve essere fatto in modo coerente, con ciò intendo dire che se due diverse posizioni vengono portate nel quarto stadio dalla stessa sequenza di mosse (cioè dopo aver applicato la sequenza di mosse a quelle posizioni diventano entrambe risolvibili usando solo mezzi giri) allora queste due posizioni devono avere la stessa codifica per la fase 3.
Presumibilmente il tuo programma elenca le posizioni degli angoli del cubo in un particolare ordine fisso. Ad esempio, potresti avere un array di lunghezza 8 che rappresenta le posizioni nell'ordine
UFR , UFL, UBL , UBR, DFR, DFL , DBL, DBR .
Ho messo in grassetto quelle posizioni che rappresentano una delle tetradi, quelle all'indice 0, 2, 5, 7 nell'array. Potresti aver scelto una diversa convenzione di ordinamento nel tuo programma, ma il metodo è lo stesso.
Supponiamo ora di avere una posizione arbitraria del cubo della fase 3, una permutazione casuale di quegli 8 angoli, ad esempio:
UBR, UBL , DBR , DFR, DFL , UFR , UFL, DBL.
Un modo semplice e coerente per separare i pezzi nelle due tetradi è separare letteralmente i due tipi di pezzi senza cambiare il loro ordine relativo:
UBL , DBR , DFL , UFR
UBR, DFR, UFL, DBL.
E poi inserirli nell'array di archiviazione, in ordine, ciascuno nel proprio insieme corretto di posizioni tetradiche. Quindi il primo set va negli indici 0,2,5,7, l'altro negli indici 1,3,4,6.
UBL , UBR, DBR, DFR, UFL, DFL , DBL, UFR .
Ora puoi applicare la tecnica di risoluzione che ho spiegato all'inizio, per ottenere una codifica coerente delle posizioni tetrad twist e parity.
Quanto sopra presuppone che tu usi un unico modo standardizzato per rappresentare il cubo e applichi le mosse a quello. Potresti invece voler mantenere i due elenchi separati dei pezzi tetradi come una rappresentazione semplificata di questa posizione e permutarli direttamente mentre li risolvi per estrarre la codifica twist + parity.
Puoi dare un'occhiata ad alcuni dei programmi in questo vecchio concorso di programmazione del cubo , anche se non sono sicuro che saranno di grande aiuto poiché sono scritti per concisione, non per intelligibilità.