Sliding block puzzles have been around since the 1800s, possibly earlier. An example is shown below. In this game you have an N by M grid with N ⋅ M − 1 blocks. Blocks are numbered 1 through N ⋅ M − 1. The goal of the game is to get the numbers in order, starting with the blank space in the upper left and incrementing as you read the blocks in the usual (English left-to-right) reading order. (Alternatively, the empty space could be in the lower right; the starter code for this assignment uses the upper-left convention.) Moves in the game are made by sliding a block into the empty space.
Here’s an example:
The above puzzle is playable! Click numbers next to the empty space. It’s also keyboard accessible – after clicking on the grid (to put keyboard focus there) you can use the arrows keys, and you can also do “s” to reshuffle the blocks. Try to solve the puzzle – there’s a (quite nice, IMHO) Easter egg.
I made an SVG the 15 puzzle because it’s a simple graphic and the resulting file is a human-editable text file, much smaller than a corresponding PNG or other raster image. But! The SVG structure is part of the DOM and therefore can be manipulated with Javascript. So: you can move the blocks!
I recommend taking a look at the SVG. Start by looking at the static version to see the kind of elements we need to put into the DOM. Then, see the above version: fifteen-puzzle-playable.svg. Read the code – the algorithms there are very similar to what you’ll use in this assignment. Compare that with Claude Fable’s original animated version.
I originally had Claude vibe-code it, and the code was perfectly functional and easy enough to read. But I wanted to make a little change…and on closer reading, realized the code really needed refactoring. In particular, the initial code mixed together internal state updates with displaying the state. It’s easier to modify and maintain code where those semantically independent areas are neatly decoupled.
In the end I spent…probably far more time than I should have fiddling. But I brushed up on my CSS, particularly animations, and got a good lesson – sure, the frontier models like Fable are really good but their work does need human review and evaluation.
The starter code repo has puzzle.py and
hw1-starter.py. In your repository, create a directory
called hw1. Copy puzzle.py, keeping the name,
and copy the hw1 starter file to hw1.py. Make
a blank hw1-writeup.txt file.
You may now play the tile game by running the following command in the directory where these files exist:
python3 hw-1-starter.py --search human
After you run this command, you should see the following
Try to get the blank space (.) to the top-left and numbers 1-8 in order!
Grid:
3 5 1
7 . 6
4 8 2
----------
Enter number to move (1-8):From here, you can select a block to move into the blank space (represented by the period). In this case, you may move 5, 7, 6, or 8 as they are next to the blank space. You are not allowed to move on diagonals. For example, if you select 5, this will be the next output:
Grid:
3 . 1
7 5 6
4 8 2
----------
Enter number to move (1-8):The goal is to get the following grid:
Grid:
. 1 2
3 4 5
6 7 8Currently, the game is hardcoded with the state
[[3, 5, 1], [7, 0, 6], [4, 8, 2]]. You can see this in the
main function when the game is created. To make it random, change the
line from
game = PuzzleGame([[3,5,1],[7,0,6],[4,8,2]])
to
game = PuzzleGame()
To begin with, the starter code provides a breadth-first search implementation with the function bfs. To run it, you can use the following command:
python3 hw-1-starter.py --search bfs
You should see the following output:
Try to get the blank space (.) to the top-left and numbers 1-8 in order!
Grid:
3 5 1
7 . 6
4 8 2
----------
Solution: [6, 2, 8, 6, 5, 1, 2, 5, 7, 4, 6, 7, 4, 3]
Congratulations! Your search solved the puzzle in 14 moves!The solution contains the order in which numbers are moved.
For each line in the bfs function, annotate the code
with a comment stating what the line does. A few words to a sentence
should suffice. If there is any function you do not understand, feel
free to look up the function. Please provide sources in the write-up.txt
file.
In the starter code, there were three unimplemented functions:
astar, calculate_distance, and
calculate_incorrect. A* is foundational search in
artificial intelligence. Like best-first search, A* uses a priority
queue to select which state to explore next. This queue is ordered
according to the function f(x) = g(x) + h(x),
where g(x) is the
cost of the path and h(x) is a heuristic
function. Best-first search is essentially A* where h(x) = 0.
In the astar function, implement best-first search. The cost of moving any one block is 1. You may use the bfs function as inspiration. The initial state of your frontier should be the following:
frontier = [(puzzle.state(), 0, [])]
The first value is the state, the second is the cost, and the third is the path. To sort the frontier at any time, you can use the following line of code:
frontier.sort(key=lambda x: x[1])
Now, run your search with the following command:
python3 hw-1-starter.py --search astar
If you are using the initial state
[[3,5,1],[7,0,6],[4,8,2]], it should have solved the puzzle
in 14 moves and should have visited over 8000 states. Now, let’s augment
our function to run A* instead of best first search. First, we are going
to have to implement our heuristic functions. One heuristic for the tile
game is number of tiles in the wrong place. Simply count how many tiles
are not in the appropriate place. For example the following has an
heuristic value of 2 because 3 and 4 are in the incorrect place.
Grid:
3 1 2
4 . 5
6 7 8In the calculate_incorrect function, implement the
incorrect placement heuristic described above. In the astar
function, calculate the heuristic value using this function. Calculate
the cost of a move as
(length of path) + (heuristic value).
If you run the search with A* now, you should see the number of visited states has gone down significantly.
This is a fine heuristic, but we can be better. One that comes to mind is distance from correct. For each number, add how many rows and columns it is from its correct position. Add these, and you have the heuristic. This is called taxicab distance or Manhattan distance. From the below example, the heuristic value is 6.
Grid:
3 1 8
4 . 5
6 7 2The number three needs to go down one row, the number 4 needs to go over 1 column, the number 8 needs to go down to rows, and the number 2 needs to go up 2 rows.
In the calculate_distance function, implement the
distance from correct heuristic described above. In the
astar function, calculate the heuristic value using this
function. Calculate the cost of a move as
(length of path) + (heuristic value).
If you run the search with A* now, you should see the number of visited has gone down even more! Let’s allow users to select their heuristic:
In the astar function, use the
heuristic input variable to select which heuristic which to
use. If it is equal to inc, use the incorrect distance
heuristic. Otherwise, use the distance-from-correct heuristic.
To run the search with the incorrect placement heuristic, run the following command:
python3 hw-1.py --search astar --heuristic inc
To run the search with the distance from correct heuristic, run the following command:
python3 hw-1.py --search astar --heuristic dist
Lastly, let’s implement weighted A*:
In the astar function, use the weight input variable to
weight the heuristic values. Essentially, you are changing the formula
from f(x) = g(x) + h(x)
to f(x) = g(x) + w * h(x)
where w is the weight
value.
Run the search with various weight values to see how it affects the search’s performance. It’s possible it will produce a suboptimal solution in terms of steps.
In your writeup file, answer the following questions:
Breadth first search is equivalent to best-first search when the cost of all actions are equivalent. Explain why.
For the tile game, is the heuristic of tiles incorrectly placed an admissible heuristic? If yes, why?
For the tile game, is the heuristic of Manhattan distance an admissible heuristic? If yes, why?
Of the two tile game heuristics we implemented, which do you think is better? Why?
Use the following game starting state:
[[3, 5, 1], [7, 0, 6], [4, 8, 2]]. Run A* with various
weights on this starting state using both heuristics. List the weights,
number of moves, and number of visits. Which weight is best for each
heuristic? Why?
Once you have finished, make sure to push your code and write-up to CSGit!