CubeSolver - Data Model
Creating a data model suited to your problem is not always simple.
Ideally, a model is:
- Understandable
- Performant
- Simple to use
It's therefore important to think carefully in advance about how data is structured, as certain problems can be avoided.
Example:
The simplest way to represent a cube is to use six matrices of nine colors. The problem with such a simple model is that complex (and sometimes unreadable) services need to be developed to access relevant information. For example, to know which piece is at a given location, you need to retrieve a series of colors and compare them to a list of pieces.
The Cube Model
The cube model was developed with the idea that it could be adapted to represent other cube sizes.
This goal comes with certain difficulties:
- Considering even-sized cubes makes it impossible to refer to a face by its color (centers are not fixed).
- Some pieces can have the same colors (for example, two adjacent edges of a 4x4x4 cube).
- Some cubes lack certain types of pieces (a 2x2x2 cube has no centers / edges).
- It must be possible to simply create an algorithm to rotate a face.
After consideration, my cube model consists of the following elements:
- A variable storing the cube size.
- A HashMap associating a "Position" object with a "Piece" object.
- A HashMap associating a position with all adjacent positions.
- References to objects that need to be accessed quickly.
Storing the cube size will allow the model to adapt to represent other cube sizes (not yet utilized).
The first HashMap has values that could be stated as:
"A red and yellow piece is at the location of a green and white piece". "A blue piece is at the location of a blue piece".
Thus, to know if a piece is solved, we can simply ask if the colors of a position match the colors of the piece found there:
"Is a red and yellow piece at this red and yellow piece position?"
The second HashMap allows, from a position, to access all adjacent positions. This information seemed interesting for certain use cases, but is not yet utilized.
The references allow quick access to certain objects, for performance purposes. Indeed, HashMaps have the drawback of being quite slow; having simplified access to certain recurring information can save a lot of time.
The Movement Model
To use our cube, we need to define the different movements we can perform. Two pieces of information are essential for each movement:
- Which face the movement is applied to.
- The direction of rotation: "clockwise", "counter-clockwise", or "double".
Initially, we can simply address the face the movement is applied to by its color.
Example: "Green counter-clockwise", "Blue clockwise", etc.
But this approach has its limits. When a human learns a movement sequence, they learn it in a "relative" way. What they will remember will look like "Right clockwise, top double, right counter-clockwise". And not "Red clockwise, white double, red counter-clockwise".
Thus, once a human learns a movement sequence, they can apply it regardless of the cube's position. Having a similar mechanism within the project provides flexibility, since it's possible to perform operations like "Perform this movement sequence when blue is on top and orange is on the right".
It's therefore possible to write a movement in two forms:
It is possible to convert a sequence of relative movements into a sequence of absolute movements with a given orientation using this service.