Author |
Topic: Rubik's Cube (Read 2302 times) |
|
Jeremy
Newbie
 
Gender: 
Posts: 25
|
 |
Rubik's Cube
« on: Mar 28th, 2003, 8:16pm » |
 Quote  Modify
|
SO... i'm currently enrolled in my first computer programming class, and i think it's great. i worked with turbo basic with my dad for a bit, but am now just using C.
Here's the thing though. i got a bit bored with the homework assignments, so i started messing around with some problems i made for myself, and some cs problems i found here... like making the palindrome tester, and making a pyramid of numbers... oops... i need to go back to that spiral of numbers problem... BUT ANYWAY...
i think i may have bit off more than i can chew. i decided to try to write a program that would solve a rubik's cube. right. So i found a way to store my data. and i found a way to have 2 basic cube movements (a face turning right, and left)... bla that took me so long though. i originally wanted 2 functions that would just be RIGHT(SIDE) and LEFT(SIDE) but i didn't know how i could get each face to go through the same manipulation using the same function.
anyway. i guess i'll figure this all out eventually, but i think i'm thinking too much like a human when approaching this problem. i have 6 arrays, each designated to a side, and when i manipulate a side the arrays shift some numbers between each other depending on the side being moved.
i guess i'm not too concerned about doing anything that will use the least amount of code, or get the fastest run time. i figure i'll get a working program first, and then worry about making it all efficient and crap.
so your thoughts and suggestions? is there a way that i can store data that will let me be able to better manipulate the cube, that isn't so much like real life?
and as far as solving it goes... i can solve a cube in real life, and i'm working backwards with this program. i've been able to write a series of steps that put the last 4 edge pieces in place, and an if statement that tells the program how to orient the cube before starting the moves.
yeesh, but i'm afraid when i get to later (earlier) steps i'll just have a whole slew of if statements that will just give every possible situation of the cube (or most of them).
and no fair giving insight if you've written a program like this, or giving a link to an existing program.
|
|
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Rubik's Cube
« Reply #1 on: Mar 29th, 2003, 12:04pm » |
Quote Modify
|
You are viewing the cube in terms of color combinations on each side. A better approach would be in terms of pieces. You have two sets of pieces you need to manipulate: corners and edges.
The easiest method of indexing pieces and positions is as a 3 digit trinary number:
Digit 1: 1= Blue side, 2= White side, 0= mid layer.
Digit 2: 1= Red side, 2= Orange side, 0= mid layer.
Digit 3: 1= Green side, 2= Yellow side, 0= mid layer.
This indexes both the position on the cube, and the piece that goes in that position when the cube is solved.
You will need two integer arrays (you could treat them as linear arrays of 27 values, or 3x3x3 arrays). On both the array index represents the cube position. The first array (P) tells which piece is currently in that position. The second array (O) tells the orientation of the the piece.
The disadvantage of this approach is that only 20 of the 27 indexes are of any use, so (horrors!) you will be wasting 14 array positions.
Some definitions:
A corner position/piece is one whose index has no digits = 0.
An edge position/piece is one whose index has exactly 1 digit = 0.
(The remaining positions are the ones not needed: the middles of each face, which do not change, and the center of the cube, which plays no part at all.)
A corner position is "even" if the sum of the digits is even, and "odd" if the sum is odd.
For corner positions the orientation array O contains a trinary digit: 0 = "home" orientation, 1 = CW rotated from home. 2 = CCW rotated from home. How to define the home orientation of a piece in an arbitrary position is complicated, but is only necessary if you are displaying the mixed up cube. When the piece is in its correct location, then the home orientation is obvious.
For edge positions, O contains a binary digit: 0 = home orientation, 1 = flipped.
To rotate a face, you find the indexes of the 4 corners and cyclicly permute the contents of the two arrays for those indexes. Then for each of the 4 indexes i, you change O by
O(i) +=1 if i is an even position and the face is turned CW (clockwise),
or i is an odd position, and the face is turned CCW. (2+1 = 0)
O(i) -=1 if i is an odd position and the face is turned CW,
or i is an even position and the face is turned CCW. (0-1 = 2)
Then you find the indexes of the 4 sides and cyclicly permute the contents of the two arrays for those indexes as well. Last you change the contents of O for those 4 indexes by:
O(i) = 1 - O(i) (i.e. 1 -> 0, 0 -> 1).
The cube is solved when P(i) = i and O(i) = 0 for all i. An arbitrary position is a valid cube position if the permutation of the edge pieces, and the permutation of the corner pieces are both even or both odd, The corner orientation values add up to 0 mod 3, and the edge orientation values add up to 0 mod 2.
To define the home orientation of an edge piece in an arbitrary position, ignore the difference in colors between opposing faces. That is, consider the cube to be 3-colored, with opposite faces of the same color. The edge piece will either be between two faces of the same colors as it has, in which case home is when the colors are matched, or the edge will between a face of one of its colors, and a face of the third color, in which case home is when the neither of the edge piece's colors match the face it is in. A little thought shows that rotating any face "flips" all four edges, no matter how they were oriented.
The definition of home orientation for corner positions is more complex, though still based on the 3-colored cube. And I am not yet energetic enough to work it out again. But, I believe that the outline I gave above for how to manipulate corner orientations is consistent with it.
|
| « Last Edit: Apr 10th, 2003, 5:38pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Rubik's Cube
« Reply #2 on: Apr 7th, 2003, 3:58pm » |
Quote Modify
|
I realized today that I made a mistake in how I said to handle rotation of the corner pieces. The way I had it, a corner would be rotated the same direction regardless of which of the two faces were turned to bring the corner from its old position to the new. But on the cube, turning the two faces gives different orientations. I have corrected the formulas in my post (I put it in bold, so you can find the changes).
While I am fairly confident of the new formulation, I have not demonstrated that it is consistent yet. The problem is coming up with good way of defining the "home orientation" for an even corner in an odd position, or an odd corner in an even position. None of the three possible orientations stands out as unique from the others. What is needed is a formulation so that whenever a face is turned, two diagonally opposing corners are also rotated CW, while the other two rotate CCW.
The other parts: permuting the pieces and orientation of the edges, are easily justified.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Rubik's Cube
« Reply #3 on: Apr 10th, 2003, 5:36pm » |
Quote Modify
|
Strike two. I thought I had come up with a consistant way to define home position for the corners sometime in the past, but apparently I missed something, because you can't do it except by arbitrary choices. I came up with this while trying to prove the three symmetry rules concerning cube position. The symmetry rules for permutation (permutation of corners and permutation of edges must both be odd or both be even) and edge orientation (the number of flipped edges must be even) are both fairly simple to prove. I had thought I had found a consistent way of demonstrating the corner condition as well, but clearly was mistaken. I have modified my original post again to strikethrough the errant parts. I'm planning on solving this whether or not Jeremy has any use for it or not, but it may take a bit.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print