Project 1: 15-Puzzle

Due Friday, Feb 20 at 2359.¶

The 15-Puzzle is just a bigger extension of the 8-Puzzle to a 4x4 grid. Read about it on the wikipedia article. A good reference paper is here. Your task is to write a python program that solves the the 15-puzzle using A* search and produces the list of moves to solve it.

Download the starter files from this zip file

I started you off with a working implementation of the Board class in board.py. You must write two functions after the class for two heuristics that take a Board argument and return the heuristic’s value for that board. The two required heuristics are manhattan distance and misplaced tiles. I’ve already written an atomic manhattan distance function that works on two points, but you must write the full manhattan for the board.

Your primary A* function will be called astar, and it will take a Board and a heuristic function as arguments, and it returns a list of the moves to solve it along with the total number of nodes that were expanded to find those moves. An example that is returned from your astar will look like:

 [(2,2),(1,2),(0,2),(0,1),(0,0)], 154

The above means there are 5 tile moves, and A* searched 154 nodes to find this solution. For the positions, (2,3) would be tile 12 in the picture below. That would slide 12 down and the blank is now at position (2,3).

Winning Configuration

You must write your code so that a winning position is the following:

Specific Requirements

• Fill in manhattan(board) and misplaced_tiles(board) at the bottom of board.py

• Write a priority queue implementation by filling in the 4 functions in priqueue.py

• Write astar(start_board, heuristic) in the file astar.py

• Run test.py and get True for all outputs

Some thoughts:

• You need to make copies of the board when you generate the children of a state. copy.deepcopy(x) is handy for that.

• You will need a priority queue. You can use built-in python help, but you must fill in priqueue.py

  • You need to be able to add a new value even if the item is already in the queue with a different value.

  • Unsorted lists are not crazy ideas for a priority queue. Remember that heaps are generally faster, but if you are doing many more inserts than removeMins, an unsorted list is faster. Are you doing many more inserts than removeMins?

Submissions¶

Submitted files should be named:

astar.py
board.py
priqueue.py

How to Submit Manually:

• Visit and login: submit.cs.usna.edu

• Click SI420 on top right drop-down, and then project1

• Click your username top left and “Upload Files”

How to Submit Command-Line:

submit -c=si420 -p=project1 astar.py board.py priqueue.py