CISC 481 - How to solve 8 Puzzle problems using BFS and DFS in Python

Assignment Task

Objectives

After completing this assignment, you’ll understand the inner workings of the following search algorithms:

• Lterative-deepening search
• Breadth-first search
• A search You’ll also gain some experience using a software profiler, which is a tool that lets you gather and analyze performance characteristics of your code. You’ll use the statistics you gather to see in a very real sense the difference in time and space complexity of the above algorithms.

The n-Puzzle

This is a classic problem studied in Artificial Intelligence. You have a m × m grid of numbered tiles 1, 2, 3, . . . , m2 − 1 and one blank space. The blank space allows tiles to be slid around on the board, and the goal is to slide the tiles into some particular configuration (usually in numerical order from left to right, top to bottom). For the project, we’ll be dealing with the 8-puzzle, which has 8 numerical tiles on a 3x3 grid. See Figure 1 from Russell & Norvig for a graphical depiction of the puzzle.

Representing the Problem

[My examples here are in Lisp, but feel free to use something similar that’s easy to parse in your target language.] Probably the most straightforward way to represent an 8 puzzle board is as a 3 × 3 array of the numbers 1 to 8 and nil (for representing the blank). In Figures 2, 3, and 4 I give some names to a few initial states that I’ll refer to throughout the writeup.

Rules of Movement (Actions)

A tile in an n-puzzle can only move orthogonally (that is, it can move horizontally or vertically), and it can only move into the blank square. As such, the components of an action are are a direction which can be one of up, down, left, or right; and a row and column specifying the 2 location of a tile to be moved in direction. If the neighboring element in direction of location (row, column) is nil, then performing the action causes (row, column) to swap values with that neighbor. Otherwise, the action is invalid. All actions have a path cost of 1.

Part

1. Write a function possible-actions that takes a board as input and outputs a list of all actions possible on the given board.1

2. Write a function result that takes as input an action and a board and outputs the new board that will result after actually carrying out the input move in the input state. Be certain that you do not accidentally modify the input board variable.

3. Write a function expand that takes a board as input, and outputs a list of all states that can be reached in one Action from the given state.

4. Implement an iterative deepening search which takes an initial board and a goal board and produces a list of actions that form an optimal path from the initial board to the goal. Test your search on *puzzle-0*. You can try running it on some of the other puzzles, but don’t feel discouraged if it takes a very long time before returning an answer.

5. Implement a breadth-first search which, like the iterative deepening search, takes an initial board and a goal and gives an optimal sequence of actions from the initial state to the goal. Test your search on *puzzle-0* and *puzzle-1*.

6.  For this part, you’ll be implementing A* search.

6.1. Similar to breadth-first and iterative deepening, your A search should take as input an initial board and a goal board. It should additionally take a heuristic function4

You can test your code by passing as the heuristic a function that always returns 0 5 , which should reduce your search to uniform-cost search. Test it on puzzle-0. It may take a long time to solve any of the others.

6.2. Now you’ll implement the two classic n puzzle heuristic functions - number of misplaced tiles and Manhattan distance. Test your code with both of these on puzzle-0 and puzzle-1. You’ll probably notice that you have to wait some time (but hopefully not as long as with (constantly 0)!) to get back an answer when using the misplaced tiles heuristic. This illustrates very clearly just how much choosing a good heuristic matters for the practicality of A search.

7. In this final part, you’ll be benchmarking your searches to get an empirical sense of the differences in time/space complexity between them. For this you’ll need a profiler. NB that some profilers also include memory usage statistics, which may give a good idea about the maximum amount of memory used at any point on a given run. If the profiler for your language does not include this, you’ll have to instrument your code to keep track of the maximum number of nodes on the frontier at any one time over the entire run. In Figures 5 and 6 I list what I get when profiling runs of my reference implementations of breadth-first and A* search. This output was generated using SBCL’s profiler. SBCL is the Common Lisp implementation that I use. Like most of Common Lisp tooling, the profiler is easily accessible using SLIME in Emacs

What we’re interested in here is ”consed” (which is a good proxy for the total amount of memory used) and the number of calls we made to expand. The former gives us an idea of the space complexity, and the latter the time complexity. Note that A* performs orders of magnitude better than breadth-first on both counts! You can also see that A* is better in terms of actual time - taking less than half a second to complete where breadth-first takes over four seconds.

7.1. Profile each of iterative deepening search, breadth-first search, and A* search using Manhattan distance solving puzzle-0. Even on this simple puzzle solvable in only 6 moves, you should be able to get a sense of the difference in performance characteristics between these three algorithms.

7.2. Just to drive the point home about choosing a good heuristic, profile A* on *puzzle-2* once using the number of misplaced tiles, and then once using the Manhattan distance

This CISC 481 - IT Computer Science has been solved by our PhD Experts at My Uni Paper.