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 for this website. 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

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.