CS 151 Assignment 3 — The Sliding-Blocks Puzzle

Introduction

In this assignment you will apply state space search to the infamous sliding-blocks puzzle. This puzzle consists of a 3 × 3 board with eight numbered tiles and a blank space. A tile adjacent to the blank space can slide into the space. The object is to figure out the steps needed to unscramble the tiles to reach the goal configuration.

For this problem, a state should specify the configuration of the eight tiles and the blank space on the board. The operators are most easily represented as moving the blank up, down, left, or right, rather than creating operators for each of the numbered tiles.

For example, suppose we wanted to get from the start state to the goal state given below:

  1 2 3     1 2 3
  8   6     8   4
  7 5 4     7 6 5

  Start     Goal

   1 2 3   RIGHT   1 2 3   DOWN   1 2 3   LEFT   1 2 3    UP    1 2 3
   8   6    --->   8 6     --->   8 6 4   --->   8 6 4   --->   8   4
   7 5 4           7 5 4          7 5            7   5          7 6 5

Part 1: Uninformed Search

1. Write an EightPuzzleState class that implements states and operators for the 8-puzzle. Your code should work with Search.py and Queues.py from the last assignment. Your EightPuzzleState constructor should take the following nine parameters as input, in the order shown:

      nw    northwest element
      n     north element
      ne    northeast element
      w     west element
      c     central element
      e     east element
      sw    southwest element
      s     south element
      se    southeast element
   

   Values should be the numbers 1 through 8 for the puzzle pieces or a space character for the blank. For example, the above goal state would be created by calling:

      EightPuzzleState(1, 2, 3, 8, " ", 4, 7, 6, 5)
   

   You may represent 8-puzzle states internally however you like, but a simple list representation is probably easiest. If you choose this approach, you may find it useful to also keep track of the current position of the blank as an additional state variable.

   An 8-puzzle state should provide a method called applyOperators(), which returns a list of (state, action) pairs containing all of the valid states generated by applying the operators to the original state. Each action is a string describing the move that generated the associated state, and should be of the form "slide 3 to the left", "slide 8 up", etc.

   You should also define a __str__ method to use for printing states. Probably the most concise description is simply a picture of the board configuration, as in the above examples.

2. Modify the UninformedSearch function in Search.py so that it keeps track of the total number of nodes expanded and the total number of nodes generated during a search. Also, your program should impose a maximum limit of 3500 node expansions on any search, in order to prevent searches from taking too long.

3. Test your program on the following starting states A-E (each is progressively harder) using the same goal each time. To save you some typing, code for creating these states is available here.

     1 2 3    1 3      1 3 4    1 3      7 1 2    8 1 2
     8   4    8 2 4    8 6 2    4 2 5    8   3    7   4
     7 6 5    7 6 5      7 5    8 7 6    6 5 4    6 5 3
     goal       A        B        C        D        E
   

4. Make a table showing the length of the solution found by BreadthFirst, DepthFirst, and UniformCost on the above starting states, as well as the number of nodes expanded and generated. If the search is unsuccessful record that as well. Does changing the order in which the operators are applied in applyOperators() have any effect on the outcome of a search?

Part 2: A* Search

1. Using UninformedSearch as a guide, write a new search function called HeuristicSearch that takes an additional input parameter heuristic, which will be a heuristic function on puzzle states. This function should take a state and a goal as input, and compute an estimate of the number of moves required to get from the state to the goal. You will also need to modify nodes so that they keep track of heuristic values in addition to path costs. Greedy search and A* search can then be implemented as shown below:

   def Greedy(initialState, goalState, heuristic):
       fringe = PriorityQueue(lambda node: node.h)
       HeuristicSearch(initialState, goalState, fringe, heuristic)
   
   def Astar(initialState, goalState, heuristic):
       fringe = PriorityQueue(lambda node: node.g + node.h)
       HeuristicSearch(initialState, goalState, fringe, heuristic)
   

2. Implement the three heuristic functions we discussed in class: (1) number of tiles out of place, (2) Manhattan distance, (3) Manhattan distance + twice the number of direct adjacent tile swaps needed. Call these functions h1, h2, and h3, respectively. They should each take a state and a goal as input parameters, as shown below:

   def h1(state, goal):
      ...
   

3. Test your program on the starting states A-E from Part 1, as well as states F-H below, using the same goal each time. Again, each test is progressively harder.

     1 2 3    2 6 3    7 3 4    7 4 5
     8   4    4   5    6 1 5    6   3
     7 6 5    1 8 7    8   2    8 1 2
     goal       F        G        H
   

4. Make a table showing how many nodes are expanded and generated by A* search using the three heuristic functions h1, h2, and h3 on test cases F, G, and H. If the search is unsuccessful record that as well. Since h2 is more informed than h1, and h3 is more informed than h2 (that is, h1(S, G) < h2(S, G) < h3(S, G) for all states S and G), we would expect A* to expand fewer nodes when using h2, and even fewer when using h3. Do your results support this?

   Also compute the effective branching factor b* for each run and include it in your table. This is simply the number of nodes generated during a search (not counting the root) divided by the number of nodes expanded. The better your heuristic, the lower the branching factor will be.

Part 3: Extra Credit Challenge

Now use your A* search engine to solve a variant of the sliding-blocks puzzle in which there are nine blocks of different sizes, as well as two independent spaces, as shown below:

You will need to define a new board representation, new state operators, and a new heuristic evaluation function for the 9-puzzle, but you shouldn't need to modify your search engine. You will probably also need to come up with a different way of printing puzzle states.

For testing purposes, define three start states and three goal states of your choosing. Call these states startA9, startB9, startC9, goalA9, goalB9, and goalC9. Call your heuristic function h9. To solve the 9-puzzle, simply invoke A* with the appropriate states and heuristic function:

   Astar(startA9, goalA9, h9)

Turning in your homework

Files to submit:

• Search.py
• EightPuzzleState.py
• NinePuzzleState.py (extra credit)