To Program a Rubrik's Cube
Author 
Message 
Cervantes

Posted: Fri Jun 25, 2004 8:07 am Post subject: (No subject) 


by all means, its worth trying!
dan when you say that there are 1020 sets, are you talking about 1020 turns and twists and whatnot, or 1020 tricks? 





Sponsor Sponsor



Dan

Posted: Fri Jun 25, 2004 11:44 am Post subject: (No subject) 


Cervantes wrote: by all means, its worth trying!
dan when you say that there are 1020 sets, are you talking about 1020 turns and twists and whatnot, or 1020 tricks?
i mean there are 1020 sets of instuctions to solve it if you start from any random point. 
Computer Science Canada
Help with programming in C, C++, Java, PHP, Ruby, Turing, VB and more! 




thegoose

Posted: Fri Jun 25, 2004 12:46 pm Post subject: (No subject) 


Because of symmetry, there has got to be more than that (I'm expecting at least somewhere in the 5digits if the path is 80 in length). 





Tony

Posted: Fri Jun 25, 2004 12:52 pm Post subject: (No subject) 


thegoose  if the path is 80 in length, how many bruteforce solutions will end up wrong? 
Tony's programming blog. DWITE  a programming contest. 




thegoose

Posted: Fri Jun 25, 2004 2:49 pm Post subject: (No 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. 





Tony

Posted: Fri Jun 25, 2004 3:17 pm Post subject: (No subject) 


there are books writen on solving the rubics cube by randomly spinning it around? 
Tony's programming blog. DWITE  a programming contest. 




thegoose

Posted: Fri Jun 25, 2004 3:26 pm Post subject: (No 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 Rubixcube is just another spinoff. 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 (NPcomplete) using a spinoff 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

Posted: Mon Jun 28, 2004 6:01 pm Post subject: (No 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... 





Sponsor Sponsor



thegoose

Posted: Mon Jun 28, 2004 6:24 pm Post subject: (No 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 





bugzpodder

Posted: Mon Jun 28, 2004 9:59 pm Post subject: (No 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. 





Tony

Posted: Mon Jun 28, 2004 10:15 pm Post subject: (No 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 
Tony's programming blog. DWITE  a programming contest. 




Cervantes

Posted: Tue Jun 29, 2004 8:33 am Post subject: (No 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 





the_short1

Posted: Tue Jun 29, 2004 3:29 pm Post subject: (No 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! 





zylum

Posted: Tue Jun 29, 2004 9:04 pm Post subject: (No 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) 





the_short1

Posted: Tue Jun 29, 2004 10:48 pm Post subject: (No 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. 






