Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 To Program a Rubrik's Cube
Index -> General Programming
Goto page Previous  1, 2, 3  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Cervantes




PostPosted: Fri Jun 25, 2004 8:07 am   Post subject: (No 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?
Sponsor
Sponsor
Sponsor
sponsor
Dan




PostPosted: 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 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.
Computer Science Canada Help with programming in C, C++, Java, PHP, Ruby, Turing, VB and more!
thegoose




PostPosted: 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 5-digits if the path is 80 in length).
Tony




PostPosted: 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? Laughing
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
thegoose




PostPosted: 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




PostPosted: 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? Confused Laughing
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
thegoose




PostPosted: 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 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




PostPosted: 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
Sponsor
sponsor
thegoose




PostPosted: 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 Very Happy
bugzpodder




PostPosted: 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




PostPosted: 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 Rolling Eyes
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
Cervantes




PostPosted: 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 Very Happy
the_short1




PostPosted: 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




PostPosted: 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




PostPosted: 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.
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 2 of 3  [ 33 Posts ]
Goto page Previous  1, 2, 3  Next
Jump to:   


Style:  
Search: