Author |
Topic: Rubik's Cube Conundrum (Read 3645 times) |
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
 |
Rubik's Cube Conundrum
« on: Mar 29th, 2003, 6:55pm » |
 Quote  Modify
|
Since the Rubik's Cube algorithm thread seems not to be moving any more, and inspired by Jeremy's Rubik' Cube post in the CS forum, I have decided to put out a new Cube question:
Call a cube position that can be reached from solved by a sequence of half-turn moves "diadic".
Call a cube position where each face has only two colors present: the color of the face itself, and the opposing color (from the opposite side of the cube), a "two-tone" position.
It is easy to see that every diadic position must be two-tone. The question is: Is every two-tone position diadic?
I do not know the answer to this one myself. I have investigated a few two-tone positions that I did not get to by diadic means, but was unable to demonstrate that they could not be solved diadic. One in particular is (R+L+F+A+)3 Which gives diagonals cutting through faces of the opposing color on the 4 sides.
R=right side, L=left side, F=front, A=aft, + means that when that face is directed towards you, the rotation is clockwise (or CCW, it doesn't matter so long as all four are turned the same way).
Alternate format: < represents turning the whole cube to the left, so that the right face becomes the new front face. Then the procedure is (R+L+<)6. This better represents what I actually do.
PS. Anyone got better suggestions for names other than "diadic" and "two-tone"?
|
| « Last Edit: Mar 30th, 2003, 11:20am 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
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Rubik's Cube Conundrum
« Reply #1 on: Apr 1st, 2003, 1:50pm » |
Quote Modify
|
I have come part-way in solving the Rubik's Cube Conundrum. I believe that not all "two-tone" orientations are "diadic". I have shown that diadic positions have certain correlations between the positions of the squares. What remains to be seen is whether or not the two-tone orientations have the same correlations. I suspect that they don't, but I cannot be sure of this.
However, if somebody does know, then I propose the following:
-If the independence factor of pieces in a "two-tone" configuration is greater than 0.00039, then not all "two-tone" orientations are "diadic".
UPDATE: this is wrong. 0.0833 is the critical correlation value for this test.
Note: Measure the independence factor in this way: take apart the Rubik's cube, and randomly reassemble it to a two-tone position. Try to solve the puzzle. Repeat a large number of times. The probability that the puzzle is solvable after being randomly assembled in this way is the independence factor. I think that the independence factor for two-tone positions is likely equal to or higher than the independence factor for all positions.
Here is how I show it:
1) We will only be considering the configuration of two sides of the cube at a time. However, this sums up 80% of the behaviour of the cube in diadic play. Choose one side, and label it with the numbers one to nine (rows first, then columns, starting in the top left corner). Now turn the cube around and label the opposite side with the letters a to i (same order).
2) We now observe that four "cliques" are formed, each containing four squares: {1,a,9,i}, {2,b,8,h}, {3,c,7,g}, and {4,d,6,f}. I will call these the "1 clique", "2 clique" etc. No diadic move can place a square from one set into a location originally occupied by a square from another set. The problem is not quite that easy, however, since all "two-tone" orientations must have exactly the same condition. I'll leave the reasoning behind this as an exercise for the reader.
3) There are six basic diadic moves. With the numbered side facing me, I will call these moves "top", "bottom", "left", "right", "front" and "back".
4) Inside each clique, we will examine the permutations of the squares that are available. For instance, if I use a "top" move, the squares in clique 1 change to this ordering: {a,1,9,i}. My first question is therefore: are all permutations possible? NOTE: There are 4! = 24 permutations possible for four objects.
5) To answer this question, I will construct some matrices. First, I construct the 4x4 identity matrix. This matrix will show the current permutation of the squares in the 1 clique. The rows are labelled "Square", and the columns are labelled "Position". A '1' in the matrix in the third row and second column will indicate that the "9" square is in the position originally occupied by the "a" square. I will examine all six moves, to see what effects they have on the permutation.
6) After examining all the six diadic moves, I see that they produce permutations (which I will represent as matrices) corresponding to all possible pair-wise swaps of the columns of the 4x4 identity matrix.
7) It is fairly easy to show that it is possible to reach any of the 24 permutations using the six diadic moves. Is it also possible to do this for the 2 clique, the 3 clique, and the 4 clique?
8 ) By symmetry, it is possible to do it with the 3 clique, but after examining the basic diadic moves for the 2 clique and the 4 clique, you will notice that two out of the six moves produce no changes. However, the other 4 moves can make up for the missing moves, so again all permutations are possible.
9) The next step is to consider whether all permutations of the 1 clique are independent of all the permutations of the 2 clique. In other words, if we fix one specific permutation for the 1 clique, how many permutations of the 2 clique could we have?
10) To answer this question, we examine the relative effects of the basic diadic moves. After a little work, we can see that for 4 of the 6 moves, the effects on the 1 clique are identical to the effects on the 3 clique. The only differences occur in the "left" and "right" moves, in which one clique will swap the middle two squares, and the other will swap the outside two squares. The only effect that this has is to make the 1 clique the end-to-end reversal of the 3 clique.
UPDATE: however, because matrix math is not commutative, this can mutate into other correlations. That is to say, it's more complicated than this...
11) Therefore, these two cliques are always correlated to a certain degree. That is to say, if the 1 clique is in this order: {i,1,9,a}, then the 3 clique must be in one of the two following orders: {h,2,8,b} or {b,8,2,h}. No other permutations are possible in diadic play.
12) Weaker correlations also exist between clique 1 and all the other cliques. The effect of this is to reduce the number of possibilities for diadic play (just considering two sides for now) from the naive 24^4 = 331776 to a mere 24*2*4*4 = 768 (I'm not 100% sure this number is accurate). This gives an independence factor of 0.0023.
13) Now when we consider the squares not accounted for by this method (squares not on either side we marked--there are only 4 of them) they also form a clique. This increases the correlation, because considering the fifth clique, there are only 24*2*4*4*4 = 3072 possibilities, out of a naive 24^5 (roughly 8 million). This is an independence factor of 0.00039.
14) Therefore, either the same proportion of two-tone positions are unavailable during regular play, or there are more two-tone positions available during regular play than are available during diadic play. The independence factor test I mention above should test this nicely (although it is a little difficult to carry out). I believe that regular play is less restrictive on two-tone positions than this, so my guess is that not all two-tone positions are diadic.
|
| « Last Edit: Apr 3rd, 2003, 2:00pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Rubik's Cube Conundrum
« Reply #2 on: Apr 3rd, 2003, 1:58pm » |
Quote Modify
|
UPDATE: TWO DAYs LATER <saner heads prevail>
Okay, what I said about the correlations was wrong. I didn't look at enough cases, and I fundamentally assumed that matrix multiplication is commutative (but of course it's not). So the correlations are a lot weaker than I said.
Having done a lot more thorough job searching for correlation, I have found that clique 1 is strongly correlated with clique 3. Given a particular permutation for clique 1, there are 4 possible permutations for clique 3. Given values for clique 1 and clique 3, cliques 2 and 4 can be whatever you like. However, given cliques 1 through 4, clique 5 has only 12 possibilities. Therefore, the critical correlation factor is not 0.00039, but is only 1/12 = 0.083.
That being said, I can now answer your question about the checkerboard-looking arrangement. All corner squares are in their normal positions, meaning cliques 1 and 3 are in the normal positions. Cliques 2 and 4 are in position 24, and clique 5 is in position 17 (this is in my own numbering system). It is actually possible to reach this position in diadic play, using, for instance, the following moves (I'm sure this is nowhere near optimal):
ltla ftfr flfb lflb flfb tlta ltla lflb ltla flfb frft tlta ltla ltla frf lta ftfr ftfr tlta tlta tftr ftfr tlta
It may be reachable in 18 moves, rather than 216 like I just gave, but I don't know which 18 moves! If you want to, explore this tree of moves:
((l or r) (t or b) (f or a) (l or r) (t or b) (f or a) (l or r) ... (f or a)) (18 moves total)
Never mind, I tried all possibilities of this form (brute force), and after 56 minutes (I was using Excel and VB macros, okay) it finished without finding anything. But I strongly doubt it's possible in fewer than 18 moves...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Rubik's Cube Conundrum
« Reply #3 on: Apr 3rd, 2003, 4:54pm » |
Quote Modify
|
Both of your posts look interesting. I am embarassed to admit I never noticed the relationships you are calling cliques. I have a few thoughts on them myself, but I haven't been able to find my cube for some time, and am having trouble visualizing things (Java Cube applets are a dime a dozen, but it's not the same). I just going to have to search harder for it.
on Apr 3rd, 2003, 1:58pm, James Fingas wrote:
That being said, I can now answer your question about the checkerboard-looking arrangement. All corner squares are in their normal positions, meaning cliques 1 and 3 are in the normal positions. Cliques 2 and 4 are in position 24, and clique 5 is in position 17 (this is in my own numbering system). It is actually possible to reach this position in diadic play:
ltla ftfr flfb lflb flfb tlta ltla lflb ltla flfb frft tlta ltla ltla frf lta ftfr ftfr tlta tlta tftr ftfr tlta |
|
Now you have me confused. The position I mentioned is not a checkerboard. The top and bottom are both single colored. The remaining 4 faces look like:
o . . | . . o | o . . | . . o
. o . | . o . | . o . | . o .
. . o | o . . | . . o | o . .
The checkerboards are all pretty easy to get diadically:
Checkerboard on 6 sides: rltbfa
Checkerboard on 4 sides: ralraltb
Checkerboard on 2 sides: ralraraf
One other question: what is clique 5? You didn't define it, and following the pattern by which you named the others clique 5 would involve the immobile center pieces.
|
|
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 Conundrum
« Reply #4 on: Apr 7th, 2003, 4:32pm » |
Quote Modify
|
I've figured out a fairly simple proof that some two-tone positions are not diadic.
A quarter-turn of a face results in an odd permutation of the corners and an odd permutation of the edges. So the overall permutation of the corners of the cube must always have the same parity as the permutation of the edges. But that parity can be even or odd.
A half-turn (diadic) move is the combination of two quarter-turns, so the permutation of the corners is even, and the permutation of the edges is even. Since any combination of even permutations is also even, every diadic position has an even permutation of corners, and an even permutation of edges.
Therefore, if there is a two-tone position whose corners (and edges) are oddly permuted, it cannot be diadic.
One such position is obtained by exchanging the TRF and TLA corners and exchanging the RF and LA edges.
|
|
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
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Rubik's Cube Conundrum
« Reply #5 on: Apr 14th, 2003, 2:02pm » |
Quote Modify
|
Icarus,
Sorry, I added clique 5 a little while later, and it consists of the four remaining mobile pieces (the ones not on the front or on the back). That is to say, the pieces between 1 and C, between 3 and A, between 9 and G, and between 7 and I, in that order.
I don't know how to solve the Rubik's cube, so I don't have a good sense of which positions are possible and which aren't...
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Rubik's Cube Conundrum
« Reply #6 on: Apr 14th, 2003, 7:29pm » |
Quote Modify
|
I'm not sure I would have been brave enough to take on this challenge without a strong sense of what the cube can do. You certainly sparked my thinking in the right direction. I'd been curious about this for some time but had never come up with the right idea before on how to solve it.
|
|
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