Computer Science Canada :: View topic - To Program a Rubrik's Cube

*/

#import "Cube.h"

@implementation Cube(CubeSolving)

/*

This diagram shows how the Cube state is stored, with a bit of an
expanded view to show how some of the different faces are lined up.

+--+--+--+ +--+--+--+
|T0|T1|T2| |T8|T7|T6|
+--+--+--+ +--+--+--+
|T3|T4|T5| |T5|T4|T3|
+--+--+--+ +--+--+--+
|T6|T7|T8| |T2|T1|T0|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|L0|L1|L2|F0|F1|F2|R0|R1|R2|P0|P1|P2|L0|L1|L2|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|L3|L4|L5|F3|F4|F5|R3|R4|R5|P3|P4|P5|L3|L4|L5|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|L6|L7|L8|F6|F7|F8|R6|R7|R8|P6|P7|P8|L6|L7|L8|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|B0|B1|B2| |B8|B7|B6|
+--+--+--+ +--+--+--+
|B3|B4|B5| |B5|B4|B3|
+--+--+--+ +--+--+--+
|B6|B7|B8| |B2|B1|B0|
+--+--+--+ +--+--+--+

*/

#define EQ(a,b) (state.a == state.b)

#define IS_CORNER_ORIENTED(a,b,c,d,e,f) \
(EQ(a,d) && EQ(b,e) && EQ(c,f))

#define IS_CORNER_PLACED(a,b,c,d,e,f) \
((EQ(a,d) || EQ(a,e) || EQ(a,f)) && \
   (EQ(b,d) || EQ(b,e) || EQ(b,f)) && \
   (EQ(c,d) || EQ(c,e) || EQ(c,f)))

#define IS_EDGE_ORIENTED(a,b,c,d) \
(EQ(a,c) && EQ(b,d))

#define IS_EDGE_PLACED(a,b,c,d) \
((EQ(a,c) || EQ(a,d)) && \
   (EQ(b,c) || EQ(b,d)))

// Internal check macros for corners (BFL, BFR, BLP, BPR, FLT, FRT, LPT, PRT)
#define BFL_ORIENTED IS_CORNER_ORIENTED(B4,F4,L4,B0,F6,L8)
#define BFL_PLACED IS_CORNER_PLACED(B4,F4,L4,B0,F6,L8)
#define BFR_ORIENTED IS_CORNER_ORIENTED(B4,F4,R4,B2,F8,R6)
#define BFR_PLACED IS_CORNER_PLACED(B4,F4,R4,B2,F8,R6)
#define BLP_ORIENTED IS_CORNER_ORIENTED(B4,L4,P4,B6,L6,P8)
#define BLP_PLACED IS_CORNER_PLACED(B4,L4,P4,B6,L6,P8)
#define BPR_ORIENTED IS_CORNER_ORIENTED(B4,P4,R4,B8,P6,R8)
#define BPR_PLACED IS_CORNER_PLACED(B4,P4,R4,B8,P6,R8)

#define FLT_ORIENTED IS_CORNER_ORIENTED(F4,L4,T4,F0,L2,T6)
#define FLT_PLACED IS_CORNER_PLACED(F4,L4,T4,F0,L2,T6)
#define FRT_ORIENTED IS_CORNER_ORIENTED(F4,R4,T4,F2,R0,T8)
#define FRT_PLACED IS_CORNER_PLACED(F4,R4,T4,F2,R0,T8)
#define LPT_ORIENTED IS_CORNER_ORIENTED(L4,P4,T4,L0,P2,T0)
#define LPT_PLACED IS_CORNER_PLACED(L4,P4,T4,L0,P2,T0)
#define PRT_ORIENTED IS_CORNER_ORIENTED(P4,R4,T4,P0,R2,T2)
#define PRT_PLACED IS_CORNER_PLACED(P4,R4,T4,P0,R2,T2)

// Internal check macros for edges (BF, BL, BP, BR, FL, FR, FT, LP, LT, PR, PT and RT)
#define BF_ORIENTED IS_EDGE_ORIENTED(B4,F4,B1,F7)
#define BF_PLACED IS_EDGE_PLACED(B4,F4,B1,F7)
#define BL_ORIENTED IS_EDGE_ORIENTED(B4,L4,B3,L7)
#define BL_PLACED IS_EDGE_PLACED(B4,L4,B3,L7)
#define BP_ORIENTED IS_EDGE_ORIENTED(B4,P4,B7,P7)
#define BP_PLACED IS_EDGE_PLACED(B4,P4,B7,P7)
#define BR_ORIENTED IS_EDGE_ORIENTED(B4,R4,B5,R7)
#define BR_PLACED IS_EDGE_PLACED(B4,R4,B5,R7)

#define FL_ORIENTED IS_EDGE_ORIENTED(F4,L4,F3,L5)
#define FL_PLACED IS_EDGE_PLACED(F4,L4,F3,L5)
#define FR_ORIENTED IS_EDGE_ORIENTED(F4,R4,F5,R3)
#define FR_PLACED IS_EDGE_PLACED(F4,R4,F5,R3)
#define FT_ORIENTED IS_EDGE_ORIENTED(F4,T4,F1,T7)
#define FT_PLACED IS_EDGE_PLACED(F4,T4,F1,T7)

#define LP_ORIENTED IS_EDGE_ORIENTED(L4,P4,L3,P5)
#define LP_PLACED IS_EDGE_PLACED(L4,P4,L3,P5)
#define LT_ORIENTED IS_EDGE_ORIENTED(L4,T4,L1,T3)
#define LT_PLACED IS_EDGE_PLACED(L4,T4,L1,T3)

#define PR_ORIENTED IS_EDGE_ORIENTED(P4,R4,P3,R5)
#define PR_PLACED IS_EDGE_PLACED(P4,R4,P3,R5)
#define PT_ORIENTED IS_EDGE_ORIENTED(P4,T4,P1,T1)
#define PT_PLACED IS_EDGE_PLACED(P4,T4,P1,T1)
#define RT_ORIENTED IS_EDGE_ORIENTED(R4,T4,R1,T5)
#define RT_PLACED IS_EDGE_PLACED(R4,T4,R1,T5)

// External Placement/orientation checks for 8 corners (BFL, BFR, BLP, BPR, FLT, FRT, LPT, PRT)
- (BOOL)isSolved
{
return
BFL_ORIENTED
&& BFR_ORIENTED
&& BLP_ORIENTED
&& BPR_ORIENTED
&& FLT_ORIENTED
&& FRT_ORIENTED
&& LPT_ORIENTED
&& PRT_ORIENTED
&& BF_ORIENTED
&& BL_ORIENTED
&& BP_ORIENTED
&& BR_ORIENTED
&& FL_ORIENTED
&& FR_ORIENTED
&& FT_ORIENTED
&& LP_ORIENTED
&& LT_ORIENTED
&& PR_ORIENTED
&& PT_ORIENTED
&& RT_ORIENTED;
;
}

- (BOOL)isBFLOriented
{
return BFL_ORIENTED;
}

- (BOOL)isBFLPlaced
{
return BFL_PLACED;
}

- (BOOL)isBFROriented
{
return BFR_ORIENTED;
}

- (BOOL)isBFRPlaced
{
return BFR_PLACED;
}

- (BOOL)isBLPOriented
{
return BLP_ORIENTED;
}

- (BOOL)isBLPPlaced
{
return BLP_PLACED;
}

// The following five methods implement the core of the cube solver.
// The algorithm is basically the one described in the book "How to
// Solve the Rubik's Cube" by XXXX. I chose that particular solution
// simply because that was the book I had in fifth grade, and because
// it was fairly simple to learn. It was also fairly straightforward
// to write code to implement it.

// There are many other ways to handle solving the cube using more
// informed search methods, but they generally require a lot more
// work and a lot more memory. Of course, they also will produce
// far more optimal solutions than those found here.

// It would be relatively straightforward to add other solution methods
// based on all of the primitives provided here.
- (BOOL)solveTopEdges
{
while(!
(FT_ORIENTED && RT_ORIENTED && PT_ORIENTED && LT_ORIENTED))
{
// Find non-solved edge to work on.
while(FT_ORIENTED)
[self performSequence:@"Y+"];

// 11 possibilities (aside from being placed correctly)
if(IS_EDGE_PLACED(F4,T4,R1,T5))
[self performSequence:@"R- F-"];
else if(IS_EDGE_PLACED(F4,T4,T1,P1))
[self performSequence:@"T+ R- T- F-"];
else if(IS_EDGE_PLACED(F4,T4,L1,T3))
[self performSequence:@"L+ F+"];
else if(IS_EDGE_PLACED(F4,T4,F5,R3))
[self performSequence:@"F-"];
else if(IS_EDGE_PLACED(F4,T4,P3,R5))
[self performSequence:@"R2 F- R2"];
else if(IS_EDGE_PLACED(F4,T4,P5,L3))
[self performSequence:@"L2 F+ L2"];
else if(IS_EDGE_PLACED(F4,T4,L5,F3))
[self performSequence:@"F+"];
else if(IS_EDGE_PLACED(F4,T4,B1,F7))
[self performSequence:@"F2"];
else if(IS_EDGE_PLACED(F4,T4,B5,R7))
[self performSequence:@"B- F2"];
else if(IS_EDGE_PLACED(F4,T4,P7,B7))
[self performSequence:@"B2 F2"];
else if(IS_EDGE_PLACED(F4,T4,L7,B3))
[self performSequence:@"B+ F2"];

if(!FT_PLACED)
return NO;

if(!FT_ORIENTED)
[self performSequence:@"F- T+ L- T-"];
assert(FT_ORIENTED);
}
return YES;
}

- (BOOL)solveTopCorners
{
unsigned iterations;

while(!(FLT_ORIENTED && FRT_ORIENTED && LPT_ORIENTED && PRT_ORIENTED))
{
// Find non-solved corner to work on.
while(FRT_ORIENTED)
[self performSequence:@"Y+"];

if(!FRT_PLACED)
{
// See if the desired cube is on the top face somewhere (but
// in the wronge place), and if so, move it to the bottom
// before the next step
if(IS_CORNER_PLACED(F4,R4,T4,F0,L2,T6))
{
[self performSequence:@"Y-"];
[self performSequence:@"R- B- R+"];
[self performSequence:@"Y+"];
}
else if(IS_CORNER_PLACED(F4,R4,T4,R2,T2,P0))
{
[self performSequence:@"Y+"];
[self performSequence:@"R- B- R+"];
[self performSequence:@"Y-"];
}
else if(IS_CORNER_PLACED(F4,R4,T4,L0,T0,P2))
{
[self performSequence:@"Y+"];
[self performSequence:@"Y+"];
[self performSequence:@"R- B- R+"];
[self performSequence:@"Y-"];
[self performSequence:@"Y-"];
}

if(!FRT_PLACED)
{
// Now turn bottom until the desired is in BFR
iterations = 0;
while(!IS_CORNER_PLACED(F4,R4,T4,F8,R6,B2))
{
iterations++;
if(iterations > 3)
return NO;
[self performSequence:@"B+"];
}
// Note: I should fix this to do one of three bring-up
// sequences that will bring up the cube into the right
// orientation to begin with.

// Bring it up.
[self performSequence:@"R- B- R+"];
}
}
while(!FRT_ORIENTED)
[self performSequence:@"R- B2 R+ F+ B2 F-"];
}
return YES;
}

- (BOOL)solveVerticalEdges
{
while(!(LP_ORIENTED && FL_ORIENTED && FR_ORIENTED && PR_ORIENTED))
{
// Find edge to fix
while(FR_ORIENTED)
[self performSequence:@"Y+"];

if(FR_PLACED)
{
[self performSequence:@"R- B+ R+ B+ F+ B- F- B+ R- B+ R+ B+ F+ B- F-"];
assert(FR_ORIENTED);
continue;
}
else
{
// Bring down cube if necessary
if(IS_EDGE_PLACED(F4,R4,F3,L5))
{
[self performSequence:@"Y-"];
[self performSequence:@"R- B+ R+ B+ F+ B- F-"];
[self performSequence:@"Y+"];
}
else if(IS_EDGE_PLACED(F4,R4,R5,P3))
{
[self performSequence:@"Y+"];
[self performSequence:@"R- B+ R+ B+ F+ B- F-"];
[self performSequence:@"Y-"];
}
else if(IS_EDGE_PLACED(F4,R4,P5,L3))
{
[self performSequence:@"Y+"];
[self performSequence:@"Y+"];
[self performSequence:@"R- B+ R+ B+ F+ B- F-"];
[self performSequence:@"Y-"];
[self performSequence:@"Y-"];
}
}
// Rotate bottom until desired cube is in BR or BF
for(;;)
{
if(IS_EDGE_ORIENTED(F4,R4,F7,B1))
{
[self performSequence:@"B- R- B+ R+ B+ F+ B- F-"];
break;
}
else if(IS_EDGE_ORIENTED(F4,R4,B5,R7))
{
[self performSequence:@"B+ F+ B- F- B- R- B+ R+"];
break;
}
[self performSequence:@"B+"];
}
assert(FR_ORIENTED);
}
return YES;
}

- (BOOL)solveBottomCorners
{
if(!(BFL_ORIENTED && BFR_ORIENTED && BLP_ORIENTED && BPR_ORIENTED))
{
unsigned placed = 0;
unsigned iterations;

iterations = 0;

// Rotate bottom face until 4 or 2 cubes are properly positioned
for(;;)
{
if(BFL_PLACED && BFR_PLACED && BLP_PLACED && BPR_PLACED)
{
placed = 4;
break;
}
else if(BFL_PLACED && BFR_PLACED)
{
[self performSequence:@"Y+"];
[self performSequence:@"Y+"];
placed = 1;
break;
}
else if(BFL_PLACED && BLP_PLACED)
{
[self performSequence:@"Y+"];
placed = 1;
break;
}
else if(BFR_PLACED && BPR_PLACED)
{
[self performSequence:@"Y-"];
placed = 1;
break;
}
else if(BLP_PLACED && BPR_PLACED)
{
placed = 1;
break;
}
else if(BFL_PLACED && BPR_PLACED)
{
[self performSequence:@"Y-"];
placed = 2;
break;
}
else if(BFR_PLACED && BLP_PLACED)
{
placed = 2;
break;
}
iterations++;
if(iterations > 3)
return NO;
[self performSequence:@"B+"];
}
if(placed == 1)
[self performSequence:@"R- B- R+ F+ B+ F- R- B+ R+ B2"];
else if(placed == 2)
[self performSequence:@"R- B- R+ F+ B2 F- R- B+ R+ B+"];

assert(BFL_PLACED && BFR_PLACED && BLP_PLACED && BPR_PLACED);

while(!(BFL_ORIENTED && BFR_ORIENTED && BLP_ORIENTED && BPR_ORIENTED))
{
// Rotate entire cube until it pattern matches with one of the
// known 7 patterns, then perform the same sequence.
iterations = 0;
for(;;)
{
unsigned c = state.B4;

if(c == state.B0 && c == state.F8 &&
   c == state.R8 && c == state.P8)
{
break;
}
else if(c == state.B0 && c == state.R6 &&
c == state.P6 && c == state.L6)
{
break;
}
else if(c == state.L8 && c == state.R6 &&
c == state.P6 && c == state.P8)
{
break;
}
else if(c == state.F6 && c == state.B2 &&
c == state.B8 && c == state.P8)
{
break;
}
else if(c == state.F6 && c == state.F8 &&
c == state.B8 && c == state.B6)
{
break;
}
else if(c == state.F6 && c == state.B2 &&
c == state.R8 && c == state.B6)
{
break;
}
else if(c == state.L8 && c == state.R6 &&
c == state.L6 && c == state.R8)
{
break;
}
iterations++;
[self performSequence:@"Y+"];
if(iterations > 3)
break;
}
if(iterations > 3)
return NO;
[self performSequence:@"R- B- R+ B- R- B2 R+ B2"];
}
}
return YES;
}

- (BOOL)solveBottomEdges
{
unsigned positioned = 0;

if(BF_PLACED)
positioned++;
if(BL_PLACED)
positioned++;
if(BR_PLACED)
positioned++;
if(BP_PLACED)
positioned++;

if(positioned == 0)
{
[self performSequence:@"(L- R+) F+ (L+ R-) B2 (L- R+) F+ (L+ R-)"];
positioned = 1;
}

while(!(BF_ORIENTED && BL_ORIENTED && BR_ORIENTED && BP_ORIENTED))
{
while(!(BF_PLACED && BL_PLACED && BR_PLACED && BP_PLACED))
{
while(!BF_PLACED)
[self performSequence:@"Y+"];
[self performSequence:@"(L- R+) F+ (L+ R-) B2 (L- R+) F+ (L+ R-)"];
}
if(BF_ORIENTED && BL_ORIENTED && BR_ORIENTED && BP_ORIENTED)
break;

for(;;)
{
if(!BF_ORIENTED && !BL_ORIENTED && !BR_ORIENTED && !BP_ORIENTED)
{
[self performSequence:@"(L- R+) F2 (L+ R-) B2 (L- R+) F+"];
[self performSequence:@"(L+ R-) B2 (L- R+) F2 (L+ R-) B-"];
break;
}
else if(!BF_ORIENTED && BL_ORIENTED && BR_ORIENTED && !BP_ORIENTED)
{
[self performSequence:@"(L- R+) F+ (L+ R-) B+"];
[self performSequence:@"(L- R+) F+ (L+ R-) B+"];
[self performSequence:@"(L- R+) F2 (L+ R-) B+"];
[self performSequence:@"(L- R+) F+ (L+ R-) B+"];
[self performSequence:@"(L- R+) F+ (L+ R-) B2"];
break;
}
else if(BF_ORIENTED && !BL_ORIENTED && BR_ORIENTED && !BP_ORIENTED)
{
[self performSequence:@"(L- R+) F+ (L+ R-) B- (L- R+) F-"];
[self performSequence:@"(L+ R-) B- (L- R+) F2 (L+ R-)"];
break;
}
[self performSequence:@"Y-"];
}
}
return YES;
}

// This method does a fairly simplistic optimization pass over the
// solution sequence. It by no means produces anything even close
// to an optimal solution.
- (NSMutableString *)optimizeSolution:(NSMutableString *)solution
{
unichar currentFace, currentMove;
unichar bufferFace, bufferMove = 0;
BOOL changed;
unsigned index, length;

NSMutableString *optimized;

// With some work, this could probably do everything in
// a single pass. Basically if a buffered move was cancelled,
// move the index back and re-buffer the previous move.
do
{
changed = NO;

optimized = [[[NSMutableString alloc] init] autorelease];

bufferFace = 0;
index = 0;
length = [solution length];

while(index < length)
{
currentFace = [solution characterAtIndex:index];
currentMove = [solution characterAtIndex:index+1];
index += 2;

if(currentFace >= 'Y')
{
if(currentFace == 'Y')
{
if(currentMove == '+')
{
// "Rotate" the remaining solution
[solution replaceOccurrencesOfString:@"F"
withString:@"_"
options:NSLiteralSearch
range:NSMakeRange(index,length-index)];
[solution replaceOccurrencesOfString:@"L"
withString:@"F"
options:NSLiteralSearch
range:NSMakeRange(index,length-index)];
[solution replaceOccurrencesOfString:@"P"
withString:@"L"
options:NSLiteralSearch
range:NSMakeRange(index,length-index)];
[solution replaceOccurrencesOfString:@"R"
withString:@"P"
options:NSLiteralSearch
range:NSMakeRange(index,length-index)];
[solution replaceOccurrencesOfString:@"_"
withString:@"R"
options:NSLiteralSearch
range:NSMakeRange(index,length-index)];
changed = YES;
}
else if(currentMove == '-')
{
// "Rotate" the remaining solution
[solution replaceOccurrencesOfString:@"F"
withString:@"_"
options:NSLiteralSearch
range:NSMakeRange(index,length-index)];
[solution replaceOccurrencesOfString:@"R"
withString:@"F"
options:NSLiteralSearch
range:NSMakeRange(index,length-index)];
[solution replaceOccurrencesOfString:@"P"
withString:@"R"
options:NSLiteralSearch
range:NSMakeRange(index,length-index)];
[solution replaceOccurrencesOfString:@"L"
withString:@"P"
options:NSLiteralSearch
range:NSMakeRange(index,length-index)];
[solution replaceOccurrencesOfString:@"_"
withString:@"L"
options:NSLiteralSearch
range:NSMakeRange(index,length-index)];
changed = YES;
}
}
continue;
}
if(!bufferFace)
{
bufferFace = currentFace;
bufferMove = currentMove;
continue;
}
if(currentFace != bufferFace)
{
[optimized appendFormat:@"%c%c",bufferFace,bufferMove];
bufferFace = currentFace;
bufferMove = currentMove;
continue;
}
// Append current move to buffered move
if(bufferMove == '+')
{
if(currentMove == '-')
bufferFace = 0;
else if(currentMove == '+')
bufferMove = '2';
else
{
assert(currentMove == '2');
bufferMove = '-';
}
}
else if(bufferMove == '-')
{
if(currentMove == '+')
bufferFace = 0;
else if(currentMove == '-')
bufferMove = '2';
else
{
assert(currentMove == '2');
bufferMove = '+';
}
}
else
{
assert(bufferMove == '2');
if(currentMove == '2')
bufferFace = 0;
else if(currentMove == '+')
bufferMove = '-';
else
{
assert(currentMove == '-');
bufferMove = '+';
}
}
changed = YES;
}
// Output buffered move
if(bufferFace)
[optimized appendFormat:@"%c%c",bufferFace,bufferMove];
solution = optimized;

} while(changed);

return optimized;
}

- (NSString *)solveCube
{
CubeState initialState = state;
NSMutableString *solution, *optimized;

[self setShowsAnimation:NO];
[self setPostsNotification:NO];
[self setUndoEnabled:NO];
[self beginRecording];

// Proceed step by step. Abort if something strange
// happens (shouldn't happen assuming the solver works right).
[self solveTopEdges] &&
[self solveTopCorners] &&
[self solveVerticalEdges] &&
[self solveBottomCorners] &&
[self solveBottomEdges];

// For the curious, try modifying the code to return
// the non-optimized solution.
solution = [self endRecording];
optimized = [self optimizeSolution:solution];

[self setState:initialState];

[self setUndoEnabled:YES];
[self setShowsAnimation:YES];
[self setPostsNotification:YES];

return optimized;
}

@end

Author:	Cervantes [ Mon May 24, 2004 5:31 pm ]
Post subject:	To Program a Rubrik's Cube
how oh how?! anyone got any ideas? it can't be just a simple 3x3x3 array because the portions of the cube have different face colours (a corner has 3 colours, for example). perhaps adding another element to the array (from 1 .. 3) to track the colour of each face, but that would quickly become a nightmare.

Author:	Tony [ Mon May 24, 2004 6:18 pm ]
Post subject:
well its ether 3x3x3 of a type that contains 6 faces or 6x3x3 (6 faces, 3x3 each) ether way, I guess the hardest part would be keeping tack of proper shifts during rotations

Author:	AsianSensation [ Mon May 24, 2004 7:46 pm ]
Post subject:
OpenGL

Author:	Andy [ Tue May 25, 2004 9:27 am ]
Post subject:
if any one can make a rubix cube program that solves it completely, i'll award 500 bits.

Author:	Dan [ Tue May 25, 2004 12:36 pm ]
Post subject:
To make a progame to solve a rubic cube whould not be that hard. There are like 10-20 sets that if you do right no matter what it will solve the cube. Dose not mater where the colors start, if u do a scrent combiation it will all ways solve it. I used to have a book on it .

Author:	Andy [ Tue May 25, 2004 7:30 pm ]
Post subject:
woa.. cool... but i meant like making it spin and all that...

Author:	bugzpodder [ Tue May 25, 2004 7:32 pm ]
Post subject:
i dont know 3d graphics maybe i'll learn directX over the summer

Author:	Tony [ Wed May 26, 2004 8:05 am ]
Post subject:
3D graphics are just the visualization of the cube. For the purposes for the program, 6 separate 2D faces could be displayed just as well

Author:	Catalyst [ Thu May 27, 2004 6:07 am ]
Post subject:
thats no fun

Author:	Dan [ Thu May 27, 2004 2:11 pm ]
Post subject:
dodge_tomahawk wrote: woa.. cool... but i meant like making it spin and all that... Oh, lol. That whould be a cool app to watch. Probly easyested to make it 3dmax and just render it as a video.

Author:	@DRI@N [ Thu May 27, 2004 9:50 pm ]
Post subject:
Don't go nuts Andy! Rubix Cube is very very hard..... I don't really care about bits that much...do you want mine Andy? [mod:af2b188502="amailer"] Meh, use the edit button next time insted of making a new post, also pm the user for such things as I don't really care about bits that much...do you want mine Andy?[/mod:af2b188502]

Author:	Andy [ Fri May 28, 2004 8:05 pm ]
Post subject:
ummm im a mod... my bits are set at 1000... and stop posting useless stuff adrian

Author:	thegoose [ Thu Jun 24, 2004 11:22 am ]
Post subject:
Will random graphs do? There are so many possible solutions for a rubix cube that if you check enough sets of random moves (around 1,000,000) with a little pruning, you are bound to hit one

Author:	wtd [ Thu Jun 24, 2004 1:39 pm ]
Post subject:
thegoose wrote: Will random graphs do? There are so many possible solutions for a rubix cube that if you check enough sets of random moves (around 1,000,000) with a little pruning, you are bound to hit one I've tried that. Be prepared to watch your computer sit there and do nothing for a very long time, even if you have a decent computer.

Author:	thegoose [ Thu Jun 24, 2004 2:35 pm ]
Post subject:
Not if you do it properly, 1,000,000 is nothing programming wise (no recursive search required)

Author:	thegoose [ Fri Jun 25, 2004 2:49 pm ]
Post subject:
The point here is that if we hit one 'GOOD' solution, we are done. The good thing here is that the program can run as long as we want (about 1 minute is reasonalbe). If you read probablity books, even if the odds are miniscule, if we try it 1,000,000 (or more, since the cost of checking is linear), the odds compound to be in favour of getting at least 1 right solution. Also, the ones which are obviously stupid (aka. 3 consecutive moves which are the same, you get the idea) can be easily eliminated. I couldn't explain this THAT well online using theories (wholes books were written on this). But it belongs to a catagory of math called random graphs.

Author:	thegoose [ Fri Jun 25, 2004 3:26 pm ]
Post subject:
No, I was not refering to this specific example. I'm refering to this strategy of solving problem using random generation. The most commonly know example is Monty Carlo while Rubix-cube is just another spin-off. You'll be suprised how many problems which look very difficult can be solved this way. I have a friend who is working on how to solve the Hamiltonian tour (NP-complete) using a spin-off of this method. Because of the typo, I think it's quite interesting to mention that entire books HAVE in fact been devoted to the various methods of solving the rubix cube and I presume this strategy is one of them.

Author:	TheZsterBunny [ Mon Jun 28, 2004 6:01 pm ]
Post subject:
simple solution: you don't write it to solve the cube, you write it to undo moves made by the user. you start with a difficulty level, and based on that, have the computer make a number of turns (hidden) this allows you to have a legal, solveable cube. now, from this point, you track every move made (in addition to the starting moves), cancel the redundant ones (opposing moves in series) and just trace your steps backwards. seriously, if professors have written books on the subject, and still resort to randomly turning the blocks, its unlikely that teenage novice programmers are going to get it. thats my idea. its a whole lot simpler to script than it is to solve. -Z i remember as a kid, when i couldn't solve the cubes, i'd disassemble them and reassemble them correctly. or, if I was feeling evil, i would create an impossible puzzle, and set the task upon my father. hehehe...

Author:	thegoose [ Mon Jun 28, 2004 6:24 pm ]
Post subject:
TheZsterBunny wrote: simple solution: you don't write it to solve the cube, you write it to undo moves made by the user. you start with a difficulty level, and based on that, have the computer make a number of turns (hidden) this allows you to have a legal, solveable cube. now, from this point, you track every move made (in addition to the starting moves), cancel the redundant ones (opposing moves in series) and just trace your steps backwards. seriously, if professors have written books on the subject, and still resort to randomly turning the blocks, its unlikely that teenage novice programmers are going to get it. thats my idea. its a whole lot simpler to script than it is to solve. -Z I take it that we are not looking for a program which lets the user play the Rubix cube, but one where the user inputs the initial configuration and the program gives the solution (or outputs it's not solvable). The finding solution part doesn't look that bad (considering random generator can do the trick), but the part to determine if it's solvable or not is HARD because it's just recursion plus pruning and that can be VERY painful. The profs did not RESORT to randomness. They just mentioned it as ONE OF the possible methods. You'll be surprised on how much programming experience some of the people here got (cough: Bugz, I know you are hiding somewhere). Just as that rabit of yours doesn't look THAT evil

Author:	Cervantes [ Fri Jun 25, 2004 8:07 am ]
Post subject:
by all means, its worth trying! dan when you say that there are 10-20 sets, are you talking about 10-20 turns and twists and whatnot, or 10-20 tricks?

Author:	Dan [ Fri Jun 25, 2004 11:44 am ]
Post subject:
Cervantes wrote: by all means, its worth trying! dan when you say that there are 10-20 sets, are you talking about 10-20 turns and twists and whatnot, or 10-20 tricks? i mean there are 10-20 sets of instuctions to solve it if you start from any random point.

Author:	thegoose [ Fri Jun 25, 2004 12:46 pm ]
Post subject:
Because of symmetry, there has got to be more than that (I'm expecting at least somewhere in the 5-digits if the path is 80 in length).

Author:	Tony [ Fri Jun 25, 2004 12:52 pm ]
Post subject:
thegoose - if the path is 80 in length, how many bruteforce solutions will end up wrong?

Author:	Tony [ Fri Jun 25, 2004 3:17 pm ]
Post subject:
there are books writen on solving the rubics cube by randomly spinning it around?

Author:	bugzpodder [ Mon Jun 28, 2004 9:59 pm ]
Post subject:
thegoose wrote: If you read probablity books, even if the odds are miniscule, if we try it 1,000,000 (or more, since the cost of checking is linear), the odds compound to be in favour of getting at least 1 right solution. i think thats the stupidest thing i've ever heard... tell your friend to put the program here so we can see how shitty this method is.

Author:	Tony [ Mon Jun 28, 2004 10:15 pm ]
Post subject:
I'd have to agree with bugz there... cuz the statement holds true only if those miniscule odds are atleast 1 : number_of_random_tries but we don't live in a perfect world, and random remains random. You can flip the coin twice, and not get heads ether time, though according to probability you should have gotten that side half the time. point is that your program still have a 1/1,000,000 chance of getting the right solution at any one point

Author:	Cervantes [ Tue Jun 29, 2004 8:33 am ]
Post subject:
thegoose wrote: I take it that we are not looking for a program which lets the user play the Rubix cube, but one where the user inputs the initial configuration and the program gives the solution (or outputs it's not solvable). either program would be good. both programs in one would be best

Author:	the_short1 [ Tue Jun 29, 2004 3:29 pm ]
Post subject:
ok... DAM!... i koi know someone who made an ONLINE rubicks cube SOLVER! u enter in all the colors of each square... and it will show u STEP by step how to solve it... i tried it... and it acually WORKED! ... its so amzing... ill try to get in touch with him to get him to help u.... its so dam amazing!

Author:	zylum [ Tue Jun 29, 2004 9:04 pm ]
Post subject:
its really not that hard... as hacker dan said, there are certain sets that will complete the cube no matter what the setting (unless it's not a proper rubiks cube ie taken apart and put back together wrong such that there is no solution)

Author:	the_short1 [ Tue Jun 29, 2004 10:48 pm ]
Post subject:
yea.. but it wa really cook cuz it al depended on what u enter for each square.. and untilizing that to solve... ill try to get link.

Author:	TheZsterBunny [ Thu Aug 04, 2005 1:09 am ]
Post subject:
http://www.wrongway.org/?rubiksource found this, if anyone still wanted it