Comment représenterais-tu un Rubik's Cube en code ?

Question

Si vous développiez un logiciel pour résoudre un Rubik's Cube, comment représenteriez-vous le cube ?

Answer 1

Ce site Document de l'ACM décrit plusieurs façons alternatives qu'il a utilisées pour représenter un rubik's cube et les compare les unes aux autres. Malheureusement, je n'ai pas de compte pour obtenir le texte complet mais la description indique :

Sept représentations alternatives du Rubik's Cube sont présentées et comparées : un tableau de 3 par 3 par 3 d'entiers à 3 chiffres ; un tableau de littéraux de 6 par 3 par 3 ; une matrice de littéraux de 5 par 12 ; une matrice de littéraux épars de ll par ll ; un vecteur de 54 éléments ; un tableau à 4 dimensions ; et un tableau imbriqué de 3 par 3 par 3. Des fonctions APL sont fournies pour les déplacements d'orientation et les quarts de tour, ainsi que plusieurs outils utiles pour résoudre le cube.

Aussi, cette RubiksCube.java contient une représentation assez propre ainsi que le code pertinent pour la rotation des sections (si vous cherchez du code réel). Il utilise un tableau de cellules et de faces.

Answer 2

L'un des moyens serait de se concentrer sur l'aspect visuel.

Un cube a six faces et chaque face est une matrice de carrés de trois par trois. Donc

Color[][][] rubik = new Color[6][3][3];

Ensuite, chaque mouvement est une méthode qui permute un ensemble spécifique de carrés colorés.

Answer 3

Oubliez l'optimisation ; orientez le tout vers l'objet. Un pseudo-code de classe que j'ai utilisé est le suivant :

class Square
    + name : string
    + accronym : string

class Row
    + left_square : square
    + center_square : square
    + right_square : square

class Face
    + top_row : list of 3 square
    + center_row : list of 3 square
    + bottom_row : list of 3 square

    + rotate(counter_clockwise : boolean) : nothing

class Cube
    + back_face : face
    + left_face : face
    + top_face : face
    + right_face : face
    + front_face : face
    + bottom_face : face

    - rotate_face(cube_face : face, counter_clockwise : boolean) : nothing

La quantité de mémoire utilisée est si faible et le traitement si minime que l'optimisation est totalement inutile, surtout si l'on sacrifie la convivialité du code.

Answer 4

Une méthode intéressante pour représenter le cube est utilisée par le logiciel "Cube Explorer". En utilisant beaucoup de mathématiques astucieuses, cette méthode permet de représenter le cube en utilisant seulement 5 entiers. L'auteur explique les mathématiques derrière son programme sur son site Web. site web . Selon l'auteur, cette représentation est adaptée à la mise en œuvre de solveurs rapides.

Answer 5

Il existe plusieurs façons de procéder. Certaines utilisent la mémoire plus efficacement que d'autres.

J'ai vu des gens utiliser un tableau 3 x 3 x 3 d'objets cuboïdes, où l'objet cuboïde doit stocker des informations de couleur (et oui, l'objet central n'est jamais utilisé). J'ai vu des gens utiliser 6 tableaux, chacun d'entre eux étant un tableau 3 x 3 de cuboïdes. J'ai vu un tableau de cuboïdes de 3 x 18. Il existe de nombreuses possibilités.

Le problème le plus important est sans doute de savoir comment représenter les différentes transformations. La rotation d'une seule face d'un cube physique (tous les mouvements du cube sont essentiellement des rotations d'une seule face) devrait être représentée en échangeant beaucoup d'objets cuboïdes.

Votre choix doit être celui qui a du sens pour l'application que vous écrivez. Il se peut que vous ne fassiez que le rendu du cube. Il se peut qu'il n'y ait pas d'interface utilisateur. Il se peut que vous résolviez le cube.

Je choisirais le tableau 3 x 18.