Hello, this thread is coming from this one : http://www.jmonkeyengine.com/jmeforum/index.php?topic=6478.0
My thesis is about simulating and solving rubik’s like puzzles. However due to the fact a generic solution is really a big thing to do, and since i already have a graduate and following courses at night, theme has been kind of “simplified” :
- Only consider cubes : this is cool since the rubikscube.java only handles cubic structure (actually 333 but working on its generalization)
- Scramble is as duenez said : generate random sequence of operations and apply it
- Solve is about actually using a given method, not simply reverse the sequence
3b) This means in later devs i may add an “input puzzle” system, a lot of solvers already do that, even with Webcam OCR :roll:
Now come the troubles… this method has been written by Arnaud Maes (in french) : http://users.skynet.be/fb819339/math-j.htm.
His method is based on Alan Hensel paper (in english) : http://www.mindspring.com/~alanh/rubikpuzzles.html
My work is to formalize this method as an algorithm. The method is a formula : PXS X’S’P’, such that :
- P: move 1/2 pieces to its/their correct position/s (correct slice)
- X: apply a sequence such that first piece is correctly placed (double exchange, double rotate and so on)
- S: "select" other piece
- X': reversed sequence X, this is second part of the solving magic for second piece
- S': re-select previous piece
- P': finalize moves by restoring the cube
All this is yet to be correctly defined/formalized but you may get the idea.
Next steps are to solve each face one at a time. This is more costy than God's algorithm http://en.wikipedia.org/wiki/God's_algorithm but is (should be) "easier for a human being".
So i have to create a human like algorithm and not an optimal one. There is a lot of reading for interesting people. One of theses is a math paper by Daniel Bump "Mathematics of the Rubik's Cube" found at http://match.stanford.edu/bump/newcube.pdf.
I think this should get you started, but i'll of course be glad to give more details :D :? :D
Other methods :
"Kociemba" - http://kociemba.org/cube.htm
"UCLA Professor Uses Artificial Intelligence Program to Solve Rubik's Cube in Minimum Number of Moves" - http://www.seas.ucla.edu/hsseas/press/1997/korfcube.html
"Solving Rubik's Cube for speed.", Lars Petrus - http://lar5.com/cube/