Tuesday, October 6, 2009

Homework 5: The Fifteen Puzzle

In the fifteen puzzle you are given a board with embedded tiles, numbered 1 to 15, which can only be moved up, down, left, or right to occupy the one blank spot. That is, you can only move a tile that is a neighbor of the blank spot. Another way of looking at it is to say that you can only move the blank spot up, down, left or right, exchanging it with the tile that is already in that position.

For this homework you will implement a FifteenPuzzle class that has the following methods:

  1. A constructor that initializes the board to the solved position, with the blank on the bottom left, as shown in the figure.
  2. A toString() method which prints a pretty board, like the ones shown below.
  3. The methods moveUp, moveDown, moveLeft, and moveRight which move the empty space up, down, left, and right, respectively. The functions should do nothing if called with a board configuration that would make it impossible to execute the action. For example, if the space is in the bottom right and we ask it to moveDown it should stay there. The program should not crash.
  4. The method isWinner which returns true if the board is in its initial configuration.

You will also implement a main function that asks the user which way he would like to move the tile and then performs the move, by calling one of the moveX methods, and displays the new board. Below is a sample interaction with the program:

 1  2  3  4 
 5  6  7  8 
 9 10 11 12 
13 14 15    

Enter command or 'done' to finish
Enter command (u,d,l,r):u
 1  2  3  4 
 5  6  7  8 
 9 10 11    
13 14 15 12 

Enter command (u,d,l,r):r
 1  2  3  4 
 5  6  7  8 
 9 10 11    
13 14 15 12 

Enter command (u,d,l,r):l
 1  2  3  4 
 5  6  7  8 
 9 10    11 
13 14 15 12 

Enter command (u,d,l,r):r
 1  2  3  4 
 5  6  7  8 
 9 10 11    
13 14 15 12 

Enter command (u,d,l,r):d
 1  2  3  4 
 5  6  7  8 
 9 10 11 12 
13 14 15    

WINNING BOARD!!

Enter command (u,d,l,r):l
 1  2  3  4 
 5  6  7  8 
 9 10 11 12 
13 14    15 

Enter command (u,d,l,r):l
 1  2  3  4 
 5  6  7  8 
 9 10 11 12 
13    14 15 

Enter command (u,d,l,r):u
 1  2  3  4 
 5  6  7  8 
 9    11 12 
13 10 14 15 

Enter command (u,d,l,r):u
 1  2  3  4 
 5     7  8 
 9  6 11 12 
13 10 14 15 

Enter command (u,d,l,r):r
 1  2  3  4 
 5  7     8 
 9  6 11 12 
13 10 14 15 

Enter command (u,d,l,r):d
 1  2  3  4 
 5  7 11  8 
 9  6    12 
13 10 14 15 

Enter command (u,d,l,r):done

You must use a 2-dimensional array to implement the board. This homework is due by Thursday, October 15 @ noon.

Tip: To turn an integer into a string that is padded on the left with enough spaces to ensure it is of length at least 3, use String iAsPaddedString = String.format("%3d",i); where i is the integer.

For hackers only: write a method that solves the puzzle. A good way to do it is using the A-star algorithm. You will learn all about this and other search algorithms if you take our Artificial Intelligence class (CSCE 580)

No comments: