Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
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 10-20 sets, are you talking about 10-20 turns and twists and whatnot, or 10-20 tricks?

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

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 5-digits 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 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

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...

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.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 2 of 3  [ 33 Posts ]
Goto page Previous  1, 2, 3  Next
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: