Overview / Usage

The Rubik’s cube is a physical puzzle that humans often find difficult to solve. There are various strategies humans use for solving a Rubik’s cube. For example, one way is to solve it layer by layer. However, in this problem we are not just interested in finding a sequence of moves that solves the Rubik’s cube; we are interested in finding the sequence with the fewest number of moves. If there are multiple such sequences, we want to find one of them.

The Rubik’s cube is a difficult puzzle because the decision tree for it rapidly increases in breadth. If we define a move to be one quarter turn in either clockwise or counter-clockwise rotation, after one turn the cube could be in any of 2*8 = 16 possible states. After, say, 20 turns, it could be in any of at most 16^20 = 1208925819614629174706176 states, some of which may be identical. It is known and has been proven that for this definition of a turn, the maximum number of moves required to solve a 3x3 cube is 26 moves. To solve a 2x2 cube, the corresponding number is 14 moves. This is still 16^14 = 72057594037927936 states, some of which may be identical.

Methodology / Approach

Parallel architectures are being targeted to efficiently perform the highly data-parallel computations on to reduce the search space as much as possible.

The goal of our project is to reduce this search space as much as possible. Have to test each individual sequence of moves in the decision tree is independent of all the others, to parallelize

Rubik Cube solving library and command line utility

$ pip install virtualenv

$ virtualenv venv

$ source venv/bin/activate

$ python setup.py build

$ python setup.py install

As a command

$ rubik_solver -i wowgybwyogygybyoggrowbrgywrborwggybrbwororbwborgowryby -s Beginner

​

Technologies Used

Intel optimized python

GPU

DevCloud

python libraries:

wheel

timeout-decorator

future

Repository

https://github.com/kazi92/rubikSolver