----------------------------------- Cervantes Mon May 24, 2004 5:31 pm 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. :think: ----------------------------------- Tony Mon May 24, 2004 6:18 pm ----------------------------------- 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 ----------------------------------- AsianSensation Mon May 24, 2004 7:46 pm ----------------------------------- OpenGL :lol: ----------------------------------- Andy Tue May 25, 2004 9:27 am ----------------------------------- if any one can make a rubix cube program that solves it completely, i'll award 500 bits. ----------------------------------- Dan Tue May 25, 2004 12:36 pm ----------------------------------- 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 :P . ----------------------------------- Andy Tue May 25, 2004 7:30 pm ----------------------------------- woa.. cool... but i meant like making it spin and all that... ----------------------------------- bugzpodder Tue May 25, 2004 7:32 pm ----------------------------------- i dont know 3d graphics :( maybe i'll learn directX over the summer ----------------------------------- Tony Wed May 26, 2004 8:05 am ----------------------------------- 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 :lol: ----------------------------------- Catalyst Thu May 27, 2004 6:07 am ----------------------------------- thats no fun :lol: ----------------------------------- Dan Thu May 27, 2004 2:11 pm ----------------------------------- 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. ----------------------------------- @DRI@N Thu May 27, 2004 9:50 pm ----------------------------------- 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? 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? ----------------------------------- Andy Fri May 28, 2004 8:05 pm ----------------------------------- ummm im a mod... my bits are set at 1000... and stop posting useless stuff adrian ----------------------------------- thegoose Thu Jun 24, 2004 11:22 am ----------------------------------- 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 ----------------------------------- wtd Thu Jun 24, 2004 1:39 pm ----------------------------------- 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. ----------------------------------- thegoose Thu Jun 24, 2004 2:35 pm ----------------------------------- Not if you do it properly, 1,000,000 is nothing programming wise (no recursive search required) ----------------------------------- Cervantes Fri Jun 25, 2004 8:07 am ----------------------------------- 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? ----------------------------------- Dan Fri Jun 25, 2004 11:44 am ----------------------------------- 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. ----------------------------------- thegoose Fri Jun 25, 2004 12:46 pm ----------------------------------- 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). ----------------------------------- Tony Fri Jun 25, 2004 12:52 pm ----------------------------------- thegoose - if the path is 80 in length, how many bruteforce solutions will end up wrong? :lol: ----------------------------------- thegoose Fri Jun 25, 2004 2:49 pm ----------------------------------- 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. ----------------------------------- Tony Fri Jun 25, 2004 3:17 pm ----------------------------------- there are books writen on solving the rubics cube by randomly spinning it around? :? :lol: ----------------------------------- thegoose Fri Jun 25, 2004 3:26 pm ----------------------------------- 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. ----------------------------------- TheZsterBunny Mon Jun 28, 2004 6:01 pm ----------------------------------- 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... ----------------------------------- thegoose Mon Jun 28, 2004 6:24 pm ----------------------------------- 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 :D ----------------------------------- bugzpodder Mon Jun 28, 2004 9:59 pm ----------------------------------- 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. ----------------------------------- Tony Mon Jun 28, 2004 10:15 pm ----------------------------------- 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 :roll: ----------------------------------- Cervantes Tue Jun 29, 2004 8:33 am ----------------------------------- 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 :D ----------------------------------- the_short1 Tue Jun 29, 2004 3:29 pm ----------------------------------- 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! ----------------------------------- zylum Tue Jun 29, 2004 9:04 pm ----------------------------------- 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) ----------------------------------- the_short1 Tue Jun 29, 2004 10:48 pm ----------------------------------- 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. ----------------------------------- rizzix Fri Jul 02, 2004 1:58 pm ----------------------------------- aah i knew i had seen it somewhere... and i found it. it was in tutorial demo from apple on opengl/cocoa.. it has the rubics cube solving algorithm ^_^. i've posted the algorithm only.. it requres a couple of ther files to render the cube etc.. also knowledge of obj-c is required. */ #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 ----------------------------------- rizzix Fri Jul 02, 2004 2:05 pm ----------------------------------- pretty straightforward if u ask me :? and here's what the perfromSequence method would look like: - (void)performSequence:(NSString *)sequence { unichar c, c2, undo; unsigned i, count; SEL selector; NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init]; count = [sequence length]; for(i = 0; i < count;) { c = [sequence characterAtIndex:i]; i++; switch(c) { case 'F': selector = @selector(rotateFront:); break; case 'P': selector = @selector(rotateBack:); break; case 'L': selector = @selector(rotateLeft:); break; case 'R': selector = @selector(rotateRight:); break; case 'T': selector = @selector(rotateTop:); break; case 'B': selector = @selector(rotateBottom:); break; case 'X': selector = @selector(rotateXAxis:); break; case 'Y': selector = @selector(rotateYAxis:); break; case 'Z': selector = @selector(rotateZAxis:); break; default: selector = NULL; break; } if(selector) { int movecount; BOOL ok = YES; BOOL showAnim = showAnimation; c2 = [sequence characterAtIndex:i++]; switch(c2) { case '+': movecount = 1; undo = '-'; break; case '-': movecount = -1; undo = '+'; break; case '2': movecount = 2; undo = '2'; break; default: ok = NO; undo = 0; break; } if(ok) { NSInvocation *moveInvocation = [NSInvocation invocationWithMethodSignature: [self methodSignatureForSelector:selector]]; [moveInvocation setTarget:self]; [moveInvocation setSelector:selector]; [moveInvocation setArgument:&movecount atIndex:2]; showAnimation = NO; [moveInvocation invoke]; // Get back new state (without posting notification) [moveInvocation getReturnValue:&state]; showAnimation = showAnim; // Handle undo. if(undoEnabled) [[[[NSApp delegate] undoManager] prepareWithInvocationTarget:self] performSequence: [NSString stringWithFormat:@"%c%c",c,undo]]; // Append sequence if animating if(showAnimation) [self appendAnimationSequence: [NSString stringWithFormat:@"%c%c",c,c2]]; // Append sequence if recording if(recordingSequence) [recordingSequence appendFormat:@"%c%c",c,c2]; } } } [pool release]; } ----------------------------------- TheZsterBunny Thu Aug 04, 2005 1:09 am ----------------------------------- http://www.wrongway.org/?rubiksource found this, if anyone still wanted it