8 Puzzle

This is an implementation of a 8 puzzle game being solved through traversal algorithms.

Roadmap

• Depth first search
• Breadth first search
• Uniform cost search
• A* search

Data structures

• Depth first search
  • Open nodes: stack
• Breadth first search
  • Open nodes: queue
• Uniform cost search
  • Open nodes: sorted list
• A* search
  • Open nodes: sorted list

"Half of the starting positions for the n puzzle are impossible to resolve."

Johnson, Wm. Woolsey; Story, William E. (1879), "Notes on the "15" Puzzle"

Tasks

• Node
  • Structure
  • Is objective
  • Compare
  • Children
• Open nodes
  • Structure
    • Queue
      • Find
      • Pop
    • SortedList
      • Sort
      • Find
      • Pop
• Runtime
  • Interval
  • Generate random inital state
• Search
  • Weights
  • Prediction heuristic

Bonus

• Display node
• Display solving process

References

• N-Puzzle solvability
• Order array nulls last
• Generate initial state
• Swap array index
• Tree visualization
• Generate random arbitrary