Parallel Rubiks Cube Solver

Parallel Rubiks Cube Solver implementation using OpenMP for the 15-418 class. Developed by Diego Garza Rodriguez and Nihar Pol. Fall 2017

View project on GitHub

Project Proposal / Project Checkpoint / Final Project Report / Tasks

TASKS

Diego

Thursday, November 23

  • [x] Basic serial implementation using Iterative Deepening Depth First Search.

Monday, November 27

  • [x] Record time to solve benchmark cube for serial implementation Iterative Deepening Depth First Search.
  • [x] Record highest deep achieved by serial Iterative Deepening Depth First Search within 5 minutes using deep 18 cube.

Thursday, November 30

  • [x] Improving Iterative Deepening Depth First Search parallel algorithm.

Monday, December 4

  • [x] Record time to solve benchmark cube for parallel implementation Iterative Deepening Depth First Search.
  • [x] Record highest deep achieved by parallel Iterative Deepening Depth First Search within 5 minutes using deep 18 cube.
  • [x] Compare performance of parallel implementation of Iterative Deepening First Search varying the amount of processors.

Thursday, December 7

  • [ ] Adapting parallel implementation for Iterative Deepening A* search algorithm with manhattan distance heuristic.

Monday, December 11

  • [x] Implementing pattern database heuristic.
  • [ ] Record time to solve benchmark cube for serial implementation Iterative Deepening A* Search with pattern database heuristic.
  • [ ] Record highest deep achieved by serial Iterative Deepening A* Search with pattern database heuristic within 5 minutes using deep 18 cube.

Tuesday, December 12

  • [x] Wrap up project and make poster for presentation.

Nihar

Thursday, November 23

  • [x] Basic parallel implementation using Iterative Deepening Depth First Search and OpenMP.

Monday, November 27

  • [x] Prune redundant tree searches.
  • [ ] Switching serial implementation to Iterative Deepening A* search.

Thursday, November 30

  • [ ] Implementing Manhattan distance heuristic.
  • [ ] Record time to solve benchmark cube for serial implementation Iterative Deepening A* Search with manhattan distance heuristic.
  • [ ] Record highest deep achieved by serial Iterative Deepening A* Search with manhattan distance heuristic within 5 minutes using deep 18 cube.

Monday, December 4

  • [ ] Improving parallel implementation for Iterative Deepening A* search algorithm with manhattan distance heuristic.

Thursday, December 7

  • [ ] Record time to solve benchmark cube for parallel implementation Iterative Deepening A* Search with manhattan distance heuristic.
  • [ ] Record highest deep achieved by parallel Iterative Deepening A* Search with manhattan distance heuristic within 5 minutes using deep 18 cube.
  • [ ] Compare performance of parallel implementation of A* Search varying the amount of processors.

Monday, December 11

  • [x] Supporting pattern database heuristic in the parallel algorithm.
  • [ ] Record time to solve benchmark cube for parallel implementation Iterative Deepening A* Search with pattern databases heuristic.
  • [ ] Record highest deep achieved by parallel Iterative Deepening A* Search with pattern databases heuristic within 5 minutes using deep 18 cube.
  • [ ] Compare performance of parallel implementation of A* Search with pattern databases heuristic varying the amount of processors.

Tuesday, December 12

  • [x] Wrap up project and make poster for presentation.