[1] Klotski

Introduction

Klotski is a sliding block puzzle. The aim of the game is to move the red block to the bottom. The initial layout of the puzzle is as follows: klotski

Data Structure

The blocks are of different size. The biggest block is occupying 4 cells. The smallest block is occupying one cell. Let’s divide the screen into twenty cells using the coordinate system as follows : xy The red block is occupying 4 cells. The upper left coordinates are (1,0) and the width and height are both 2 cells. We may represent this block as :
new Block(1,0,2,2,Color.RED);
Similarly, we may define every block in the initial layout as:
    static Block[] blocks = new Block[] {
      new Block(1,0,2,2,Color.RED),
      new Block(0,0,1,2,Color.GREEN),
      new Block(0,2,1,2,Color.GREEN),
      new Block(3,0,1,2,Color.GREEN),
      new Block(3,2,1,2,Color.GREEN),
      new Block(1,2,2,1,Color.YELLOW),
      new Block(1,3,1,1,Color.CYAN),
      new Block(2,3,1,1,Color.CYAN),
      new Block(0,4,1,1,Color.CYAN),
      new Block(3,4,1,1,Color.CYAN)
    };

The above array is defined in BlockList.java

User Interface

For a sliding puzzle like Klotski, drag and drop is a good choice for user interface. Click here for a simple example of drag and drop.

Drag and Drop Implementation

We would need to implement
  1. mousePressed() and mouseReleased() in the MouseListener interface.
  2. mouseDragged() in the MouseMotionListener interface.
The source code of the above functions are inside Block.java
  1. Inside mousePressed(), the mouse position is saved. This is the starting point of the drag action.
  2. Inside mouseDragged(), a displacement vector is calculated from the starting point saved above to the current mouse position. This displacement vector is added to the dragged object
  3. Inside mouseReleased(), the object is dropped. That means a move has been made. It is a good place to check whether the puzzle is solved
Before looking at the advance implementation of drag and drop in Block.java, you are advised to read the simple version first.

Checking for solution

The puzzle is solved only if the red block is moved to position (1,3). How do we know the previously moved block is the red block ? We may check for the color :
  if (this.getColor()==Color.RED)
  { 
    // this is the red block
  }
Or we may check for the size (this is the actual implementation in Block.java):
    if (this.getWidth()==Cell.W*2 && this.getHeight()==Cell.H*2)
    {
      // this is the red block (because it occupies 4 cells)
    }
If the last moved block is the red block, we will need to check whether its position is (1,3). Note that (1,3) is the coordinates in cells. So the coordinates in pixels is (1*Cell.W, 3*Cell.H). Hence the actual source code to check for solution is:
    if (this.getWidth()==Cell.W*2 && this.getHeight()==Cell.H*2
       && this.getX()==Cell.W && this.getY()==Cell.H*3)
    {
      // Congratulations ! You have solved the puzzle !
    }


Hint for solution

To solve the puzzle, the minimum number of moves is 81, which is verified by computer to be the absolute minimum for the default starting layout, if you consider sliding a piece two positions in the same direction to be a single move.
If you found the puzzle difficult to solve, the following are some intermediate milestones for solving the puzzles. hint

Compile and Run

Please visit the source code page. You will need the following files :
  1. Board.java Define the board size of the game.
  2. Cell.java Define the width and height of a cell in pixels
  3. BlockList.java Define the initial layout of the game
  4. Block.java Define a block object which implements the drag and drop function
  5. Main.java Program entry point
Next Entries [2] Space Invader