8-puzzle

First grab puzzle8.py, which contains some useful functions for managing the 8-puzzle. DO NOT MODIFY IT.

Each location in the puzzle contains an integer from 0 to 8 (0 for the blank). The locations themselves are each also represented as an integer from 0 to 8, arranged as follows:

0 1 2
3 4 5
6 7 8

Finally, an entire configuration of the 8-puzzle (e.g., a state) is represented by a single large integer. Specifically, to represent a single state, we take each tile number times the power of its location, then add it all together. For example:

1 2 3                          1*9^0 + 2*9^1 + 3*9^2
8 . 4  is represented by:    + 8*9^3 + 0*9^4 + 4*9^5
7 6 5                        + 7*9^6 + 6*9^7 + 5*9^8 = 247893796

There are a number of functions in puzzle8.py that you will likely found useful. Start Python up interactively, import puzzle8, then type help(puzzle8). Play around at the command prompt with these functions to get a sense of how they work. What your code will ultimately do.

The goal state that you are trying to achieve is the following:

1 2 3
8 . 4
7 6 5

So for example, if the initial state was

1 . 2
8 4 3
7 6 5

The code that you write should return a list containing locations that the blank square moves to, in order. Since you will not worry about keeping track of duplicate states, if there is no solution to be found, your code will just run forever. So for the above example, the solution might appear as

[2, 5, 4]

Implement the following two functions, just to practice with the framework we’re using:

• numWrongTiles(state)
  • Returns the number of misplaced tiles for the indicated state. The blank square does not count as a misplaced tile. It isn’t a tile.
• manhattanDistance(state)
  • Returns the so-called Manhattan distance for the misplaced tiles for the indicated state: for each misplaced tile, if you could slide it right through other tiles, measure the number of steps it would take to get it to the right place; then add those up for each misplaced tile. The blank square does not count as a misplaced tile.

You should grab this search.py file to use as a starting point. I have also supplied a file titled warmup-test.py which will test your functions that you have written. You can run it via the command python warmup-test.py.

Here’s how we will grade this assignment:

You will receive a grade M (meets expectations) for this assignment if…

• when we run python warmup-test.py, your program passes the tests labels as “M” tests.
• your program is written to work in general, and not to only work for the specific tests that we have provided.

You will receive a grade of E (exemplary) for this assignment if you satisfy the above M requirements, and …

• when we run python warmup-test.py, your program passes the tests labels as “E” tests.
• your code demonstrates a clear sequence of actions to achieve the goal at hand, and each piece is essential. Your code does not have notably more cases or conditions than it needs to.

You should submit your search.py file via Moodle; this is the only file you need to submit. Do not put your name in the file; we are going to grade the assignments anonymously, where Moodle will keep track of who you are but we won’t know until we’re done grading.