Comment représenter un cube de Rubik dans une structure de données

58

Si je tente de simuler un cube Rubik , comment créer une structure de données pour stocker l'état du cube en mémoire, avec un nombre X de mosaïques par face?

Choses à considérer:

  • le cube peut être de n'importe quelle taille
  • c'est un cube de Rubik, donc les couches peuvent être tournées
Mel
la source
2
Devoirs? Ou problème du monde réel ...
sdg
4
Vous pourriez être intéressé par le code source de ce solveur de cube de Rubik .
mouviciel
22
Je suis à peu près sûr que le nombre de côtés d'un cube devrait être égal à 6
Simon Bergot le
3
Je serais curieux de voir un modèle de Rubik's Cube aplati afin que je puisse voir tous les côtés en même temps. Hmm, je suis tenté d'écrire ça maintenant. Il pourrait s'agir de la forme d'un T ou même d'une mosaïque infinie si possible (je n'ai pas pensé à ce dernier).
Lee Kowalkowski
6
Je suis tenté de citer Eric Evans: "Les modèles ne sont ni bons, ni faux. Ils sont simplement plus ou moins utiles" (citation probablement pas exacte à 100% car elle est citée de mémoire)
Pete

Réponses:

37

Quel est le problème avec un vieux tableau de taille plaine [6X][X]? Vous n'avez pas besoin de connaître les mini-cubes intérieurs , car vous ne les voyez pas; ils ne font pas partie de l'état du cube. Cachez deux méthodes laides derrière une interface agréable et simple à utiliser, testez-la à mort, et le tour est joué, vous avez terminé!

dasblinkenlight
la source
31
même un vrai cube de Rubik n'a pas de mini-cubes intérieurs
jk.
8
Cela fonctionnera, mais votre algorithme sera probablement excessivement complexe pour prendre en charge une structure de données aussi simple.
maple_shaft
6
As long as you know how the six surfaces are "threaded" together Ce qui est exactement ce qu'une structure de données plus robuste vous donnera. Je pense que nous plaidons pour la même chose. Un tableau de côtés et un côté étant un tableau de blocs, cependant, il existe de nombreuses propriétés intéressantes sur les côtés et les blocs qui aident à comprendre que le "threading" n'aime pas vraiment ce terme car il peut être confondu avec le multi-threading; )
maple_shaft
7
@maple_shaft "Ce qui est exactement ce qu'une structure de données plus robuste vous donnera." Je ne sais pas à ce sujet: une structure de données avec plus « structure » à elle apporterait nécessairement plus accessoire complexité liée à la mise en place, le maintien et l' accès à différentes parties de cette structure. Il est difficile de dire ce qui serait plus complexe - implémenter de vilains décalages sur un tableau simple avec quelques angles de cas plus un "tour gratuit" pour accéder à des cellules individuelles, ou une structure avec des décalages un peu moins complexes et des lectures un peu plus complexes.
dasblinkenlight
16
En tant que personne ayant réellement écrit des programmes pour manipuler un cube de Rubik, j'ai adopté l'approche simple consistant à utiliser six tableaux à deux dimensions, un par visage. Il est vrai que vous devez implémenter certaines opérations fondamentales sur le cube qui sont un peu gênantes, mais vous pouvez ensuite oublier la représentation. Cela n'a jamais été un problème pour moi. Je me suis souvent demandé comment les autres représentations pourraient fonctionner du point de vue de la performance, mais je ne me suis jamais senti surchargé du point de vue du codage.
PeterAllenWebb
39

Il convient de noter que je suis un passionné de vitesse, mais je n’ai jamais essayé de représenter par programme un cube de Rubik dans un algorithme ou une structure de données.

Je créerais probablement des structures de données séparées pour capturer les aspects uniques de chaque bloc dans un cube.

Il existe 3 types distincts de blocs sur un cube:

  1. Bloc d'angle - Il comporte trois faces de couleur et trois pièces adjacentes avec lesquelles il partage une face à tout moment.

  2. Bloc de bord - Il a deux faces de couleur et 4 pièces adjacentes avec lesquelles il partagera un côté à tout moment. Dans les blocs 3x3, il y a toujours 2 pièces centrales et 2 pièces de coin.

  3. Bloc central - Dans un cube 3x3, cette pièce n'est pas mobile, mais elle peut être pivotée. Il aura toujours 4 blocs de bordure adjacents. Dans les plus gros cubes, plusieurs blocs centraux peuvent être partagés avec un autre bloc central ou une pièce de bord. Les blocs centraux ne sont jamais adjacents à un bloc d'angle.

Sachant cela, un bloc peut avoir une liste de références à d'autres blocs qu'il touche. Je conserverais une autre liste de listes, qui serait une liste de blocs représentant une seule face de cube et une liste contenant des références à chaque face de cube.

Chaque face de cube serait représentée comme une face unique.

Avec ces structures de données, il serait assez facile d'écrire un algorithme qui effectue une transformation de rotation sur chaque face, déplaçant les blocs appropriés dans les listes appropriées.

EDIT: Remarque importante, ces listes doivent être commandées bien sûr mais j'ai oublié de le mentionner. Par exemple, si je retourne le côté droit, le bloc du coin droit du coin gauche se déplace vers le coin droit du côté droit et est pivoté dans le sens des aiguilles d'une montre.

arbre_érable
la source
convenez que chaque bloc devrait avoir des propriétés uniques. mais la transformation ne serait-elle pas fastidieuse car vous devez mettre à jour les références aux blocs adjacents et à vos fichiers list of lists. peut-être vaut-il mieux avoir juste une liste non ordonnée de blocs que vous pouvez interroger. et vous venez de mettre à jour les références de bloc adjacentes lorsque vous effectuez une transformation. Si vous voulez une liste de tous les blocs d'un visage, vous pouvez interroger votre liste pour tous les blocs adjacents aux blocs centraux, n'est-ce pas?
Mel
@Mel Il est possible de le faire de toute façon, mais après avoir discuté avec dasblinkenlight, je pense en fait que son approche serait moins complexe. Je souhaite que sa réponse a eu plus de votes que le mien. Je ne suis pas très bon avec les algorithmes et celui qui est le plus efficace, j'aime vraiment beaucoup les cubes Rubiks et les collectionner (plus de 40 types différents provenant du monde entier).
maple_shaft
Bien que la solution de dasblinknenlight soit la solution la plus simple, je vous attribue cette prime, car j'apprécie le fait que votre réponse inclue une partie de la logique qui serait nécessaire pour une telle structure de données, ainsi que les différents attributs de bloc
Rachel
Ce modèle de données est plus fidèle à la réalité, mais il rend certaines des opérations simples que vous souhaitez effectuer plus difficilement qu’elles ne devraient l’être. Pour obtenir l’état du cube, il vous faudrait parcourir récursivement les listes de cubes, ce qui est fastidieux.
Ziv
@Ziv True, cependant, la question portait sur la structure de données et pas nécessairement sur les algorithmes.
arbre_érable
13

Quand je pense à ce problème, je pense à un cube statique dans lequel les couleurs se déplacent dans des motifs connus. Alors....

Un objet Cube contient 6 objets Side qui restent indexés de 0 à 5. Chaque côté contient 9 objets de position qui restent indexés de 0 à 8. Chaque position contient une couleur.

Pour plus de simplicité, gérez chaque action par incréments de quart de tour. Il y a 3 axes de rotation, chacun dans 2 directions possibles pour un total de 6 actions possibles sur le cube. Avec ces informations, il devient assez simple de cartographier les 6 actions possibles sur le cube.

Ainsi, la couleur verte du côté 6, position 3, peut se déplacer entre le côté 1, la position 3 ou le côté 2, la position 7, entre autres, en fonction de l'action entreprise. Je n'ai pas suffisamment exploré cela pour trouver des traductions mathématiques, mais des schémas apparaîtront probablement dont vous pourrez tirer parti dans le code.

À l'aide de la structure de données, comment savoir si un certain cube dans un certain état peut être résolu? J'ai moi-même eu du mal à répondre à cette question et je n'ai pas encore trouvé la réponse.

Pour ce faire, ne commencez jamais par un état de cube aléatoire. Au lieu de cela, commencez avec un état résolu et effectuez n actions par programme pour que le cube passe dans un état de départ aléatoire. Étant donné que vous avez uniquement engagé des actions en justice pour obtenir l'état actuel, le cube doit pouvoir être résolu.

Matthew Vines
la source
1
Conseil classique "vous ne voulez pas partir d'ici"!
Ergwun
8

J'ai trouvé qu'un système de coordonnées xyz était un moyen simple de traiter un cube de Rubik et que les matrices de rotation étaient un moyen simple et générique de mettre en œuvre les rotations.

J'ai créé une classe Piece contenant un vecteur de position (x, y, z). Vous pouvez faire pivoter une pièce en appliquant une matrice de rotation à sa position (multiplication matrice-vecteur). La pièce conserve également une trace des couleurs dans un tuple (cx, cy, cz), en donnant les couleurs qui se font face le long de chaque axe. Une petite quantité de logique garantit que ces couleurs sont mises à jour de manière appropriée au cours d'une rotation: une rotation de 90 degrés dans le plan XY signifie que nous échangerions les valeurs de cxet cy.

Comme toute la logique de rotation est encapsulée dans la classe Pièce, le Cube peut stocker une liste non ordonnée de pièces et les rotations peuvent être effectuées de manière générique. Pour effectuer une rotation de la face gauche, sélectionnez toutes les pièces avec une coordonnée x de -1 et appliquez la matrice de rotation appropriée à chaque pièce. Pour effectuer une rotation du cube entier, appliquez la même matrice de rotation à chaque pièce.

Cette implémentation est simple et a quelques subtilités:

  1. La position d'un objet Piece changera, mais pas ses couleurs. Cela signifie que vous pouvez demander la pièce rouge-verte, vous accrocher à l'objet, effectuer des rotations et vérifier le même objet pour voir où la pièce rouge-verte s'est terminée.
  2. Chaque type de pièce (bord, centre, angle) a un motif de coordonnées unique. Pour un cube 3x3, une pièce d'angle n'a pas de zéros dans son vecteur de position ( (-1, 1, 1)), une arête a exactement un zéro ( (1, 0, -1)) et une pièce centrale a deux zéros ( (-1, 0, 0)).
  3. Les matrices de rotation qui fonctionnent pour un cube 3x3 fonctionneront pour un cube NxN.

Inconvénients:

  1. La multiplication matrice-vecteur est plus lente que l’échange de valeurs dans les tableaux.
  2. Recherches temporelles linéaires pour les pièces par position. Vous devez stocker des pièces dans une structure de données externe et la mettre à jour lors des rotations pour des recherches à temps constant par position. Cela annule une partie de l'élégance d'utiliser des matrices de rotation et glisse la logique de rotation dans votre classe de cube. Si je mettais en œuvre un type d’algorithme de résolution basé sur la recherche, j’utiliserais une autre implémentation.
  3. L'analyse de modèle (pendant la résolution) n'est pas aussi belle qu'elle pourrait l'être. Une pièce n'a pas connaissance de ses pièces adjacentes et l'analyse serait lente en raison des problèmes de performances susmentionnés.
utilisateur156217
la source
3
J'ai constaté que ce type d'implémentation fonctionnait le mieux pour représenter le cube dans un programme graphique 3D. La multiplication de la matrice permet d’animer les rotations des calques. Voir ce dépôt github pour un exemple de mise en œuvre de cette approche. Je considère que pour ajouter un solveur à mon cube 3D, il me faut un algorithme et une structure de données provenant d'une des autres réponses.
Jonathan Wilson
5

vous pouvez utiliser un tableau simple (chaque élément ayant une correspondance 1 à 1 sur un carré d'une face) et simuler chaque rotation avec une certaine permutation

vous pouvez vous en tirer avec seulement 3 permutations essentielles: faites pivoter une tranche avec l’axe par la face avant, faites pivoter le cube autour de l’axe vertical et faites-le pivoter sur l’axe horizontal en passant par les faces gauche et droite. tous les autres mouvements peuvent être exprimés par une concaténation de ces trois.

Le moyen le plus simple de savoir si un cube est résoluble est de le résoudre (trouver une série de permutations qui résoudront le cube), si vous vous retrouvez avec 2 bords échangés, un seul bord retourné, un seul coin retourné ou 2 coins échangés vous avez un cube insoluble

monstre à cliquet
la source
1
the most straightforward way of know whether a cube is solvable is to solve it. En utilisant le modèle que vous suggérez, je suppose que c'est vrai. Mais si vous utilisez un modèle plus proche de @ maple_shaft et suivez les rotations, vous pouvez rapidement vérifier si un cube 3x3x3 peut être résolu en vérifiant que la somme des flips de bord mod 2 est 0 et que les rotations de coin mod 3 sont 0. Vérifiez ensuite la parité de la permutation par en comptant les swaps de bord et les swaps de coins (nécessaires pour revenir à la résolution), leur somme mod 2 doit être égale à 0 (même parité totale). Ce sont les tests nécessaires et suffisants pour prouver que le cube est soluble.
Jimhark
3

La première condition pour qu'il soit soluble est que chaque pièce soit présente et que les couleurs de chaque pièce puissent être utilisées pour assembler un cube "sovled". C'est une condition relativement triviale dont la vérité peut être déterminée avec une simple liste de contrôle. Le jeu de couleurs sur un cube "standard" est défini , mais même si vous ne traitez pas avec un cube standard, il n'y en a que 6! combinaisons possibles de faces résolues.

Une fois que tous les éléments et les couleurs sont corrects, il est alors essentiel de déterminer si une configuration physique donnée peut être résolue. Tous ne le sont pas. La manière la plus naïve de vérifier cela consiste à exécuter un algorithme de résolution de cube et à voir s'il se termine par un cube résolu. Je ne sais pas s'il existe des techniques combinatoires sophistiquées pour déterminer la solvabilité sans réellement essayer de résoudre le cube.

En ce qui concerne quelle structure de données ... cela n'a presque pas d'importance. La partie la plus délicate est d’obtenir les transformations correctes et de pouvoir représenter l’état du cube de manière à vous permettre de travailler parfaitement avec les algorithmes disponibles dans la littérature. Comme l’a indiqué Maple-shaft, il existe trois types de pièces. La littérature sur la résolution de cube de rubik fait toujours référence à des pièces par leur type. Les transformations sont également représentées de manière courante (recherchez la notation Singmaster ). En outre, toutes les solutions que j'ai vues se réfèrent toujours à une pièce comme point de référence (généralement, placer la pièce centrale blanche en bas).

Angelo
la source
1
Pour le point 2, au lieu de commencer avec un cube aléatoire et de vérifier s’il est résoluble. Je commencerais par un cube résolu et effectuerais n actions aléatoires sur le cube pour le mettre dans un état aléatoire.
Matthew Vines
Oui, c'est le moyen le plus simple de générer une configuration physiquement possible à résoudre. Commencer par une configuration arbitraire et déterminer si elle peut être résolue est un problème distinct mais lié.
Angelo
2
Vous supposez qu'il pourrait exister des "techniques sophistiquées" pour déterminer si un cube peut être résolu; en fait il y en a. Si vous désassemblez un cube mais conservez les autocollants puis réassemblez le cube, vous n'obtiendrez pas nécessairement un cube pouvant être résolu; En fait, les chances sont de un à douze contre le fait que vous avez un cube résoluble. Vous pouvez déterminer si vous êtes dans un état résoluble par une analyse de parité des arêtes et des angles. vous ne devez pas réellement essayer de résoudre le cube.
Eric Lippert
1
Voici un bref aperçu des trois types de propriétés de paires de cubes à préserver pour que le cube puisse être résolu. ryanheise.com/cube/cube_laws.html .
Eric Lippert
1
J'ai posté cette question sur le site du match stackexchange et obtenu de très bonnes réponses: math.stackexchange.com/questions/127577/…
Mel
3

Puisque vous avez déjà reçu d'excellentes réponses, permettez-moi d'ajouter un détail.

Indépendamment de votre représentation concrète, notez que les lentilles sont un très bon outil pour "zoomer" sur les différentes parties d’un cube. Par exemple, regardez la fonction cycleLeftdans ce code Haskell . C'est une fonction générique qui permute de façon cyclique toute liste de longueur 4. Le code permettant d'effectuer le déplacement L ressemble à ceci:

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

Ainsi cycleLeftopère sur la vue donnée par leftCols . De même, rotateSideCWqui est une fonction générique prenant un côté d’une version tournée de celle-ci, opère sur la vue donnée par leftSide. Les autres mouvements peuvent être mis en œuvre de manière similaire.

Le but de cette bibliothèque Haskell est de créer de jolies images. Je pense que ça a réussi: La bibliothèque diagrams-rubiks-cube en action

Ingo Blechschmidt
la source
2

Vous semblez poser deux questions distinctes.

  1. Comment représenter un cube avec un nombre X de côtés?

Si vous voulez simuler un cube de Rubic du monde réel, tous les cubes de Rubik ont ​​6 faces. Je pense que ce que vous voulez dire est "X nombre de carreaux par dimension et par côté". Chaque côté du cube de Rubic original est 3x3. D'autres tailles incluent 4x4 (cube du professeur), 5x5 et 6x6.

Je représenterais les données avec 6 côtés, en utilisant la notation de résolution de cube "standard":

  • AVANT: le visage face au solveur
  • RETOUR
  • DROITE
  • LA GAUCHE
  • UP
  • VERS LE BAS

Chaque côté est un tableau 2D de X par X.

B Seven
la source
Vous pouvez acheter un cube 17x17 ! Il comporte des compromis mécaniques, mais il est isomorphe à la réalité.
RBerteig
1

J'aime l'idée de @maple_shaft pour représenter différentes pièces (mini-cubes) différemment: les pièces centrales, les pièces de coin et les pièces de coin portent respectivement 1, 2 ou 3 couleurs.

Je représenterais les relations entre eux sous forme de graphique (bidirectionnel), avec des arêtes reliant des pièces adjacentes. Chaque pièce aurait un ensemble de fentes pour les bords (connexions): 4 fentes dans les pièces centrales, 4 fentes dans les pièces de bord, 3 fentes dans les pièces de coin. Alternativement, les pièces centrales peuvent avoir 4 connexions aux pièces de bord et 4 pour les pièces de coin séparément, et / ou les pièces de bord peuvent avoir 2 connexions aux pièces de centre et 2 aux pièces de coin séparément.

Ces tableaux sont ordonnés de manière à ce que l'itération sur les bords du graphique représente toujours la même rotation, modulo la rotation du cube. C'est-à-dire, par exemple, pour une pièce centrale, si vous faites pivoter le cube de manière à ce que sa face soit au-dessus, l'ordre des connexions est toujours dans le sens des aiguilles d'une montre. De même pour les pièces de coin et de coin. Cette propriété est valable après les rotations de visage (du moins me semble-t-il maintenant).

  • Trouver des pièces appartenant à une arête est trivial.
  • Trouver des pièces appartenant à un visage est trivial.
  • Trouver des faces qui se trouvent dans une direction donnée à une face donnée, ou une face opposée, consiste à traverser 2 ou 3 liens bien définis.
  • Pour faire pivoter une face, mettez à jour les connexions de toutes les pièces connectées à la pièce centrale de la face.

Détection de conditions clairement insolubles (bords intervertis / inversés, coin échangés), si tout va bien, aussi, car trouver des pièces d'un type particulier et leur orientation est simple.

9000
la source
1

Qu'en est-il des nœuds et des pointeurs?

En supposant qu'il y ait toujours 6 faces et que 1 nœud représente 1 carré sur 1 face:

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 nœud a un pointeur sur chaque nœud à côté de lui. Une rotation de cercle ne fait que migrer le pointeur (Nombre de nœuds / Nombre de faces) -1 nœuds sur, dans ce cas 2. Comme toutes les rotations sont des rotations de cercle, vous ne créez qu'une seule rotatefonction. Il est récursif, en déplaçant chaque nœud d'un espace et en vérifiant s'il les a suffisamment déplacés, car il aura collecté le nombre de nœuds et qu'il y a toujours quatre faces. Sinon, incrémentez le nombre de fois que la valeur a été déplacée et appelez à nouveau la rotation.

N'oubliez pas qu'il est doublement lié, alors mettez également à jour les nœuds nouvellement pointés. Il y aura toujours hauteur * largeur nombre de nœuds déplacés, avec un pointeur mis à jour par nœud, il devrait donc y avoir hauteur * largeur * 2 nombre de pointeurs mis à jour.

Étant donné que tous les nœuds se font face, il vous suffit de vous déplacer sur un cercle pour mettre à jour chaque nœud au fur et à mesure de votre progression.

Cela devrait fonctionner pour n'importe quel cube de taille, sans cas limite ni logique complexe. C'est juste une marche / mise à jour de pointeur.

Spencer Rathbun
la source
-1

Par expérience personnelle, utiliser un ensemble pour garder une trace de chaque partie rotationnelle du cube fonctionne bien. Chaque sous-cube est composé de trois ensembles, quelle que soit la taille du cube de rubik. Donc, pour trouver un sous-cube à un endroit quelconque du cube de rubik, il suffit de prendre l'intersection des trois ensembles (le résultat est un sous-cube). Pour effectuer un mouvement, retirez les sous-cubes affectés des ensembles impliqués dans le mouvement, puis remettez-les dans les ensembles qui les prennent en conséquence du mouvement.

Le cube 4 par 4 aura 12 ensembles. 6 jeux pour les 6 faces et 6 jeux pour les six bandes qui font le tour du cube. Les faces ont chacune 16 sous-cubes et les bandes ont chacune 12 sous-cubes. Il y a un total de 56 sous-cubes. Chaque sous-cube contient des informations sur la couleur et la direction des couleurs. Le cube rubik lui-même est un tableau de 4 sur 4 sur 4, chaque élément ayant des informations composées des 3 ensembles définissant le sous-cube à cet emplacement.

Contrairement aux 11 autres réponses, dans la structure de données, vous utilisez l'intersection d'ensembles pour définir l'emplacement de chaque sous-bloc dans le cube. Cela évite de devoir mettre à jour les sous-blocs proches lorsqu’une modification est apportée.

Martyn Strong
la source
cela ne semble rien offrir de substantiel sur les points soulevés et expliqués dans les 11 réponses précédentes
gnat