Today we will explore a game called "8 Puzzle" which can be solved using the classical search techniques we've talked about. The goal of the puzzle is to shift around 8 tiles until they're in "row major order." For example, if we start with the grid
we can move to this series of steps until we get to a goal state that's in row major order
Below is a cute interactive version of this, courtesy of Murhaf Sousli
Solver
Your job will be to implement a solver for a text-based version of this in Python. Click here to download the starter code. In many ways, this code mirrors the code for part 1 of Assignment 2. In particular, you will have to fill in
is_goal: True if this is a goal state, False otherwise-
get_neighbs: A method that returns a list of states which are neighbors of this state. Be very careful to use deep copies here. If you accidentally make a shallow copy of the tiles in this state, anything you do to that reference will change the original tiles.
-
solve: A method to find a shortest path from this state to a goal state. You can use the two methods above as helper methods. You should start with a tree-based version of breadth first search and then move to graph search.
Below is an example running some interactive versions of these methods via Jupyter
For Fun
Below is a cartoon (courtesy of wikimedia commons) of a political cartoon from 1880 about finding a Republican presidential candidate
