Problem Description

A sliding puzzle is two-dimensional and combinational puzzle that challenges a player to slide flat pieces along certain routes on a N by N board to establish a certain end pattern. 8-puzzle is a sliding puzzle that has 8 pieces placed on a 3 by 3 board.

The initial configuration/state of the game is usually (N times N - 1) pieces randomly placed on the N by N board with the right bottom place being the empty slot. The goal of the game is to sort these pieces so that a certain end pattern is achieved, and optionally with as few steps as possible.

The rule of the game is simple. In each step, you can only slide a piece adjacent to the empty spot into the empty spot, thus that piece's original slot becomes empty.

Not that not all sliding puzzles can be solved. NOT (edited on Sept. 21, 2023 from the student feedback) All 8-puzzle games (on 3 by 3 board) have solutions. Only about half of the 15-puzzle games (on 4 by 4 board) have solutions.

To simplify things, we'll place numbers (1 to (N times N - 1)) on the puzzle pieces. In the initial state of the game, these numbers are randomly placed. The end pattern should see these numbers sorted into numerical order from left to right, top to bottom, while the right bottom slot is the empty one.

The following shows an example of the start state of a 15-puzzle game and its goal state:

|----|----|----|----|          |----|----|----|----|
|  2 |  7 |  9 |  8 |          |  1 |  2 |  3 |  4 |
|----|----|----|----|          |----|----|----|----|
| 14 | 13 |  1 |  5 |          |  5 |  6 |  7 |  8 |
|----|----|----|----|   ==>    |----|----|----|----| 
|  3 |  4 | 10 | 15 |          |  9 | 10 | 11 | 12 |
|----|----|----|----|          |----|----|----|----| 
| 12 |  6 | 11 |    |          | 13 | 14 | 15 |    |
|----|----|----|----|          |----|----|----|----| 

Here is a simple C++ program that generates and displays a random initial state of a slide puzzle game with N set to be 4.

Your Tasks:

Implement a program that can play the sliding puzzle games. To be more specific, implement an AI agent that can read in the start state/configuration of a sliding puzzle game, find the solution using search strategies, especially A* search strategies, and display the solution steps to reach the end goal state of the game, or display a message if that particular puzzle doesn't have a solution.

Provide a Makefile to automate the compilation of your program.

Provide an assignment report (a .txt or .pdf file) that includes at least the following information:

• How to compile and execute your program? If your source code files need to be placed into subfolders in order to use the makefile, explain how the files should be organized.
• How should a user enter the initial state of the sliding puzzle game?
• What output can be expected from your program if your AI agent finds a solution of the game or fails to find a solution (hopefully only because the puzzle doesn't have a solution);
• How is a state encoded in your program;
• Where and how, in your program, is the successor function implemented?
• Where and how does your program test whether a state is the final state?
• What is the heuristics provided in your implementation of the Problem? Why do you choose this heuristics? Where in your program is the heuristics calculated?
• Where and how, in your program, is it guaranteed that the most promising state is selected to expand?
• Any known bugs;
• Any comment you would like the marker to know.

What and How to Submit

You need to submit the following files for this assignment:

• source code file(s) -- I assume that they are written in C/C++, with the extension name .cpp and .h. If you use any other programming language in implementing your program, let me know the extension name(s) of these files before you attempt submitting. And make sure that your program can be compiled and executed on otter. Thanks.
• makefile
• assignment report -- it should be either a text file (.txt) or a PDF file (.pdf).

Put all the files you want to submit in one folder on otter, submit them using the following command:
~liuh/bin/submit 485 A1 .

To check what file(s) you have submitted for this assignment, use the following command on otter:
~liuh/bin/checksubmit 485 A1