CSCI 121 Programming Assignment 2

Topic:  The 8 puzzle

 

In this assignment you will implement the 8 puzzle, a 3 x 3 grid with 8 tiles, numbered 1 through 8, that can be moved into various configurations.  Here is one possible configuration:

 

 

Solving the 8 puzzle involves moving the tiles until a particular goal configuration is achieved.  A common goal configuration is:

 

 

One sequence of moves that transforms the start puzzle given above to the goal is:

 

1

2

3

4

5

 

 

 

 

 

6

7

8

9

10

 

 

 

 

 

 

11

12

13

14

 

 

Your program should do the following things:

 

·        Generate an initial puzzle configuration.  To do this, start with the goal configuration and make some number of random moves.

·        Display the puzzle in a frame with a 3 x 3 GridLayout.

·        When a mouse click occurs on a movable tile, make the indicated move.

·        When the goal configuration is reached, use JOptionPane.showMessageDialog() to announce that the goal has been reached:

 

         

 

Representing a tile

 

A bordered JLabel can be used to make a nice-looking tile.  To make a tile with a magenta background and label of “5” we could use the following code:

 

JLabel tile = new JLabel(“6”);

tile.setHorizontalAlignment(JLabel.CENTER);

tile.setFont(whatever_font_you_prefer);

tile.setOpaque(true);

tile.setBackground(Color.MAGENTA);

tile.setBorder(etchedBorder);

 

To register the application as the mouse listener for the tile, we would use the code:

 

tile.addMouseListener(this);

 

Now, whenever a mouse event occurs over this tile, the mouse listener will be notified.

 

Since we need 9 tiles, including the “blank” tile, an array of JLabels makes sense:

 

private JLabel[] tile;

private String[] label = {“1”, “2”, “3”, “4”, “”, “5”, “6”, “7”, “8”};

 

The constructor can create the array of tiles and initialize them appropriately (think for loop).  The numbered tiles should all have the same background color.  The “blank” tile should have a different color to make it stand out.

 

Moving a tile

 

A tile is movable if the “blank tile” is immediately

·        to its left

·        to its right

·        above it

·        below it

 

For example, in the configuration

 

 

the movable tiles are tiles 3, 4, and 5.  To move a legal tile, say tile[ndx], you can do the following:

 

·        Find blankPos, the position (index) of the blank tile.  Use a loop to do this.

·        Exchange the labels of tile[ndx] and tile[blankPos].  Use getText() and setText() to do this.

·        Exchange the background colors of tile[ndx] and tile[blankPos].  Use getBackground() and setBackground() to do this.

 

The move method is basically a sort of “swap” routine:

 

private void swap(int ndx, int blankPos)
{

   /* precondition: tile[ndx] is movable */

 

   /* exchange the labels of tile[ndx] and tile[blankPos] */
   /* exchange the background colors of tile[ndx] and tile[blankPos] */
}

 

Generating a random puzzle

 

To generate a random starting configuration, it is useful to think of moving the blank tile randomly to the left, right, up, and down.

·        To move the blank tile (at array index blankPos) left, we simply swap it with the tile at position blankPos – 1:

 

swap(blankPos - 1, blankPos);

 

·        To move the blank tile right, we swap it with the tile at position blankPos + 1:

 

swap(blankPos + 1, blankPos);

 

·        To move the blank tile up, we swap it with the tile at position blankPos - 3:

 

swap(blankPos - 3, blankPos);

 

·        To move the blank tile down, we swap it with the tile at position blankPos + 3:

 

swap(blankPos + 3, blankPos);

 

To scramble the puzzle randomly, we use the Random class defined in java.util.Random.  Since we have 4 possible moves, we can generate a random value in the range 0 … 3 and make one of the moves based on the value of this number.  To generate a random number in this range, use the following code:

 

    Random rand = new Random();

    int whichMove;

    for (int i = 0; i < numberOfRandomMoves; i++) {

      whichMove = rand.nextInt(4);

      move (whichMove);

    }

 

In the code above, I am assuming you have a move method that moves the blank tile left, right, up, or down based on the value of whichMove.  The move method should check to make sure the requested move is legal; if so, it should call swap appropriately.

 

 

Outline of the program:

 

/*

   EightPuzzle.java

   Written by YourNameHere

*/

 

import java.awt.*;

import java.awt.event.*;

import javax.swing.*;

import javax.swing.border.*;

import java.util.Random;

 

public class EightPuzzle extends JFrame implements MouseListener

{

 

   /* class variable declarations */

 

 

   /* constructor */

 

 

   /* MouseListener methods:

 

   public void mouseClicked(MouseEvent e)
   {

      /* determine which tile was clicked and move it, if possible */
   }

 

   /* the other MouseListener methods can have empty bodies */

 

 

   /* utility methods (make them private) */

 

 

   public static void main(String[] args)
   {

      EightPuzzle puzzle = new EightPuzzle();

      puzzle.setVisible(true);

   }

}

 

 

Email a copy of EightPuzzle.java to mclark@wvutech.edu by 5:00 on the due date.  Hand in a printed listing of EightPuzzle.java in class.