A* Puzzle Solver

Using A* to solve 8 and 15 tile puzzles

Authors

• Pat Hawks
• Ryan Larson
• Rui Yang

Directory Structure

.
├── data
│   ├── 3x3.tgz           # Boards archive
│   ├── 4x4.tgz           # Boards archive
│   ├── results           # Experimental results
|   |   └── canonical     # Processed data
│   └── test-board.txt
├── docs
│   ├── analysis          # Chart outputs
│   ├── notes.md
│   ├── outline.md
│   └── paper.md
├── index.html            # Interactive analysis
├── launch.sh
├── Makefile
├── README.md
└── src
    ├── analysis          # Results analysis
    └── main              # Application

How to run

Compile with make and run in your shell with scala Project.jar <file.txt> <search> <heuristic> where:

• <file.txt> File containing a text representation of the puzzle to solve (See test-board.txt for an example)
• <search> Search algorithm to use. Can be one of
  • astar A*
  • ida Iterative Deepening A*
• <heuristic> Heuristic to use. Can be one of
  • dummy Always returns 0
  • manhattan Sum of Manhattan distance of all tiles to correct position
  • linearConflict Linear Conflict
  • NMaxSwap Number of swaps between incorrect tiles and empty space necessary to arrive at solution
  • nonAdditiveFringe Nonadditive Pattern Database
  • nonAdditiveCorner Nonadditive Pattern Database
  • nonAdditiveMax Maximum of nonAdditiveFringe & nonAdditiveCorner
  • disjointPDBVertical Disjoint Pattern Database
  • disjointPDBHorizontal Disjoint Pattern Database
  • disjointPDBMax Maximum of disjointPDBVertical & disjointPDBHorizontal

The program will return results as a row of Comma Seperated Values in the format:

Board Size, <file.txt>, <search>, <heuristic>, Expanded Nodes, Effective Branching Factor, Number of moves in optimal solution, run time

All of our data was generated by running launch.sh on the data files in data/3x3.tgz and data/4x4.tgz. Each of these archives contain all of the puzzles of that board size that are solvable in 20 or fewer moves. They are organized into subdirectories by size of the optimal solution. If these files are expanded, launch.sh can be executed to rerun tests, albeit with perhaps a different subset of test cases.