Come costruire una rappresentazione cubica del cubo di un rubik, dato un array

Ci sono alcuni modi per farlo.

Oltre ai sei array 3x3 contenenti i colori degli adesivi, potresti avere una matrice 3x3x3 che rappresenta i cubi solidi. (La cella interna di questo array può essere ignorata.) Le celle della matrice 3x3x3 potrebbero quindi contenere numeri interi (o puntatori a oggetti più dettagliati) che descrivono la posizione originale di ciascun cubo. Devi solo assicurarti di eseguire la "rotazione" appropriata della matrice 3x3x3 ogni volta che "ruota" gli adesivi.

Oppure potresti semplicemente mettere tutto in un array 5x5x5. L'array centrale 3x3x3 potrebbe rappresentare le parti solide del cubo e l'array 3x3 centrale di celle su ciascuna faccia dell'array 5x5x5 potrebbe rappresentare gli adesivi.

Un'altra alternativa: solo un array 3x3x3, in cui ogni cella contiene un puntatore a una struttura. La struttura identifica la posizione originale dei cubetti e i colori e le posizioni degli adesivi sui suoi volti. La struttura contiene anche un intero modificabile che descrive l'orientamento del cubo: un valore particolare (per esempio, 0) per l'orientamento che il cubo "dovrebbe" avere in un cubo completamente risolto e altri 23 valori che rappresentano gli altri possibili orientamenti del cubo. cubie dopo una sequenza di rotazioni. È inoltre necessaria una funzione (che potrebbe essere una semplice ricerca tabella) che indica quale orientamento risulta da ogni possibile quarto di giro applicato a ciascun orientamento possibile. Probabilmente troverai anche l'uso per una funzione che dice, per ciascun orientamento, quale faccia dell'originale (orientamento 0) cubie è in alto, in basso, a sinistra e così via. Per ruotare una porzione del cubo, devi ovviamente permutare il contenuto delle celle mobili, ma devi anche modificare correttamente l'orientamento di ogni cubetto nella fetta ruotata (inclusi i cubi al centro della faccia per un rotazione del viso, anche se la posizione del cucciolo non si muove).

Sembra che potresti gradire la mia risposta qui: link

L'idea di base è:

1. Indirizza il cubo in un sistema di coordinate x-y-z, con un centro a (0, 0, 0).
2. Una classe Piece memorizza una posizione (x, y, z ) e colora (cx, cy, cz) . The Piece sa quali colori adesivi sono su quale asse (x, y o z) ma non sa in quale direzione è rivolto l'adesivo.
3. Il cubo memorizza una lista non ordinata di pezzi.
4. Le rotazioni vengono eseguite aggiornando la posizione e i colori dei pezzi pertinenti.

Questo è bello perché tutta la logica di rotazione è limitata alla classe Piece. Un pezzo non conosce il suo orientamento, ma non ne ha bisogno. L'orientamento di un Pezzo dipende strettamente dalla sua posizione: l'angolo a (-1, -1, -1) è l'angolo LEFT-UP-BACK.

Qui di seguito utilizzo il termine sotto cubi per il termine cubie. Per il 4x4 uso i numeri da 1 a 56 per modellare ciascun cubo. Ho e matrice per i colori cioè ogni voce sarebbe simile a "G > GY > YR > R" questa è per un cubo d'angolo.
Questo array verrà aggiornato man mano che le mosse vengono eseguite perché i colori puntano ">" a lati fissi diversi. Per la posizione dei cubetti uso un set di 12 set: un set per ogni tipo di movimento. 6 set contengono 16 cubetti. E 6 set hanno 12 cubetti in loro. Identifico questi set con un codice di 3 lettere. "SBS" per set lato blu. I set vengono aggiornati man mano che le mosse vengono fatte. C'è un array 4x4 che contiene i tre tre codici lettera che definiscono i tre set per la posizione sul cubo. Questi non cambiano. Ho un enum che collega i 3 codici lettera all'indice di un array dove tengo i set. Io uso un algoritmo di rotazione della matrice per aggiornare i set con ogni mossa. Ciò comporta la rimozione dei blocchi dai vari set inserendoli in un array 2D che esegue l'algoritmo di rotazione e quindi inserendo i blocchi nelle loro nuove case nei set.

Dall'esperienza personale, l'utilizzo di un set per tenere traccia di ogni parte rotazionale del cubo funziona bene. Ogni sub cubo è in tre set non mater le dimensioni del cubo di rubik. Quindi per trovare un sub cubo in un punto in cui sul cubo del rubik si prende l'intersezione dei tre set (il risultato è un sub cubo). Per eseguire una mossa, rimuovi i cubetti sub effettivi dai set coinvolti nella mossa e poi rimettili nei set che li prendono come risultato del movimento.

Il cubo 4 x 4 avrà 12 serie. 6 set per le 6 facce e 6 set per le sei bande che girano attorno al cubo. Le facce hanno ciascuna 16 sub cubi e le fasce hanno 12 sub-cuccioli. Ci sono un totale di 56 sub cubi. Ogni sub cubo contiene informazioni sul colore e la direzione dei colori. Lo stesso cubo di rubik è un array 4: 4 di 4 con ogni elemento che ha informazioni costituite dai 3 set che definiscono il sub cubo in quella posizione.

Dipende tutto da cosa vuoi fare. Considerare il problema delle otto regine di classe in "Algorithms + Data Structures = Programs". Una rappresentazione a scacchiera per risolvere il problema delle otto regine è un bitset di lenth 8 (indice = numero di colonna, bit se la riga è occupata da una regina), due bitset per la diagonale (riga - colonna e riga + colonna) e una pila per la ricorsione.

Le informazioni in un cubo di orientamento di Rubik sono 24 facce mobili, ciascuna con un paio di bit di orientamento. Questo può essere ridotto un po 'con una matematica più complessa, poiché alcuni angoli sono disgiunti dai bordi e alcune configurazioni sono impossibili. In breve, un cubo di Rubik criptato rende una povera chiave di crittografia e una piccola quantità di dati se si desidera memorizzare molte configurazioni.

Quindi guardi l'interfaccia per il tuo algoritmo di risoluzione e inizi a fare scambi di tempo / spazio / complessità. Rappresentare tutte le facce esposte 3x3x6 come colori è spazio elevato, costo elevato di manipolazione. Nel caso estremo, è possibile memorizzare ciascuna configurazione come set minimo di spostamenti da un cubo intatto a quella configurazione.

Pensare a questo può essere divertente. Per un programma in esecuzione, scegli qualcosa che fa tutto ciò che vuoi, non è una scelta terribile e corri con esso.