Learn how to solve problems: Rubik Hackathon part 2.

previous part of this article was about the Rubik hackathon arranged for my friends. Guys who were expected to take a part in this hackathon are not as experienced in programming and problem solving techniques as probably some readers, so if you are really familiar with Rubik’s solvers you might not be interested in reading further.
I would say that this hackathon is oriented for beginners, for students who like mathematics, algorithm development and analysis, and for guys who have already got an engineering education and now are concentrated on learning how to solve complex discrete problems with programming.

We have special github repo with a simple for use Rubik’s model and solver template.

• Capabilities it has:
• We have the Rubik’s model represented in a very simple to use python class Cube. It can be instantiated, instances support all atomic operations. I should say that the model is optimized for simplicity of usage in client code and I didn't spend much time for optimizing memory representation or operations completing speed. The list of atomic operations is:
• cube_instance.rotate(direction) with following “direction” values supported (I should notice that annotations are different from standard, user can change them): ('L+', 'L-', 'R+', 'R-', 'U+', 'U-', 'D+', 'D-', 'B+', 'B-', 'F+', 'F-') 
• cube_instance.randomize() - this method does randomizing of cube state. Be aware, it can make cube state too complex for default algorithm to solve in admissible (practical) time. Once you have developed your own algorithm, you will be able to use randomization for checking your algorithm performance and correctness.
• When you create cube instance (cube_instance.bind_visualizer(Visualizer())) or later (by calling Cube.bind_visualizer(Visualizer()))), you can assign visualization object, it will show a 3D representation of cube. It was written as a part of the hackathon by my friend Igor Yeryomin and looks pretty cool:
• 
• If you need development-only visualization, call cube_instance.print_cube() method-it’ll show cube state in terminal:
• Before applying any changes to your cube instance, you can save its state by calling cube_instance.copy() method-it creates deep copy of cube and you can hold it as one of processed states.
• cube_instance.get_distance(another_instance) returns quantity of cells which are not on their positions.
• cube_instance.get_color_distance(another_instance) returns quantity of colors which are not on their positions.
• calling cube_instance.is_equal_to(another_instance) helps to check equality of two cubes. Do not compare cubes with “==” or “!=” operators-they compare equality of objects, not states.
• How to use it. Cube API.
• Clone repository.
• git clone git@github.com:korobool/rubica.git
• Install dependencies.
• You will need vpython. it is available in ubuntu repositories and also can be downloaded from http://www.vpython.org/
• Run test code.
• python ./main.py  
• try to change this script, this is actually user code for cube handling, here you can try all cube’s capabilities (rotation, visualization, etc.)
• Try default solver.
• create new cube with cube_instance = Cube()
• Apply 3 - 4 operations to cube (e.g. cube_instance.rotate(‘L+’))
• call Solver.solve_cube(cube_instance)
• observe result
• perform your experiments








Watch quick tour through Rubik's API




• Develop your idea of how to solve cube faster than the default algorithm does.

• Consider different approaches to calculate heuristic, building edges of graph, reducing problem, using not A* solver etc. Remember, the solver you see is just a simple non-optimal template for writing your own, much better.
• Implement your idea in new solving function with the same signature as solve_cube() function has.
• Please try to make minimum changes inside Cube or Visualizer classes. Feel free to change main.py or Solver.py.
• After this is done, you will be able to learn “state of the art” by reading a bunch of articles mentioned in the previous post (some links are in Russian)

Try to join us if you are interested in improving your skills in computational problem solving. The guys have done some experiments, but they keep working and experimenting.

As I advised in the previous post, before learning the state of the art, try to solve the problem yourself.
Expected result is a good algorithm to solve random Rubik’s state which is running fast.

If you are interested in solutions sharing and discussion, mail me: korobov.alex[-a-t-]gmail.com

Possibly I'll publish one of the interesting solving algorithms later.