Graduation Semester and Year

2005

Language

English

Document Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science and Engineering

First Advisor

Ishfaq Ahmad

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.

Disciplines

Computer Sciences | Physical Sciences and Mathematics

Comments

Degree granted by The University of Texas at Arlington

Download

Share

COinS