CS461-Homework 2 Solved

In this homework, you’ll solve a variant of the 15-puzzle, something I would like to call the E15puzzle because it is easier to solve. (It is well-known that the 15-puzzle is difficult to solve; Wikipedia notes that lengths of optimal solutions can be as large as 80 moves.) The first figure below is the goal state for the (classical) 15-puzzle. The second figure below is the goal state for the E15-puzzle. It is clear that due to the repeated tiles, the E15-puzzle should take fewer moves to solve in general.  

  

15-puzzle (goal state) 

 

 

1 
2 
3 
4 
2 
3 
4 
5 
3 
4 
5 
5 
4 
5 
5 
 
 

E15-puzzle (goal state)

(colors are just to emphasize the duplicate tiles)

 

Now implement the A* search algorithm (no other algorithm is acceptable) and use it to solve a given instance of the E15-puzzle optimally, that is, with a minimum number of moves. (Winston covers A* in chapter 5. It is up to you to add the dynamic programming part; no points will be deducted for lack of it. On the other hand, you must definitely implement loopchecking.)

As you know, A* requires admissible heuristics. The following are used in solving the 15-puzzle and with some modifications (if necessary) should work for the E15-puzzle, too. The admissibility proofs given below within parentheses are for the 15-puzzle though.

•        h1: number of misplaced tiles

(h1 is an admissible heuristic for the 15-puzzle, since every tile that is out of position must be moved at least once.)

•        h2: sum of Manhattan distances of the tiles from their proper positions

(h2 is an admissible heuristic for 15-puzzle, since in every move, one tile can only move closer to its goal by one step and the Manhattan distance is never greater than the number of steps required to move a tile to its proper position.)

Here’s what you should do:

•        Write a ‘puzzle generator’ first. Starting from the goal state of the E15-puzzle (cf.

preceding figure), the generator returns a reasonably garbled initial state (S) by randomly shuffling the puzzle 10 times. This means that starting with the goal state, you ‘move’ the blank tile (up, down, left, or right) 10 times in succession, each move being decided by a call to a pseudo-random number generator. Notice that the puzzle generator thus guarantees that this (initial state) S will be solvable.

•        Run your generator as many times as necessary to obtain a dozen distinct initial states of the E15-puzzle. For the benefit of a reader (e.g., our TAs), clearly print these states and give them names, viz. S1, S2, …, S12.

•        Solve each Si, where i is between 1 and 12, via A*. In your A* implementation, you’ll use admissible heuristics similar to h1 or h2 (see presently).