Rubiks cube solver
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6

Thread: Rubiks cube solver

  1. #1
    Join Date
    Jan 2011
    Posts
    3

    Question 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

  2. #2
    Join Date
    Feb 2008
    Posts
    966

    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?

  3. #3
    Join Date
    Jan 2011
    Posts
    3

    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.

  4. #4
    Join Date
    May 2006
    Location
    UK
    Posts
    4,474

    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.
    Posting code? Use code tags like this: [code]...Your code here...[/code]
    Click here for examples of Java Code

  5. #5
    Join Date
    Jan 2011
    Posts
    3

    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.
    Last edited by j.a.mcguire; January 29th, 2011 at 07:30 AM.

  6. #6
    Join Date
    Jan 2011
    Location
    Tacoma, Washington
    Posts
    31

    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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center