christianix.de

-> Main -> GWT Tutorial -> PuzzleBoard.java

package de.christianix.puzzle.client;

import java.util.Arrays;
import com.google.gwt.user.client.Random;

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

    /**
     * Construct puzzle board.
     *
     * @param ydim y dimension
     * @param xdim x dimension
     */
    public PuzzleBoard( int ydim, int xdim ) {
        rowSize = xdim;
        board = new int[ydim * xdim];
        init();
    }

    /**
     * Initialize with permutation.
     * The Fisher–Yates shuffle is used to generate the permutations.
     */
    public void init() {
        board[0] = 0;
        int pc = 0;

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

            /* Check if puzzle is solvable */
            pc = permutationCount();
            if ( (pc % 2) != 0 ) {
                switchTiles(0, 1);
            }
        } while ( pc == 0 );

        emptyPos = board.length-1;
        board[emptyPos] = -1;
    }

    /**
     * Get index of tile at give position.
     *
     * @param y coordinate
     * @param x coordinate
     * @return tile index
     */
    public int getTileIndex( int y, int x ) {
        int i = (y * rowSize) + x;
        return board[i];
    }

    /**
     * Get x coordinate of empty tile.
     *
     * @return x coordinate
     */
    public int getEmptyX() {
        return (emptyPos % rowSize);
    }

    /**
     * Get y coordinate of empty tile.
     *
     * @return y coordinate
     */
    public int getEmptyY() {
        return (emptyPos / rowSize);
    }

    /**
     * Count permutations of board.
     * Two tiles x and y are permuted if x < y but index(x) > index(y).
     *
     * @return number of permutations
     */
    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;
    }

    /**
     * Move tile if allowed.
     * Movement of a tile is only allowed if the empty tile is in the
     * neighborhood.
     *
     * @param x coordinate
     * @param y coordinate
     * @return true if move was allowed, false otherwise
     */
    public boolean moveTile( int x, int y ) {
        int i = (y * rowSize) + x;

        /* Check if movable */
        if ( (i+1 == emptyPos) ||
             (i-1 == emptyPos) ||
             (i+rowSize == emptyPos) ||
             (i-rowSize == emptyPos) )
        {
            board[emptyPos] = board[i];
            emptyPos = i;
            board[emptyPos] = -1;
            return true;
        }

        return false;
    }

    /**
     * Debug method
     */
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append( Arrays.toString(board) ).append( "\n" );
        return builder.toString();
    }

    /**
     * Switch tiles.
     * Uses arithmetics only.
     *
     * @param i first index
     * @param j second index
     */
    protected void switchTiles( int i, int j ) {
        board[j] += board[i];
        board[i] = board[j] - board[i];
        board[j] -= board[i];
    }
}

syntax highlighted by Code2HTML, v. 0.9.1