CS540 Homework 2- A* Search Solution

Program Goals
Deepen understanding of state space generation
Practice implementation of an efficient search algorithm
Summary
This assignment is about solving the 8-tile puzzle we have discussed in class. The 8-tile puzzle was invented and popularized by Noyes Palmer Chapman in the 1870s. It is played on a 3x3 grid with 8 tiles labeled 1 through 8 and an empty grid. The goal is to rearrange the tiles so that they are in order.
You solve the puzzle by moving the tiles around. For each step, you can only move one of the neighbor tiles (left, right, top, bottom) into an empty grid. And all tiles must stay in the 3x3 grid. An example is shown in the picture below. In this example, there are only 2 valid moves, i.e., either moving 6 down or moving 1 right.

Given these rules for the puzzle, you will generate a state space and solve this puzzle using the A* search algorithm. Note that not all 8-tile puzzles are solvable. For this assignment, it is safe to assume that the input puzzle is always solvable.
Program Specification
The code for this program should be written in Python, in a file called funny_puzzle.py.
In this assignment, you will need to implement a priority queue. We highly recommend to use package heapq for the implementation. You should refer to heapq (https://docs.python.org/3/library/heapq.html)
if you are not familiar with it.

Even if you modify the code, you should still cite your original inspiration (and any assisting TAs or peer mentors!).
Goal State
The goal state of the puzzle is [1, 2, 3, 4, 5, 6, 7, 8, 0] , or visually:

Heuristic
Since we are using the A* search algorithm, we should agree on a heuristic. Recall the Manhattan distance used in HW1. We will use the sum of Manhattan distance of each tile to its goal position as our heuristic function.
In our first example puzzle ( [2, 5, 8, 4, 3, 6, 7, 1, 0] ) , the h() value for the original state is 10. This is computed by calculating the Manhattan distance of each title and summing them. Specifically, tiles 4/6/7 are already in place, thus they have 0 distances. Tile 1 has a Manhattan distance of 3 ( manhattan([2,1], [0,0]) = 3 ), tiles 2/3/5/8 have distances of 1/2/1/3, respectively.
Caution: do not count the distance of tile '0' since it is actually not a tile but an empty grid.
Functions
For this program you should write at least two (2) Python functions:
1. print_succ(state) — given a state of the puzzle, represented as a single list of integers with a 0 in the empty space, print to the console all of the possible successor states
2. solve(state) — given a state of the puzzle, perform the A* search algorithm and print the path from the current state to the goal state
Print Successors
This function should print out the successor states of the initial state, as well as their heuristic value according to the function described above. The number of successor states depends on the current state. There could be 2 (empty grid is at corner), 3 (empty grid is at middle of a boundary), or 4 (empty grid is at the center of a boundary) successors.

We do require that these be printed in a specific order: if you consider the state to be a nine-digit integer, the states should be sorted in ascending order. Conveniently, if you ask Python to sort one-dimensional arrays, it will adhere to this order by default; don't do more work than you have to:

Priority Queue
Now is a good time to implement the priority queue in your code.
We recommend you use the python library heapq to create your priority queue. Here is a quick example:

The code will push an item ([1, 2, 3, 4, 5, 0, 6, 7, 8], (0, 5, -1)) with priority 5 into the queue. This format follows (g+h, state, (g, h, parent_index)) representing both the cost, state and the parent index in A* search (a parent index of -1 denotes the initial state, without any parent). For more details, please refer
to the documentation of (https://docs.python.org/3/library/heapq.html) heapq (https://docs.python.org/3/library/heapq.html) .
To get the final path, for each element in the priority queue we need to remember its parent state. Remember to store the state when you pop it from the priority queue, so you could refer to it later when you generate the final path.
Here is how you can pop from a priority queue,

The priority queue is stored in a list and you can print its items (with the associated priority) by using

Note that the heappush maintains the priority in ascending order, i.e., heappop will always pop the element with the smallest priority.
We require that the states with the same cost (priority) to be popped in a specific order: if you consider the state to be a nine-digit integer, the states should be sorted in ascending order - just like we mentioned above. If you follow the format in pq as shown above, heapq will automatically take care of this and you do not need more work.
Solve the Puzzle
This function should print the solution path from the provided initial state to the goal state, along with the heuristic values of each intermediate state according to the function described above, and total moves taken to reach the state. Recall that our cost function g(n) is the total number of moves so far, and every valid successor has an additional cost of 1.


Note: please do not use exit() or quit() to end your function when you find a path, as this will cause Python to close entirely.
Additional Examples
For your successor function:

For your solution function:

Additional hints
For some complicated cases, your solve function could take a very long time to get an answer, or maybe even the entire program breaks. It is recommended that you don't explore any state that has been seen before. To do this, you can use a set to track which states have been seen already.

Submission
Some Rubric

Criteria Ratings Pts
print_succ 1 5.0 pts
print_succ 2 5.0 pts
print_succ 3 5.0 pts
print_succ 4 5.0 pts
solve 1 10.0 pts
solve 2 10.0 pts
solve 3 10.0 pts
solve 4 10.0 pts
solve complicated 1 20.0 pts
solve complicated 2 20.0 pts