Se sto tentando di simulare un Cubo di Rubik , come crei una struttura dati per archiviare il cubo? stato in memoria, con X numero di tessere per lato?
Cose da considerare:
Cosa c'è di sbagliato in un semplice vecchio array di dimensioni [6X][X] ? Non hai bisogno di sapere dei mini-cub interiori , perché non li vedi; non fanno parte dello stato del cubo. Nascondi due metodi brutti dietro un'interfaccia piacevole e semplice da usare, l'unità testala fino alla morte e voilà, hai finito!
Va notato che sono un avido cubo della velocità, ma non ho mai provato a rappresentare in modo programmatico un cubo di Rubik in un algoritmo o in una struttura dati.
Probabilmente creerei strutture dati separate per catturare gli aspetti unici di ciascun blocco in un cubo.
Ci sono 3 diversi tipi di blocchi su un cubo:
Corner Block - Ha tre facce di colore e tre pezzi adiacenti che condividerà un lato con in qualsiasi momento.
Edge Block: ha due facce di colore e ha 4 pezzi adiacenti che condividerà un lato con in qualsiasi momento. Nei blocchi 3x3 ha sempre 2 pezzi centrali e 2 pezzi angolari.
Center block - In un cubo 3x3 questo pezzo non è mobile, tuttavia può essere ruotato. Avrà sempre 4 blocchi di bordi adiacenti. Nei cubi più grandi ci sono più blocchi centrali che possono condividere con un altro blocco centrale o un pezzo di bordo. I blocchi centrali non sono mai adiacenti a un blocco d'angolo.
Sapendo questo, un Blocco può avere una lista di riferimenti ad altri blocchi che tocca. Manterrei un altro elenco di elenchi, che sarebbe un elenco di blocchi che rappresentano una singola faccia del cubo e un elenco che mantiene i riferimenti a ogni faccia del cubo.
Ogni faccia di cubo sarebbe rappresentata come una faccia unica.
Con queste strutture dati sarebbe piuttosto facile scrivere un algoritmo che esegua una trasformazione di rotazione su ogni faccia, spostando i blocchi appropriati dentro e fuori dagli elenchi appropriati.
EDIT: Nota importante, questi elenchi devono essere ordinati, naturalmente, ma ho dimenticato di dirlo. Ad esempio, se capovolgo il lato destro, l'angolo sinistro del blocco laterale destro si sposta nell'angolo destro del lato destro e viene ruotato in senso orario.
Quando penso a questo problema, penso a un cubo statico con i colori che si muovono su di esso in modelli noti. Quindi ....
Un oggetto Cube contiene 6 oggetti laterali che rimangono fissi indicizzati 0-5. Ogni lato contiene 9 oggetti di posizione che rimangono fissi indicizzati 0-8. Ogni posizione contiene un colore.
Per semplicità, gestisci ogni azione con incrementi di un quarto di giro. Ci sono 3 assi di rotazione, ciascuno in 2 direzioni possibili per un totale di 6 azioni possibili sul cubo. Con queste informazioni, diventa un compito abbastanza semplice mappare le 6 azioni possibili sul cubo.
Quindi il colore verde nel lato 6, posizione 3, può spostarsi verso il lato 1 posizione 3, o il lato 2 posizione 7, tra gli altri, a seconda dell'azione intrapresa. Non l'ho ancora esplorato abbastanza per trovare traduzioni matematiche, ma probabilmente emergeranno dei pattern che puoi sfruttare nel codice.
Using the data structure, how can I know if a certain cube in a certain state is solvable? I have been struggling with this question myself and haven't quite found the answer yet.
Per fare ciò, non iniziare mai con uno stato cubo casuale. Invece, inizia con uno stato risolto ed esegui azioni n a livello di codice per portare il cubo in uno stato di partenza casuale. Dal momento che hai solo intrapreso azioni legali per arrivare allo stato attuale, il cubo deve essere risolvibile.
Ho trovato un sistema di coordinate x-y-z per essere un modo semplice per indirizzare il cubo di Rubik e le matrici di rotazione un modo semplice e generico per implementare le rotazioni.
Ho creato una classe Piece contenente un vettore posizione (x, y, z) . Un pezzo può essere ruotato applicando una matrice di rotazione alla sua posizione (una moltiplicazione di matrice-vettore). The Piece ne conserva anche le tracce in una tupla (cx, cy, cz) , dando i colori di fronte ad ogni asse. Una piccola quantità di logica garantisce che questi colori vengano aggiornati in modo appropriato durante una rotazione: una rotazione di 90 gradi nel piano X-Y significa che dovremmo scambiare i valori di cx e cy .
Poiché tutta la logica di rotazione è incapsulata nella classe Piece, il cubo può memorizzare una lista non ordinata di pezzi e le rotazioni possono essere eseguite in modo generico. Per eseguire una rotazione della faccia sinistra, seleziona tutti i pezzi con una coordinata x di -1 e applica la matrice di rotazione appropriata a ciascun pezzo. Per eseguire una rotazione dell'intero cubo, applica la stessa matrice di rotazione a ogni pezzo.
Questa implementazione è semplice e ha un paio di sottigliezze:
(-1, 1, 1) ), un bordo ha esattamente uno zero ( (1, 0, -1) ), e un pezzo centrale ha due zeri ( (-1, 0, 0) ). Svantaggi:
puoi usare un semplice array (ogni elemento ha una mappatura 1 a 1 per un quadrato su una faccia) e simulare ogni rotazione con una certa permutazione
puoi farcela con solo 3 permutazioni essenziali: ruotare una fetta con l'asse attraverso la faccia anteriore, ruotare il cubo attorno all'asse verticale e ruotare il cubo sull'asse orizzontale attraverso le facce sinistra e destra. tutte le altre mosse possono essere espresse con una concatenazione di questi tre.
il modo più diretto per sapere se un cubo è risolvibile è risolverlo (trovare una serie di permutazioni che risolvono il cubo), se si finisce con 2 bordi che hanno posto scambiato, un singolo bordo capovolto, un singolo angolo ruotato o 2 angoli scambiati hai un cubo non separabile
La prima condizione che sia risolvibile sarebbe che ogni pezzo fosse presente e che i colori su ogni pezzo possano essere usati per assemblare un cubo "sovled". Questa è una condizione relativamente banale la cui verità può essere determinata con una semplice lista di controllo. La combinazione di colori su un cubo "standard" è definita , ma anche se non stai trattando con il cubo standard ce ne sono solo 6! possibili combinazioni di facce risolte.
Una volta che tutti i pezzi e i colori sono corretti, si tratta di determinare se una data configurazione fisica è risolvibile. Non tutti sono. Il modo più ingenuo per verificare ciò è eseguire un algoritmo di risoluzione dei cubi e vedere se termina con un cubo risolto. Non so se esistono fantasiose tecniche combinatorie per determinare la risolubilità senza realmente cercare di risolvere il cubo.
Per quanto riguarda la struttura dei dati ... quasi non importa. La parte difficile è ottenere le trasformazioni giuste e poter rappresentare lo stato del cubo in un modo che consenta di lavorare con precisione sugli algoritmi disponibili in letteratura. Come l'albero di acero indicato ci sono tre tipi di pezzi. La letteratura sulla risoluzione dei cubi di rubik si riferisce sempre ai pezzi secondo il loro tipo. Le trasformazioni sono anche rappresentate in modi comuni (consulta la notazione Singmaster ). Inoltre, tutte le soluzioni che ho visto si riferiscono sempre ad un pezzo come punto di riferimento (di solito posizionando il pezzo centrale bianco sul fondo).
Dato che hai già ricevuto ottime risposte, lascia che aggiunga solo un dettaglio.
Indipendentemente dalla tua rappresentazione concreta, tieni presente che gli obiettivi sono uno strumento molto utile per "ingrandire" le varie parti di un cubo. Ad esempio, guarda la funzione cycleLeft in questo codice Haskell . È una funzione generica che ciclicamente permuta qualsiasi lista di lunghezza 4. Il codice per eseguire la mossa di L assomiglia a questo:
moveL :: Aut (RubiksCube a)
moveL =
cong cube $ cong leftCols cycleLeft
. cong leftSide rotateSideCW
Quindi cycleLeft opera nella vista data da leftCols . Allo stesso modo, rotateSideCW , che è una funzione generica che si accosta a una versione ruotata di esso, opera sulla vista fornita da leftSide . Le altre mosse possono essere implementate in modi simili.
L'obiettivo di quella libreria Haskell è creare belle immagini. Penso che sia riuscito:
Sembra che tu stia facendo due domande separate.
- How to represent a cube with X number of sides?
Se stai per simulare un cubo di Rubic del mondo reale, allora tutti i cubi di Rubik hanno 6 lati. Penso che ciò che intendi sia "X numero di tessere per dimensione per lato". Ogni lato del cubo originale di Rubic è 3x3. Altre dimensioni includono 4x4 (Professor's Cube), 5x5 e 6x6.
Rappresenterei i dati con 6 lati, usando la notazione di risoluzione dei cubi "standard":
Ogni lato è una matrice 2-D di X per X.
Mi piace l'idea di @maple_shaft di rappresentare pezzi diversi (mini-cubi) in modo diverso: i pezzi centrale, di bordo e d'angolo portano rispettivamente 1, 2 o 3 colori.
Rappresenterei le relazioni tra di loro come un grafico (bidirezionale), con i bordi che collegano i pezzi adiacenti. Ogni pezzo avrebbe una serie di slot per i bordi (collegamenti): 4 slot in pezzi centrali, 4 slot in pezzi di bordo, 3 slot in pezzi angolari. In alternativa, i pezzi centrali possono avere 4 connessioni per i pezzi del bordo e 4 per i pezzi angolari separatamente, e / o i pezzi del bordo possono avere 2 collegamenti per i pezzi centrali e 2 per i pezzi angolari separatamente.
Questi array sono ordinati in modo che l'iterazione sui bordi del grafico rappresenti sempre la 'stessa' rotazione, modulo la rotazione del cubo. Cioè, ad es. per un pezzo centrale, se si ruota il cubo in modo che la sua faccia sia in cima, l'ordine delle connessioni è sempre in senso orario. Allo stesso modo per i bordi e gli angoli. Questa proprietà tiene dopo le rotazioni faccia (o così mi sembra ora).
Rilevamento di condizioni chiaramente irrisolvibili (bordi invertiti / invertiti, angolo di swap), se possibile, anche perché è facile trovare pezzi di tipo particolare e il loro orientamento.
Che ne dici di nodi e puntatori?
Supponendo che ci siano sempre 6 facce e che 1 nodo rappresenti 1 quadrato su 1 faccia:
r , g , b
r , g , b
r , g , b
| | |
r , g , b - r , g , b
r , g , b - r , g , b
r , g , b - r , g , b
Un nodo ha un puntatore a ciascun nodo vicino ad esso. Una rotazione circolare migra solo il puntatore (Numero di nodi / Numero di facce) -1 nodi sopra, in questo caso 2. Poiché tutte le rotazioni sono rotazioni di cerchio, si crea solo una funzione rotate . È ricorsivo, sposta ogni nodo di uno spazio e controlla se li ha spostati abbastanza, dal momento che avrà raccolto il numero di nodi e ci sono sempre quattro facce. In caso contrario, incrementa il numero di volte che il valore è stato spostato e chiama di nuovo a rotazione.
Non dimenticare che è doppiamente collegato, quindi aggiorna anche i nodi appena puntati. Ci sarà sempre Altezza * Larghezza numero di nodi spostati, con un puntatore aggiornato per nodo, quindi ci dovrebbe essere Altezza * Larghezza * 2 numero di puntatori aggiornati.
Poiché tutti i nodi puntano l'uno sull'altro, basta camminare sul cerchio aggiornando ogni nodo mentre ci si avvicina.
Questo dovrebbe funzionare per qualsiasi cubo di dimensioni, senza casi limite o logica complessa. È solo un puntatore a piedi / aggiornamento.
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 fare una mossa, rimuovi i sottomessi effettivi dai set coinvolti nella mossa e poi rimettili nei set che li prendono come risultato della mossa.
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.
A differenza delle altre 11 risposte, questa struttura dati utilizza l'intersezione di insiemi per definire la posizione di ogni sub-blocco nel cubo. Questo salva il lavoro di dover aggiornare i sub blocchi vicini quando viene apportata una modifica.
Leggi altre domande sui tag data-structures