Today we will explore a game called "8 Puzzle" which can be solved using breadth-first search. 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. 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 using breadth-first search. You can use the two methods above as helper methods.
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
