Hello Guest, please login or register.
Did you miss your activation email?
Login with username, password and session length.

Pages: [1]   Go Down

Author Topic: Rubik's Cube Solver  (Read 1436 times)

0 Members and 1 Guest are viewing this topic.
Rubik's Cube Solver
« on: May 16, 2007, 12:03:04 am »
  • *
  • Reputation: +0/-0
  • Offline Offline
  • Gender: Male
  • Posts: 1635
I'll copy and paste from the GMC:

I'm going to start creating a Rubik's Cube solver. I was wondering what the best way to do this would be. Are there any algorithms out there to apply? If brute forcing is the only way, how would I go about that? I know how to solve the cube - I'm asking how to translate it into code. I mean rather, how to transfer an algorithm for solving it by hand into a computer algorithm.

I'm thinking of the best way to store piece position, color, etc. Maybe having a 3d grid, and storing a width, height, depth? Then storing colors of each piece? This is where I'm a bit lost, not the programming too much.
Logged

mit
Re: Rubik's Cube Solver
« Reply #1 on: May 16, 2007, 02:19:42 pm »
  • QBASIC programmer since age 4. Take that, world.
  • *
  • Reputation: +0/-0
  • Offline Offline
  • Posts: 1079
There was a guy famous for solving a rubik's cube using only maths. Can't remember who though.

Definitely the first step is making a virtual rubik's cube, the way I'd do it is have three grids, and each cell would have the number of the piece, not the colours on its sides. Then making a way for a human to move the pieces following the cube's rules, and then working on an algorithm to solve it. Brute force would be stupid, considering there are about 20 quintillion combinations...
Logged
Programmer / Spriter / Level designer / Game Director / Web Designer / Music Sequencer for
Random Highscore table:

Play the Kousou Arcade today!
  • Kousou Games
Re: Rubik's Cube Solver
« Reply #2 on: May 16, 2007, 02:22:24 pm »
  • *
  • Reputation: +3/-0
  • Offline Offline
  • Gender: Male
  • Posts: 6629
Gyah, that would just be painful to work out an algorithm for. Personally I would search around for a pre-existing algorithem as I'm sure there are a few.
Logged
Re: Rubik's Cube Solver
« Reply #3 on: May 16, 2007, 04:52:14 pm »
  • IBV
  • *
  • Reputation: +0/-0
  • Offline Offline
  • Gender: Female
  • Posts: 1075
You'll have to have it in some array. Then you define one function/script for rotating arg1 row, in arg2 90 degrees turns, and another for column. Then you have another function for rotating the whole cube. You write the functions so they just rotate the array and switch places on the elements (to make sure nothing wrong happens, work with a temporary array, or be very careful)

Basically you then have "solver functions" which you call whatever the algorithm is called. Then you call the rotating functions necessary on the conditions the algorithm say. What would work with hand would work in the computer :) Plus, a cool thing would be to let the solver functions return the time they executed. And you could split them in "steps" so that a user click constantly to solve step by step and see what happens every step (in an iterative algorithm you can probably just let it do another iteration per call).

Also, it might be wise to have a "scramble function". And why not an "instant solve" where you just alter and reset the array directly :)

http://en.wikipedia.org/wiki/Rubik%27s_Cube
http://en.wikibooks.org/wiki/How_to_solve_the_Rubik%27s_Cube

Also, like mit said, bruteforce would be very inefficient (but it would do the job; it always does ;D )
Logged
My signature is empty.
Re: Rubik's Cube Solver
« Reply #4 on: May 16, 2007, 08:26:01 pm »
  • *
  • Reputation: +3/-0
  • Offline Offline
  • Gender: Male
  • Posts: 6629
What you could always do as a sort of hackish approach is always have the cube start in a finished state and then randomly call functions that turn each section to scramble it. Each time you call the function you store a log of the call in an list and then to unscramble it all you have to do is iterate the list in reverse and call the reverse of each function (so function TurnX90 would change to TurnXMinus90 or something like that) which would unscramble it.
Logged
Re: Rubik's Cube Solver
« Reply #5 on: May 17, 2007, 12:35:38 am »
  • *
  • Reputation: +0/-0
  • Offline Offline
  • Gender: Male
  • Posts: 1635
Ok, but the thing is that essentially I want it to be able to input the current "state" of my cube in real life and have it spit back a series of moves that will solve it (the shortest number possible). I guess I could apply a real life algorithm that I use to solve it, but my method is somewhat slow (my personal bes time is a 68 second solve), so I'm wondering if there is a faster algorithm online, like a brute force type thing. So Helios (I will not conform...), your method won't really do what I want.

Anyone know on the best ways to implement an algorithm? Google it, or just brute force or something?
Logged
Re: Rubik's Cube Solver
« Reply #6 on: May 17, 2007, 01:14:01 am »
  • If not now, when?
  • *
  • Reputation: +0/-0
  • Offline Offline
  • Gender: Male
  • Posts: 520
Just Google for an algorithm. It exists.
Logged
Re: Rubik's Cube Solver
« Reply #7 on: May 21, 2007, 12:45:47 am »
  • *
  • Reputation: +0/-0
  • Offline Offline
  • Gender: Male
  • Posts: 1635
Well, thanks to insane amounts of help from Xot at the GMC.

//EDIT: Had to take the URL down, it'll be up soon

This is mostly xot's coding, but I understand completely how it works now. I'm going to start building my own engine, and then implement a solving algorithm. I even added a nice looking pattern :D
« Last Edit: May 21, 2007, 03:31:14 am by Scooternew »
Logged
Re: Rubik's Cube Solver
« Reply #8 on: June 13, 2007, 06:14:12 pm »
  • *
  • Reputation: +0/-0
  • Offline Offline
  • Gender: Male
  • Posts: 252
Where can I really buy a Rubik's Cube for cheap, and what is the best brand? Is it really "Hasbro", because I think so?

Infinitus Edit: This is totally the wrong topic. Just because it has 'Rubik's Cube' in the title it dosen't mean you can post anything to do with them in it.
« Last Edit: June 13, 2007, 06:15:39 pm by Infinitus »
Logged
The Legend of Zelda: The Spell Caster
Release Date: ?

I'm a faithful man! Don't be a whimp, fight for life.
Pages: [1]   Go Up
« previous next »

 


Contact Us | Legal | Advertise Here
2013 © ZFGC, All Rights Reserved


Page created in 0.073 seconds with 55 queries.