[2] Sliding Puzzle

Introduction

We are going to implement a 4×4 sliding puzzle. The implementation is very similar to the game of Klotski.

The Puzzle

sample_puzzle

The Solution

solution

Cell Coordinates System

xy

List of Block

Note that the block at (0,0) is missing.
    static UnitBlock[] blocks = new UnitBlock[] {
      new UnitBlock(1,0,Color.WHITE,imageList[1]),
      new UnitBlock(2,0,Color.WHITE,imageList[2]),
      new UnitBlock(3,0,Color.WHITE,imageList[3]),
      new UnitBlock(0,1,Color.WHITE,imageList[4]),
      new UnitBlock(1,1,Color.WHITE,imageList[5]),
      new UnitBlock(2,1,Color.WHITE,imageList[6]),
      new UnitBlock(3,1,Color.WHITE,imageList[7]),
      new UnitBlock(0,2,Color.WHITE,imageList[8]),
      new UnitBlock(1,2,Color.WHITE,imageList[9]),
      new UnitBlock(2,2,Color.WHITE,imageList[10]),
      new UnitBlock(3,2,Color.WHITE,imageList[11]),
      new UnitBlock(0,3,Color.WHITE,imageList[12]),
      new UnitBlock(1,3,Color.WHITE,imageList[13]),
      new UnitBlock(2,3,Color.WHITE,imageList[14]),
      new UnitBlock(3,3,Color.WHITE,imageList[15]),
    };

Dividing the Image

First we load the whole image file mona.png.
        image=ImageIO.read(new java.io.File("mona.png"));
        int imageW=image.getWidth(null);
        int imageH=image.getHeight(null);
where mona.png is tbe image below: mona

The image dimension is 400×400 pixels. To divide it into 16 pieces, the dimension of each sub-image is 100×100. The bounding region of the upper left sub-image is (0,0,100,100). The bounding region of the lower right sub-image is (300,300,400,400). A picture worth a thousand words: region
Referring to our cell coordinate system. If (x,y) is the cell coordinates, then the image region of the cell is:
(x*100,y*100, x*100+100, y*100+100)
or to be more generic :
(x*imageW/4,y*imageH/4, x*imageW/4+imageW/4, y*imageH/4+imageH/4)
And this explains half of the parameters in BlockList.java
    static BufferedImage[] initImageList()
    {
      try {
        imageList = new BufferedImage[16];
        image=ImageIO.read(new java.io.File("mona.png"));
        int imageW=image.getWidth(null);
        int imageH=image.getHeight(null);
        for (int i=0;i<16;i++)
        {
          imageList[i]=new BufferedImage(Cell.W,Cell.H,BufferedImage.TYPE_INT_ARGB);
          int x=i % 4;
          int y=i / 4;
          imageList[i].getGraphics().drawImage(
            image,2,2,Cell.W-4,Cell.H-4,
            x*imageW/4,y*imageH/4, x*imageW/4+imageW/4, y*imageH/4+imageH/4,null);
        }
      } catch (Exception e)
      {
        String message="Error Reading File";
        javax.swing.JOptionPane.showMessageDialog(null, message);
        e.printStackTrace();
        System.exit(1);
      }
      return imageList;
    }
 

Image Scaling

The dimension of every cell is 80×80 pixels. This is defined in Cell.java.
class Cell
{
  static final int W=80;
  static final int H=80;
}
If we want to copy the lower right region of the source image (mona.png) to one of the cell image, we may use the following parameters:
// copy a region of the source image(mona.png) to cell image
// the image will be scaled down from 100x100 to 80x80 pixels
          cellImage.getGraphics().drawImage(
            sourceImage,0,0,80,80,
            300,300, 400, 400,null);
Since our cell has a border, we reserve two pixels on every side. Hence the parameters become:
// copy a region of the source image(mona.png) to cell image
          cellImage.getGraphics().drawImage(
            sourceImage,2,2,76,76,
            300,300, 400, 400,null);
To be more generic, we write:
// copy a region of the source image(mona.png) to cell image
          imageList[i].getGraphics().drawImage(
            image,2,2,Cell.W-2,Cell.H-2,
            x*imageW/4,y*imageH/4, x*imageW/4+imageW/4, y*imageH/4+imageH/4,null);
And those are exactly the parameters used in initImageList() inside BlockList.java  

Reusing Object

We have written a Block object that supports drag and drop functions in the game of Klotski. We may reuse Block.java. However, in Klotski, every block may occupy 1 to 4 cells, whereas the block in the sliding puzzle may occupy only 1 cell. Hence we create a UnitBlock class that is a child class of Block. As the name suggest, a UnitBlock is just a Block that always occupy one cell.
class UnitBlock extends Block
{
  public UnitBlock(int x,int y, Color color,BufferedImage image)
  {
    // note that the width and height are always 1
    // hence we pass (1,1) as (W,H) to the parent constructor
    super(x,y,1,1,color);
    this.image = image;
    javax.swing.ImageIcon icon=new javax.swing.ImageIcon(image);
    JLabel imageLabel = new JLabel(icon);
    imageLabel.setBounds(0,0,Cell.W,Cell.H);
    this.setLayout(null);
    this.add(imageLabel);
  }
}
Note also that every UnitBlock is associated with a BufferImage, which is one of the 16 sub-images created in initImageList().

Checking for Solution

Just like the game of Klotski, we check the solution whenever a move is completed. Hence we override the mouseRelease() function inside UnitBlock.
class UnitBlock extends Block
{
// ...
// ... other functions omitted
// ...
  @Override // MouseListener
  public void mouseReleased(MouseEvent e) 
  {
    super.mouseReleased(e);

    boolean solved=true;
    for (UnitBlock block : BlockList.blocks)
    {
      int j=block.getY()/Cell.H*Board.W+block.getX()/Cell.W;
      if (block.image!=BlockList.imageList[j]) solved=false;
    }

    if (solved)
    {
      BlockList.congratulations();
    }
  }
}

Brief Explanation of Solution Checking

For every block, we can get the cell coordinates using the following formula :
   x = block.getX()/80;  // result: 0 to 3
   y = block.getY()/80;  // result: 0 to 3
Since our cells are arranged in row major order, hence an index can be calculated as follows:
   j = y*4 + x;
Or to be more generic,
      int j=block.getY()/Cell.H*Board.W+block.getX()/Cell.W;
if every cell is in the correct position, then for every block, the following condition should be true:
  (block.image==BlockList.imageList[j])
And that explains the source code in mouseReleased().

Compile and Run

Please visit the source code page. You will need the following files :
  1. UnitBlock.java A child class of Block which occupies exactly 1 cell.
  2. Board.java Define the board size of the game.
  3. Cell.java Define the width and height of a cell in pixels
  4. BlockList.java Define the initial layout of the game
  5. Block.java Define a block object which implements the drag and drop function
  6. Main.java Program entry point
Previous Entries [4] Dot Matrix