mp_puzzle

Goals and Overview

In this MP, you will:

• Work with a graph that is to large too store completely in memory
• Use a graph algorithm to solve a complex problem
• Implement an algorithm from public sources documents
• See the difference in performance between a guided and unguided search algorithm

Checking Out the Code

All assignments will be distributed via our release repo on github this semester. You will need to have set up your git directory to have our release as a remote repo as described in our git set up

You can merge the assignments as they are released into your personal repo with

git pull --no-edit --no-rebase release main
git push

if you are using multiple machines you may need to use the following to allow them to work correcly.

git pull --no-edit --no-rebase release main --allow-unrelated-histories
git push

The first git command will fetch and merge changes from the main branch on your remote repository named release into your personal. The --no-edit flag automatically generates a commit message for you, and the--no-rebase flag will merge the upstream branch into the current branch. Generally, these two flags shouldn’t be used, but are included for ease of merging assignments into your repo.

The second command will push to origin (your personal), which will allow it to track the new changes from release.

You will need to run these commands for every assignment that is released.

All the files for this mp are in the mp_puzzle directory.

Preparing Your Code

This semester for MPs we are using CMake rather than just make. This allows for us to use libraries such as Catch2 that can be installed in your system rather than providing them with each assignment. This change does mean that for each assignment you need to use CMake to build your own custom makefiles. To do this you need to run the following in the base directory of the assignment. Which in this assignment is the mp_puzzle directory.

mkdir build
cd build

This first makes a new directory in your assignment directory called build. This is where you will actually build the assignment and then moves to that directory. This is not included in the provided code since we are following industry standard practices and you would normally exclude the build directory from any source control system.

Now you need to actually run CMake as follows.

cmake ..

This runs CMake to initialize the current directory which is the build directory you just made as the location to build the assignment. The one argument to CMake here is .. which referes to the parent of the current directory which in this case is top of the assignment. This directory has the files CMake needs to setup your assignment to be build.

At this point you can in the build directory run make as described to build the various programs for the MP.

You will need to do the above once for each assignment. You will need to run make every time you change source code and want to compile it again.

Assignment Description

In this mp we will be developing a puzzle solver for 15 puzzle as a graph problem. If you have not heard of 15 puzzle before you may want to look at the wikipedia article on it here. We will then generate an animation of the solution.

Part 1: The PuzzleState data structure

In the first part of this assignment we will work on representing the puzzle as a graph. To do this we will have a node for every possible position of the puzzle and an edge between two nodes if there is a single move of a tile that will move from one position to the next. The tricky part in this is that there are 16 factorial possible positions for the puzzle. Since this is way too large to store in memory we will need to only use the portions of the graph that we need to get from the starting position until we can find a solution.

To do this we will build a class PuzzleState that stores a single vertex of the graph but can also create its neighbors when asked. This is not hard to do since the possible positions you can move to are easy to compute only knowing the current position. This will give you a system where you only need to create the nodes of the graph when you explore them. You will need to implement all the methods in the PuzzleState class.

Creating and Outputing

While the internal implementation of the PuzzleState class is entirely up to you we are defining two functions to make sure that we agree on what state we are referring to. These functions are the Constructor that takes an array of positions and creates a PuzzleState with those positions and asArray which returns the array version of that state. The format of this is to list the values in the puzzle starting for the upper left hand corner and moving to the right until the end of the line then moving to the next line until all 16 positions are provided.

Implementing operator<

To ensure that you can use std::map to store PuzzleStates we require you to implement an operator<(). While this operator does not represent any real relation between the different puzzle states it will satisfy the requirement for a total order so that you can use std::map.

Manhattan Distance

One function that might be unclear is the manhattanDistance function. This is asking you to compute a distance value between two states. This distance is the distance that each tile has to travel in the x dimension and the y dimension to reach the location of the tile in the other state.

Testing Your Code

Provided Catch test cases are available as well by running:

make test
./test

Extra Credit Submission

For extra credit, you can submit the code you have implemented and tested for part one of mp_puzzle. You must submit your work before the extra credit deadline as listed at the top of this page. See Handing in Your Code for instructions.

Part 2: The Solve Functions

In part 2 we are writing two different functions that will each solve the puzzle by finding the shortest path from the start state to the goal state. If the goal is not stated, the standard solved state will be used. The first version will solve this by implementing breadth first search. The second will use the A* algorithm. The doxygen of these functions can be seen here solveBFS and solveAstar.

A* search Algorithm

The A* algorithm is an algorithm for finding the shortest path from one point in a graph to another point in the graph. Documentation on the general algorithm can be found on wikipedia here. You should use the material provided there as the basis for your implementation. The key idea here is that A* uses a heuristic function to estimate how much further a state is from the goal state. In our case we will be using the manhattan distance function we wrote in part 1. This works since each move in the puzzle moves a single piece in a single direction so the minimum distance from a state to the goal state is enough moves to move each piece directly there.

Handing in your code

You must submit your work on PL for grading. We will use the following files for grading:

• puzzle.h
• puzzle.cpp

All other files will not be used for grading.