Rubik's Cube: simulating, solving

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

  1. Only consider cubes : this is cool since the rubikscube.java only handles cubic structure (actually 333 but working on its generalization)
  2. Scramble is as duenez said : generate random sequence of operations and apply it
  3. 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/

This sounds cool, my only question is if there is an actual question in the post 

Sorry i made the post to create context of work.



Currently i've been modifiying Rubikscube.java to use it as a View (MVC).

My data model is a 3-dimensional array, i'm currently working on slices rotations to reflect data model after a given rotation.



I exposed this for jfaerman in previous "group or not group" thread.