christianix.de

-> Main -> GWT Tutorial

Introduction

The Google Web Toolkit (GWT) provides tools for writing web applications purely in Java. The Java code of the front-end is then translated to Java Script. GWT takes care of all the browser quirks, so you don't need to care about those.

This tutorial describes how I implemented the 15 puzzle on My Prague site. Only front-end code is required for this. You should have read through some beginner tutorial already, because I'll mainly focus on the mathematics and how things work together.

Mathematics

First you have to shuffle the board. The probably fasted way to create a permutation of the sequenced board is the Fisher–Yates shuffle:

	for ( int i = 1; i < board.length-1; ++i ) {
		int j = Random.nextInt(i+1);
		board[i] = board[j];
		board[j] = i;
	}
	

But not every permutation is solvable! A puzzle is only solvable if

N = Number permutations + Row of empty tile

has same parity (equal or unequal) than resolved puzzle. Our resolved puzzle has 0 permutations and the empty tile is in the bottom right corner of 3 rows: N = 0 + 3 = 3. Hence, the parity must be unequal.

However, we can simplify the equation, because the empty tile will be in the bottom right corner after we shuffled the board. So we just need to check that the parity of the number of permutations is equal. Since 0 is an equal number, we require an equal number of permutations on our initial board.
If the current permutation isn't solvable, I just switch the first with the second tile. This creates an equal parity again.

	pc = permutationCount();
	if ( (pc % 2) != 0 ) {
		switchTiles(0, 1);
	}
	

Permutations are counted by finding all tiles which are out-of-sequence. That is, for each tile we count the number of following tiles with a smaller number:

	public int permutationCount() {
		int cnt = 0;

		for ( int i = 0; i < (board.length - 1); ++i ) {
			for ( int j = i + 1; j < board.length; ++j ) {
				if ( (board[i] > board[j]) && (board[j] != -1) ) ++cnt;
			}
		}

		return cnt;
	}
	

There is a small chance that the shuffle process created the original picture with 0 permutations. In that rare case, I just run the shuffling process again. With a very small chance, this would result in many iterations. But it won't ever be an infinite loop.

	do {...} while ( pc == 0 );
	
PuzzleBoard

The class PuzzleBoard implements our model of the puzzle:

	public class PuzzleBoard {
		private int board[] = null;
		private int rowSize = 0;
		private int emptyPos = 0;

		public PuzzleBoard( int ydim, int xdim ) ;

		public void init() ;
		public int getTileIndex( int y, int x ) ;
		public int getEmptyX() ;
		public int getEmptyY() ;
		public int permutationCount() ;
		public boolean moveTile( int x, int y ) ;

		@Override
		public String toString() ;

		protected void switchTiles( int i, int j ) ;
	}
	

It contains methods to create permutations, model movement and map a 2D position into a tile index.

Constructor
Reserves memory for the board and initialises it.
init
Creates the permutation of the board.
getTileIndex
Get sequential index of tile at 2D position
getEmptyX / getEmptyY
Get x/y position of empty tile.
moveTile
Switch position with empty tile in neighbourhood. Which is only possible if the empty tile is in the neighbourhood.
toString
This is a debug method which creates a String representation of the board.
switchTiles
Internal function to switch tiles. For the pure fun of it, swapping is done without helper variable:
board[j] += board[i];
board[i] = board[j] - board[i];
board[j] -= board[i];

WebPuzzle

The class WebPuzzle implements the user interface and is the entry point of the web application:

	public class WebPuzzle implements ClickHandler, EntryPoint {

		private static final String DEFAULT_IMAGE_DIR = "images";
		private static final String IMAGE_BASE_NAME = "tile";
		private static final int XDIM = 6;
		private static final int YDIM = 3;

		private static DialogBox msgbox = null;
		private static Button msgbutton = null;
		private VerticalPanel mainPanel = null;
		private Grid puzzleGrid = null;

		private PuzzleBoard puzzleBoard = null;
		private Image tiles[] = null;

		public void onModuleLoad() ;

		protected void loadTiles() ;

		protected void placeTiles() ;

		private void move( int fromX, int fromY, int toX, int toY ) ;

		@Override
		public void onClick( ClickEvent event ) ;
	}
	

Class WebPuzzle implements the entry point onModuleLoad() for the web application. The entry points sets up the user interface, instantiates the model of the puzzle board and loads the images of the shuffled tiles.
Tiles are classes of type com.google.gwt.user.client.ui.Image . The tiles are placed in a com.google.gwt.user.client.ui.Grid .

Further more WebPuzzle implements the handler onClick(ClickEvent event) for mouse click events. The events are then resolved to the tile x where the click event came from. If the model was able to move x, it is swapped with the empty tile.

Verantwortlich/Responsible: Martin Christian (martin at christianix dot de)