Solving The Rubik's Cube With Parallel Processing

Abstract

This thesis investigates parallel processing techniques for solving the 3 x 3 x 3 Rubik's Cube. We explore various state-space search based algorithmic approaches to optimally solve the Cube. The parallel processing approach is based on IDA* using a pattern database as the underlying heuristic because of its well established effectiveness. The parallel algorithm is an extension of the Michael Reid algorithm which is sequential. The parallel algorithm exhibits good speedup and scalability. Nearly 150 random as well as symmetrical cube configurations were tested for the experiments on sequential and parallel implementations. The proposed parallel algorithm using master-slave type of load balancing proves efficient in terms of time as well as memory resources while yielding an optimal solution to find the state of a Rubik's cube. Parallel processing helps in solving a Cube with initial cube configurations having solutions at a higher depth level in the search tree. Various comparative results are provided to support the efficiency of the parallel implementation.