/Rush-Hour-Puzzle-Game-Solver

Primary LanguageJava

Rush-Hour-Puzzle-Game-Solver

Instructions

---Translate map to string to get shortest path solution---

  • 'XX' = your car
  • '22' = a car horizontally
  • 'BB' = a car of the same size vertically
  • 'CCC' = a truck vertically
  • '333' = a truck of the same size horizontally
  • '.' = an empty space
  • Move a car from one spot to another count as only 1 move

Algorithm Analysis

  • Each Map is a unique graph, the number of vertices and edges may vary
  • Use branch and bound to reduce the redundant moves from each steps, all the maps could cut some branches
  • The shortest path (steps) is not related to how complicated the map is

More Readings

Michael Fogleman

The Complexity of Sliding-Block Puzzles and Plank Puzzles - Robert A. Hearn