Skip to content
Code + website for our 15-418 project: Solving the 15-Puzzle with Parallel A*
HTML C++ Makefile
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
graphs
images
tests
Fifteen_puzzle.png
README.md
board.cpp
index.html
main.cpp
makefile
parallel.cpp
priorityqueue.cpp
run
sequential.cpp
state.cpp
tspriorityqueue.cpp

README.md

How to Run Our Program

Running a File

In order to run the A* algorithm on a specific board input of the puzzle, we can encode the board input in a file.

The layout of the file must be like:

3 
1 3 4 
2 5 6
8 7 0

The first line is the width of the board. The following files are the board input, with the 0 encoding the empty space.

Then, you can type the following into the command line:

make
./run -t numThreads -b bucketMultiplier -f filename 
  • numThreads: The number of threads working on the algorithm. If the flag is omitted, the sequential implementation is ran. An input greater than 0 runs the parallel version.
  • bucketMultiplier: If running the parallel version, the program will allot bucketMultiplier number of priority queues per thread. The default value is 1.
  • filename: The full name of your file. We have sample files you can use in the tests folder.

Examples:

make
./run -t 16 -b 128 -f tests/med1.txt

This will run the parallel version on tests/med1.txt with 16 threads, each thread getting an average 128 priority queues.

make
./run -f tests/med1.txt

This will run the sequential version on tests/med1.txt.

Randomized Input

We can also run the algorithm on a randomized input, generated by the program.

You can type the following into the command line:

make
./run -t numThreads -b bucketMultiplier -m moves -s size
  • numThreads: The number of threads working on the algorithm. If the flag is omitted, the sequential implementation is ran. An input greater than 0 runs the parallel version.
  • bucketMultiplier: If running the parallel version, the program will allot bucketMultiplier number of priority queues per thread. The default value is 1.
  • moves: The system will begin with the goal board and perform m randomly generated moves. A greater m signifies a more randomized board.
  • size: The width of the board. The default value is 3.

An example:

make
./run -t 16 -b 1 -m 200 -s 4

This will run after performing 200 randomly generated moves on the goal board, with width 4. It will support 16 threads, each with one priority queue.

You can’t perform that action at this time.