So stellen Sie einen Rubik's Cube in einer Datenstruktur dar

58

Wenn ich versuche, einen Zauberwürfel zu simulieren , wie würden Sie eine Datenstruktur erstellen, um den Zustand des Würfels im Speicher mit einer X-Anzahl von Kacheln pro Seite zu speichern?

Dinge, die man beachten muss:

  • Der Würfel kann von beliebiger Größe sein
  • Es ist ein Zauberwürfel, sodass Ebenen gedreht werden können
Mel
quelle
2
Hausaufgaben? Oder Problem in der realen Welt ...
SDG
4
Der Quellcode dieses Rubik's Cube Solver könnte Sie interessieren .
Mouviciel
22
Ich bin mir ziemlich sicher, dass die Anzahl der Seiten eines Würfels 6 sein sollte
Simon Bergot,
3
Ich wäre neugierig, wenn ein Modell von Rubik's Cube abgeflacht wäre, damit ich alle Seiten gleichzeitig sehen könnte. Hmm, ich bin versucht, das jetzt zu schreiben. Es könnte die Form eines T haben oder, wenn möglich, endlos gekachelt sein (ich habe letzteres nicht durchdacht).
Lee Kowalkowski
6
Ich fühle mich versucht Eric Evans zu zitieren, (Zitat wahrscheinlich nicht 100% richtig , wie es aus dem Gedächtnis zitiert) „Model sind weder richtig, noch falsch Sie sind einfach mehr oder weniger nützlich.“
Pete

Antworten:

37

Was ist los mit einem einfachen alten Array von Größe [6X][X]? Sie müssen nichts über innere Mini-Würfel wissen , da Sie sie nicht sehen. Sie gehören nicht zum Status des Würfels. Verstecken Sie zwei hässliche Methoden hinter einer gut aussehenden und einfach zu bedienenden Oberfläche, testen Sie sie bis zum Tod, und fertig!

dasblinkenlight
quelle
31
sogar ein echter Zauberwürfel hat keine inneren Mini-Würfel
jk.
8
Dies wird funktionieren, aber Ihr Algorithmus wird wahrscheinlich außerordentlich komplex sein, um eine so einfache Datenstruktur aufzunehmen.
maple_shaft
6
As long as you know how the six surfaces are "threaded" together Welches ist genau das, was eine robustere Datenstruktur Ihnen geben wird. Ich denke, wir streiten uns für dasselbe. Eine Array-Seite und eine Seite ist ein Array von Blöcken. Es gibt jedoch viele interessante Eigenschaften von Seiten und Blöcken, die helfen, dieses "Threading" herauszufinden. Mag diesen Begriff nicht wirklich, weil er mit Multithreading verwechselt werden kann. )
maple_shaft
7
@maple_shaft "Genau das erhalten Sie durch eine robustere Datenstruktur." Ich weiß ja nicht , dass: eine Datenstruktur mit mehr „Struktur“ , um es unbedingt zu zusätzlicher brächte Neben Komplexität Einrichtung, Wartung im Zusammenhang, und der Zugriff auf einzelne Teilen dieser Struktur. Es ist schwer zu sagen, was komplexer wäre - das Implementieren hässlicher Verschiebungen auf einem einfachen Array mit einigen Eckfällen plus einer "freien Fahrt" beim Zugriff auf einzelne Zellen oder einer Struktur mit etwas weniger komplexen Verschiebungen und etwas komplexeren Lesevorgängen.
dasblinkenlight
16
Als jemand, der tatsächlich Programme zur Manipulation eines Zauberwürfels geschrieben hat, habe ich den einfachen Ansatz gewählt, sechs zweidimensionale Arrays zu verwenden, eines pro Gesicht. Es ist wahr, dass Sie einige grundlegende Operationen auf dem Würfel implementieren müssen, die ein wenig ärgerlich sind, aber danach können Sie die Darstellung vergessen. Für mich war das nie ein Problem. Ich habe mich oft gefragt, wie andere Darstellungen aus Performance-Sicht funktionieren würden, fühlte mich aber aus Coding-Sicht nie belastet.
PeterAllenWebb
39

Es sollte beachtet werden, dass ich ein begeisterter Geschwindigkeitsknacker bin, aber ich habe nie versucht, einen Zauberwürfel in einem Algorithmus oder einer Datenstruktur programmgesteuert darzustellen.

Ich würde wahrscheinlich separate Datenstrukturen erstellen, um die einzigartigen Aspekte jedes Blocks in einem Cube zu erfassen.

Es gibt drei verschiedene Arten von Blöcken auf einem Würfel:

  1. Eckblock - Er hat drei Farbflächen und drei benachbarte Teile, mit denen er jederzeit eine Seite teilt.

  2. Kantenblock - Er hat zwei Farbflächen und 4 benachbarte Teile, mit denen er jederzeit eine Seite teilt. In 3x3 Blöcken hat es immer 2 Mittelstücke und 2 Eckstücke.

  3. Zentralblock - In einem 3x3-Würfel ist dieses Teil nicht beweglich, kann jedoch gedreht werden. Es wird immer 4 benachbarte Kantenblöcke haben. In größeren Würfeln gibt es mehrere Mittelblöcke, die sich mit einem anderen Mittelblock oder einem Randstück teilen können. Mittelblöcke grenzen niemals an einen Eckblock.

Wenn Sie dies wissen, kann ein Block eine Liste von Verweisen auf andere Blöcke haben, die er berührt. Ich würde eine andere Liste von Listen führen, die eine Liste von Blöcken ist, die eine einzelne Würfelfläche darstellen, und eine Liste, die Verweise auf jede Würfelfläche enthält.

Jedes Würfelgesicht würde als ein einzigartiges Gesicht dargestellt.

Mit diesen Datenstrukturen wäre es ziemlich einfach, einen Algorithmus zu schreiben, der eine Rotationstransformation für jede Fläche ausführt und die entsprechenden Blöcke in die entsprechenden Listen und aus diesen heraus verschiebt.

EDIT: Wichtiger Hinweis, diese Listen müssen natürlich bestellt werden, aber ich habe vergessen, das zu erwähnen. Wenn ich zum Beispiel die rechte Seite drehe, bewegt sich der rechte Block der linken Ecke in die rechte Ecke der rechten Seite und wird im Uhrzeigersinn gedreht.

maple_shaft
quelle
Stimmen Sie zu, dass jeder Block eindeutige Eigenschaften haben muss. aber wäre nicht langweilig, da Sie die Verweise auf die angrenzenden Blöcke und Ihre aktualisieren müssen list of lists. Vielleicht ist es besser, nur eine ungeordnete Liste von Blöcken zu haben, die Sie abfragen können. und Sie aktualisieren nur die angrenzenden Blockreferenzen, wenn Sie eine Transformation durchführen. Wenn Sie eine Liste aller Blöcke in einer Fläche möchten, können Sie Ihre Liste nach allen benachbarten Blöcken für die mittleren Blöcke abfragen, oder?
Mel
@ Mel Es ist möglich, es so oder so zu machen, aber nachdem ich mit dasblinkenlight gesprochen habe, denke ich tatsächlich, dass sein Ansatz weniger komplex wäre. Ich wünschte, seine Antwort hätte mehr Stimmen als meine. Ich bin nicht so gut mit Algorithmen und der effizientesten, ich mag einfach Rubiks-Würfel und sammle sie (über 40 verschiedene Arten aus der ganzen Welt).
maple_shaft
Obwohl die Antwort von dasblinknenlight die einfachste Lösung ist, gebe ich Ihnen das Kopfgeld, weil ich die Tatsache mag, dass Ihre Antwort einige der Logik enthält, die für eine solche Datenstruktur erforderlich wäre, und die verschiedenen Blockattribute
Rachel
Dieses Datenmodell ist realistischer, macht jedoch einige der einfachen Vorgänge, die Sie durchführen möchten, schwieriger als sie sein sollten. Um den Status des Cubes zu ermitteln, müssen Sie rekursiv durch die Cubelisten navigieren, was umständlich ist.
Freitag,
@ Ziv Richtig, die Frage stellte sich jedoch nach der Datenstruktur und nicht unbedingt nach den Algorithmen.
maple_shaft
13

Wenn ich an dieses Problem denke, denke ich an einen statischen Würfel, über den sich die Farben in bekannten Mustern bewegen. Damit....

Ein Cube-Objekt enthält 6 Side-Objekte, die mit einem festen Index von 0-5 versehen bleiben. Jede Seite enthält 9 Positionsobjekte, die mit einem festen Index von 0-8 versehen bleiben. Jede Position enthält eine Farbe.

Der Einfachheit halber sollten Sie jede Aktion in Vierteldrehungsschritten ausführen. Es gibt 3 Rotationsachsen in jeweils 2 möglichen Richtungen für insgesamt 6 mögliche Aktionen auf dem Würfel. Mit diesen Informationen wird es zu einer relativ einfachen Aufgabe, die 6 möglichen Aktionen auf dem Würfel abzubilden.

Die Farbe Grün in Seite 6, Position 3, kann sich unter anderem in Abhängigkeit von der durchgeführten Aktion zu Seite 1, Position 3 oder Seite 2, Position 7 bewegen. Ich habe dies nicht genug untersucht, um mathematische Übersetzungen zu finden, aber es werden wahrscheinlich Muster auftauchen, die Sie im Code nutzen können.

Wie kann ich anhand der Datenstruktur feststellen, ob ein bestimmter Cube in einem bestimmten Zustand lösbar ist? Ich habe mich selbst mit dieser Frage beschäftigt und die Antwort noch nicht ganz gefunden.

Beginnen Sie dazu niemals mit einem zufälligen Würfelzustand. Beginnen Sie stattdessen mit einem gelösten Status und führen Sie n Aktionen programmgesteuert aus, um den Cube in einen zufälligen Startstatus zu versetzen. Da Sie nur rechtliche Schritte unternommen haben, um zum aktuellen Status zu gelangen, muss der Cube lösbar sein.

Matthew Vines
quelle
1
Klassische "Sie wollen nicht von hier aus starten" Beratung!
Ergwun
8

Ich fand, dass ein xyz-Koordinatensystem eine einfache Möglichkeit ist, einen Rubik-Würfel zu adressieren, und Rotationsmatrizen eine einfache, generische Möglichkeit, die Rotationen zu implementieren.

Ich habe eine Piece-Klasse erstellt, die einen Positionsvektor enthält (x, y, z). Ein Stück kann gedreht werden, indem eine Rotationsmatrix auf seine Position angewendet wird (eine Matrix-Vektor-Multiplikation). Das Teil zeichnet auch die Farben in einem Tupel auf (cx, cy, cz), wobei die Farben entlang jeder Achse ausgerichtet sind. Eine kleine Menge Logik stellt sicher, dass diese Farben während einer Drehung entsprechend aktualisiert werden: Eine 90-Grad-Drehung in der XY-Ebene bedeutet, dass die Werte von cxund vertauscht werden cy.

Da die gesamte Rotationslogik in der Piece-Klasse gekapselt ist, kann der Cube eine ungeordnete Liste von Pieces speichern, und Rotationen können auf generische Weise durchgeführt werden. Um die linke Fläche zu drehen, wählen Sie alle Teile mit einer x-Koordinate von -1 aus und wenden Sie die entsprechende Drehmatrix auf jedes Teil an. Um den gesamten Würfel zu drehen, wenden Sie auf jedes Teil dieselbe Rotationsmatrix an.

Diese Implementierung ist einfach und hat ein paar Feinheiten:

  1. Die Position eines Objektes ändert sich, die Farben jedoch nicht. Das bedeutet, Sie können nach dem rot-grünen Teil fragen, sich an dem Objekt festhalten, einige Rotationen ausführen und dasselbe Objekt überprüfen, um festzustellen, wo das rot-grüne Teil gelandet ist.
  2. Jeder Teiletyp (Kante, Mitte, Ecke) hat ein eindeutiges Koordinatenmuster. Bei einem 3x3-Würfel hat ein Eckstück keine Nullen in seinem Positionsvektor ( (-1, 1, 1)), eine Kante hat genau eine Null ( (1, 0, -1)) und ein Mittelstück hat zwei Nullen ( (-1, 0, 0)).
  3. Die Rotationsmatrizen, die für einen 3x3-Würfel funktionieren, funktionieren für einen NxN-Würfel.

Nachteile:

  1. Die Matrix-Vektor-Multiplikation ist langsamer als das Austauschen von Werten in Arrays.
  2. Linearzeit-Lookups für Teile nach Position. Sie müssten Teile in einer externen Datenstruktur speichern und diese bei Rotationen aktualisieren, um eine zeitlich konstante Suche nach Position zu ermöglichen. Dadurch wird ein Teil der Eleganz der Verwendung von Rotationsmatrizen zunichte gemacht und die Rotationslogik in Ihre Cube-Klasse verlagert. Wenn ich irgendeine Art von suchbasiertem Lösungsalgo implementieren würde, würde ich eine andere Implementierung verwenden.
  3. Die Musteranalyse (während des Lösens) ist nicht so schön wie sie sein könnte. Ein Teil hat keine Kenntnis über die angrenzenden Teile, und die Analyse wäre aufgrund der oben genannten Leistungsprobleme langsam.
user156217
quelle
3
Ich habe festgestellt, dass diese Art der Implementierung am besten funktioniert, um den Würfel in einem 3D-Grafikprogramm darzustellen. Die Matrixmultiplikation ermöglicht es, die Schichtrotationen zu animieren. In diesem Github-Repo finden Sie ein Beispiel für die Implementierung dieses Ansatzes. Um meinem 3D-Würfel einen Löser hinzuzufügen, benötige ich einen Algorithmus und eine Datenstruktur aus einer der anderen Antworten.
Jonathan Wilson
5

Sie können ein einfaches Array verwenden (jedes Element hat eine 1: 1-Zuordnung zu einem Quadrat auf einer Fläche) und jede Drehung mit einer bestimmten Permutation simulieren

Sie können mit nur 3 wesentlichen Permutationen davonkommen: Drehen Sie eine Scheibe mit der Achse durch die Vorderseite, drehen Sie den Würfel um die vertikale Achse und drehen Sie den Würfel über die horizontale Achse durch die linke und rechte Seite. Alle anderen Züge können durch eine Verkettung dieser drei ausgedrückt werden.

Die einfachste Methode, um festzustellen, ob ein Würfel lösbar ist, besteht darin, ihn zu lösen (finden Sie eine Reihe von Permutationen, die den Würfel lösen) 2 getauschte Ecken haben Sie einen unlösbaren Würfel

Ratschenfreak
quelle
1
the most straightforward way of know whether a cube is solvable is to solve it. Nun, wenn Sie das Modell verwenden, das Sie vorschlagen, denke ich, ist das wahr. Wenn Sie jedoch ein Modell verwenden, das näher an der Rotation von @ maple_shaft liegt, und die Rotation verfolgen, können Sie schnell testen, ob ein 3x3x3-Würfel lösbar ist, indem Sie überprüfen, ob die Summe der Kantenumkehrungen mod 2 0 und die Eckendrehung mod 3 0 beträgt. Überprüfen Sie dann die Parität der Permutation mit Zählt man Edge-Swaps und Corner-Swaps (um wieder gelöst zu werden), muss deren Summe Mod 2 0 sein (total parity even). Dies sind die notwendigen und ausreichenden Tests, um zu beweisen, dass der Würfel lösbar ist.
Jimhark
3

Die erste Bedingung, dass es lösbar ist, wäre, dass jedes Stück vorhanden ist und dass die Farben auf jedem Stück verwendet werden können, um einen "souveränen" Würfel zusammenzusetzen. Dies ist eine relativ triviale Bedingung, deren Wahrheit mit einer einfachen Checkliste ermittelt werden kann. Das Farbschema auf einem "Standard" -Würfel ist definiert , aber auch wenn Sie sich nicht mit Standardwürfeln beschäftigen, gibt es nur 6! mögliche Kombinationen von gelösten Gesichtern.

Wenn Sie alle Teile und Farben richtig eingestellt haben, ist es eine Frage, ob eine bestimmte physikalische Konfiguration lösbar ist. Nicht alle von ihnen sind. Die einfachste Möglichkeit, dies zu überprüfen, besteht darin, einen Algorithmus zum Lösen von Würfeln auszuführen und zu prüfen, ob er mit einem gelösten Würfel endet. Ich weiß nicht, ob es ausgefallene kombinatorische Techniken gibt, um die Lösbarkeit zu bestimmen, ohne tatsächlich zu versuchen, den Würfel zu lösen.

Was die Datenstruktur angeht, spielt das fast keine Rolle. Der knifflige Teil besteht darin, die Transformationen richtig zu machen und den Würfelzustand so darzustellen, dass Sie mit den verfügbaren Algorithmen in der Literatur ordentlich arbeiten können. Wie Maple-Shaft angibt, gibt es drei Arten von Stücken. Literatur über das Lösen von Rubiks Würfeln bezieht sich immer auf Stücke nach ihrer Art. Transformationen werden auch auf übliche Weise dargestellt (siehe Singmaster-Notation ). Außerdem beziehen sich alle Lösungen, die ich gesehen habe, immer auf ein Stück als Bezugspunkt (normalerweise wird das weiße Mittelstück auf den Boden gelegt).

Angelo
quelle
1
Für Punkt 2, anstatt mit einem zufälligen Würfel zu beginnen und zu prüfen, ob er lösbar ist. Ich würde mit einem gelösten Würfel beginnen und n zufällige Aktionen für den Würfel ausführen, um ihn in einen zufälligen Zustand zu versetzen.
Matthew Vines
Ja, absolut, das ist der einfachste Weg, eine Konfiguration zu generieren, die physikalisch lösbar ist. Mit einer beliebigen Konfiguration zu beginnen und zu bestimmen, ob sie lösbar ist, ist definitiv ein separates, aber damit verbundenes Problem.
Angelo
2
Sie vermuten, dass es "ausgefallene Techniken" geben könnte, um zu bestimmen, ob ein Würfel gelöst werden kann; in der Tat gibt es. Wenn Sie einen Würfel zerlegen, aber die Aufkleber behalten und dann den Würfel wieder zusammenbauen, erhalten Sie nicht unbedingt einen lösbaren Würfel. in der Tat, steht die Chancen 11.59 gegen , dass Sie einen lösbaren Würfel haben. Sie können durch eine Paritätsanalyse der Kanten und Ecken feststellen, ob Sie sich in einem lösbaren Zustand befinden . Sie müssen nicht wirklich versuchen, den Würfel zu lösen.
Eric Lippert
1
Hier ist eine kurze Übersicht über die drei Arten von Eigenschaften der Würfelpaarung, die beibehalten werden müssen, damit der Würfel lösbar ist. ryanheise.com/cube/cube_laws.html .
Eric Lippert
1
Ich habe diese Frage auf der Seite zum Austausch von Stapeln gepostet und wirklich nette Antworten erhalten: math.stackexchange.com/questions/127577/…
Mel
3

Da Sie bereits gute Antworten erhalten haben, möchte ich nur ein Detail hinzufügen.

Unabhängig von Ihrer konkreten Darstellung ist zu beachten, dass Linsen ein sehr gutes Werkzeug zum "Einzoomen" der verschiedenen Teile eines Würfels sind. Schauen Sie sich zum Beispiel die Funktion cycleLeftin diesem Haskell-Code an . Es ist eine generische Funktion, die zyklisch jede Liste der Länge 4 durchläuft. Der Code zum Ausführen der L-Bewegung sieht folgendermaßen aus:

moveL :: Aut (RubiksCube a)
moveL =
    cong cube $ cong leftCols cycleLeft
              . cong leftSide rotateSideCW

So cycleLeftarbeitet auf der Ansicht , gegeben durch leftCols . In ähnlicher Weise rotateSideCWfunktioniert die generische Funktion, die eine Seite zu einer gedrehten Version davon darstellt, mit der Ansicht von leftSide. Die anderen Schritte können auf ähnliche Weise implementiert werden.

Das Ziel dieser Haskell-Bibliothek ist es, hübsche Bilder zu erstellen. Ich denke es ist gelungen: Die diagrams-rubiks-cube Bibliothek in Aktion

Ingo Blechschmidt
quelle
2

Sie scheinen zwei getrennte Fragen zu stellen.

  1. Wie kann man einen Würfel mit X Seitenzahlen darstellen?

Wenn Sie einen Rubik-Würfel aus der realen Welt simulieren möchten, haben alle Rubik-Würfel 6 Seiten. Ich denke, was Sie meinen, ist "X Anzahl der Fliesen pro Dimension pro Seite". Jede Seite des ursprünglichen Rubic-Würfels ist 3x3. Andere Größen sind 4x4 (Professor's Cube), 5x5 und 6x6.

Ich würde die Daten mit 6 Seiten darstellen, unter Verwendung der "Standard" -Würfel-Lösungsnotation:

  • VORNE: das Gesicht, das dem Löser zugewandt ist
  • ZURÜCK
  • RICHTIG
  • LINKS
  • NACH OBEN
  • NIEDER

Jede Seite ist ein 2-D-Array von X mal X.

B Sieben
quelle
Sie können einen 17x17 Würfel kaufen ! Es hat einige mechanische Kompromisse, aber es ist zur realen Sache isomorph.
RBerteig
1

Ich mag die Idee von @maple_shaft, verschiedene Teile (Mini-Würfel) unterschiedlich darzustellen: Mittel-, Rand- und Eckteile haben jeweils 1, 2 oder 3 Farben.

Ich würde die Beziehungen zwischen ihnen als (bidirektionales) Diagramm darstellen, wobei Kanten benachbarte Teile verbinden. Jedes Stück hätte eine Reihe von Schlitzen für Kanten (Verbindungen): 4 Schlitze in zentralen Stücken, 4 Schlitze in Kantenstücken, 3 Schlitze in Eckstücken. Alternativ können Mittelstücke 4 Verbindungen zu Randstücken und 4 für Eckstücke separat aufweisen, und / oder Randstücke können 2 Verbindungen zu Mittelstücken und 2 zu Eckstücken separat aufweisen.

Diese Arrays sind so angeordnet, dass die Iteration über die Graphenkanten immer "dieselbe" Rotation darstellt, die die Rotation des Würfels moduliert. Das heißt, wenn Sie z. B. für ein Mittelstück den Würfel so drehen, dass seine Fläche oben liegt, ist die Reihenfolge der Verbindungen immer im Uhrzeigersinn. Ähnlich für Kanten- und Eckstücke. Diese Eigenschaft gilt nach Gesichtsrotationen (oder so scheint es mir jetzt).

  • Zu einer Kante gehörende Teile zu finden, ist trivial.
  • Zu einem Gesicht gehörende Teile zu finden ist trivial.
  • Das Finden von Gesichtern, die sich in einer bestimmten Richtung zu einem bestimmten Gesicht oder zu einem gegenüberliegenden Gesicht befinden, durchläuft 2 oder 3 genau definierte Verknüpfungen.
  • Um ein Gesicht zu drehen, aktualisieren Sie die Verbindungen aller Teile, die mit dem zentralen Teil des Gesichts verbunden sind.

Die Erkennung eindeutig unlösbarer Zustände (vertauschte / umgedrehte Kanten, vertauschte Ecke) ist hoffentlich auch einfach, da es einfach ist, Teile eines bestimmten Typs und ihrer Ausrichtung zu finden.

9000
quelle
1

Wie wäre es mit Knoten und Zeigern?

Angenommen, es gibt immer 6 Flächen und 1 Knoten repräsentiert 1 Quadrat auf 1 Fläche:

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

Ein Knoten hat einen Zeiger auf jeden Knoten daneben. Bei einer Kreisrotation wird der Zeiger (Anzahl der Knoten / Anzahl der Flächen) um -1 Knoten verschoben, in diesem Fall um 2. Da alle Rotationen Kreisrotationen sind, wird nur eine rotateFunktion erstellt. Es ist rekursiv, verschiebt jeden Knoten um ein Feld und prüft, ob er sie genug verschoben hat, da es die Anzahl der Knoten gesammelt hat und es immer vier Flächen gibt. Ist dies nicht der Fall, erhöhen Sie die Anzahl der Verschiebungen und rufen Sie "Rotation" erneut auf.

Vergessen Sie nicht, dass es doppelt verknüpft ist. Aktualisieren Sie daher auch die neu zugewiesenen Knoten. Es wird immer eine Höhe * Breite-Anzahl von Knoten verschoben, wobei ein Zeiger pro Knoten aktualisiert wird. Daher sollte eine Höhe * Breite * 2-Anzahl von Zeigern aktualisiert werden.

Da alle Knoten aufeinander zeigen, gehen Sie einfach im Kreis herum und aktualisieren Sie jeden Knoten, wenn Sie zu ihm kommen.

Dies sollte für Würfel jeder Größe ohne Kantenfälle oder komplexe Logik funktionieren. Es ist nur ein Zeigerlauf / Update.

Spencer Rathbun
quelle
-1

Aus persönlicher Erfahrung funktioniert es gut, ein Set zu verwenden, um jeden rotierenden Teil des Würfels im Auge zu behalten. Jeder Subwürfel besteht aus drei Sätzen, unabhängig von der Größe des Rubikwürfels. Um einen Unterwürfel zu finden, in dem sich der Zauberwürfel befindet, nehmen Sie einfach den Schnittpunkt der drei Mengen (das Ergebnis ist ein Unterwürfel). Um einen Zug auszuführen, entfernen Sie die betroffenen Sub-Cubs aus den Sätzen, die am Zug beteiligt sind, und legen Sie sie dann in die Sätze zurück, die sie als Ergebnis des Zuges aufnehmen.

Der 4 mal 4 Würfel wird 12 Sätze haben. 6 Sätze für die 6 Gesichter und 6 Sätze für die sechs Bänder, die um den Würfel herumlaufen. Die Gesichter haben jeweils 16 Unterwürfel und die Bänder haben jeweils 12 Unterwürfel. Es gibt insgesamt 56 Unterwürfel. Jeder Unterwürfel enthält Informationen über die Farbe und die Richtung der Farben. Der Rubik-Würfel selbst ist ein 4 × 4 × 4-Array, wobei jedes Element Informationen enthält, die aus den drei Mengen bestehen, die den Sub-Würfel an dieser Stelle definieren.

Im Gegensatz zu den anderen 11 Antworten haben Sie in dieser Datenstruktur den Schnittpunkt von Mengen verwendet, um die Position der einzelnen Unterblöcke im Cube zu definieren. Dies erspart die Arbeit, die Near-Sub-Blöcke aktualisieren zu müssen, wenn eine Änderung vorgenommen wird.

Martyn Strong
quelle
dies scheint nicht alles zu bieten erhebliche über Punkte gemacht und erläutert vor 11 Antworten
gnat