-
Rubiks cube solver
I've began writing a Rubiks cube solver in Java. Normally when you perform a move on a Rubiks, you turn the appropriate face 90 degrees clockwise, this has the effect of changing the position of the colours on four of the adjacent cuboid faces.
When I began thinking about how I would write this in software, it became apparent that I had to create a collection of matrices to represent each tile on each face of the full Rubiks cuboid, and I would need a scheme to map the matrix on the cuboid face being rotated to the four other adjacent faces, whose values would need to be updated.
I began writing a truth table which mapped the adjacent faces and it came out like so:
(F = Front, T = Top, L = Left, B = Bottom, A = Away, R = Right)
F T L B A R
F 0 1 1 1 0 1
T 1 0 1 0 1 1
L 1 1 0 1 1 0
B 1 0 1 0 1 1
A 0 1 1 1 0 1
R 1 1 0 1 1 0
It immediately becomes apparent that there's some repitition within the table and I can reduce it as so:
F T L B A R
F/A 0 1 1 1 0 1
T/B 1 0 1 0 1 1
L/R 1 1 0 1 1 0
But again if you look at the first/last 3 values of each row there is some repititon still. So my question is, is there a simple algorithm for calculating the adjacent faces of a cube without any sort of lookup table?
Can the truth table above be reduced further through another approach to working out the adjacent faces, and have I overcomplicated the matter?
Thanks,
James
-
Re: Rubiks cube solver
I am not even sure I understand your logic at all. For each spot on your matrix I would expect there to be ANOTHER matrix representing the colors, not a 1 or a 0. Since each face of the cube contains 9 colors (3x3), how are you representing them?
-
Re: Rubiks cube solver
The truth table above doesn't represent the colour values, it represents a face of the cube and its four adjacent faces.
The colour matrices are outside the scope of the adjacents problem but I was just explaining my logic at how I arrived at the issue.
-
Re: Rubiks cube solver
This is not an OO approach to solving the problem. An example of an OO approach would be:
You have a Face class which knows which other Faces are it's neighbours and when you rotate a row or column of Cells on a Face, it forwards the Cells which are moving onto the neighbouring Face they are moving to. That Face replaces it's Cells with the ones it has received and forwards it's original Cells onto it's neighbour etc etc until you get back to the original face.
You have now moved a row or column in either direction and each Face object still knows which Cells it has.
-
Re: Rubiks cube solver
Interesting but not very efficient since each cell has one very simple property -- its colour. Two methods associated with it, setColour() and getColour(), I think a matrix object with multiple values and a pointer is equally as good and more efficient.
The adjacents promblem turns out to be a very simple solution, associating the face facing you with the face opposite you: L->R, F->A, T->B. For more complex 3d polygons I have been told that it is possible to deduce the adjacents through the dot product of normal vectors, but I'm still looking for more material on this.
-
Re: Rubiks cube solver
You could also represent the faces with a single array and make associations mathematically. So the face the user "sees" could be represented with the top left face being 0 the one to the right would be 1, & 2 for the top row. Then 3, 4, 5 for the next row. The next face to the right could be 9 - 17. Knowing the set order you could then extrapolate the adjacent faces functionally. A friend of mine did a similar thing with a chess board. He used a single array to represent the board and piece validation was checked mathematically. It was neat.
At any rate you seem hellbent on using matrix math (which is probably the best way if you're going to be performing move analysis on the state of the cube rather than making a game.)
Good times. =D