Megaminx Solver

Designs, randomizes, and solves a virtual Megaminx (a 12-face Rubik's Cube).

C++ program that designs and randomizes a Megaminx puzzle and solves it using the A* search algorithm. It uses Floyd-Warshall algorithm to create a matrix used to find the distance used for the heuristic and then outputs the steps to solve the puzzle.

Demo

Features

  • Implements A* algorithm to find shortest distance between randomized and solved Megaminx

  • Floyd-Warshall algorithm used to create minimum distance matrix between faces

  • Creates a virtual Megaminx, randomizes it using random clockwise and counterclockwise turns, and prints solution path

Skills Learned

  • Coding the A* search algorithm

  • Designing and manipulating a virtual 2D model of a 3D object

  • Managing space complexity to optimize the number of turns away from solution that the puzzle could be solved for

Acknowledgments

  • Professor Judy Goldsmith at the University of Kentucky presented this as a project in her Fall 2018 CS463 Artificial Intelligence course and did an excellent job teaching the concepts and algorithms neccessary for this implementation