Rubik’s ParaCube

SUMMARY

We are going to parallelize several algorithms and incorporate our own heuristics to find the optimal solution to any given standard 3x3x3 Rubik’s Cube case. We will perform analysis comparing these different algorithms, and attempt to generalize some for an NxNxN Rubik’s Cube.

For the final project, the CornerDB data file required to run code is here

SCHEDULE

Nov 4 - Nov 16

Implement software from scratch, Cube representations etc., and benchmarking tools for different implementations;
Complete basic sequential implementation for resolving cubes in small number of steps;
Parallelize the basic implementation to adapt to large number of steps;
Measure all implemented code

Nov 16 - Nov 23

Implement the more sophisticated (Iterative Deepening A* based) algorithms (Korf DB) discussed in the paper.
Construct IDA with database (Database adapted from this repo)
Perform measurements for IDA with Korf (only corner) DB over BFS.

Nov 23 - Nov 30

Adapt database complete. (We spend some time to port our code and make sure our model works with the given database).
Parallelize IDA with Korf DB using OMP, and perform measurements.
Incorporate different heuristics and branch pruning techniques that we came up with (work in progress, delayed as we were blocked previous on constructing our own DB)

Nov 30 - Dec 4

(tianez) continued improvement of branch pruning techniques and OMP.
(chengzhh) MPI implementation of the optimal cube solver. We expect the OMP and MPI algorithms to be different.

Dec 4 - Dec 7

(team) Measurements over all implemented algorithms and understand the new performance characteristics.
(team) deep dive into OMP and MPI implementations

Dec 7 - Dec 9

(team) deep dive into OMP and MPI implementations

Dec 9 - Dec 14

(team) deep dive into OMP and MPI implementations
(team) Prepare for poster session and final report.

Rubik-s-ParaCube