Return to Revisions

Object-oriented design

There is more data being passed around than should be necessary with an object-oriented design.

You have ran (a Random object) and tileGrid (a 2-D matrix) as instance variables. I don't think that there's much point to keeping a Random object as part of the puzzle's state; it would only be useful in .shuffle(), so it could just be a local variable in .shuffle(). (There might be a case for supporting repeatable results if, for example, you wanted to run simulations. In that case, you could have the shuffle method accept a Random parameter instead.)

It looks like currTile isn't the position of a "current tile", but is actually the coordinates of the hole. I was, um, puzzled by that unclear naming. A clearer name could be hole. The position of the hole should be (a redundant) part of the object's state. You shouldn't have to pass it to moveTile(), nor should moveTile() need to return the new hole position. In particular, requiring the caller of the public method moveTile() to pass in the correct hole position is just asking for trouble.

Shuffling

Instead of hard-coding 1000, I suggest accepting a parameter for the number of moves to make.

The way you assume that the hole is initially at the bottom-left is problematic. What if .shuffle() is called when the hole is not where you expect?

You have nine cases, depending on the position of the hole: 4 corners, 4 edges, and the interior points. All of those cases have to have their ±1 logic consistently coded, and it's hard to check that you wrote all of those cases correctly.

In the cases where the hole is at the edge, there is a \$\frac{1}{2}\$ chance of moving the hole into the interior, a \$\frac{1}{6}\$ chance of moving it one way along the edge, and a \$\frac{1}{6}\$ chance of moving it the other way along the edge. I consider that to be a weird distribution — I would have expected equal odds.

Even weirder: a hole at the edge has a \$\frac{1}{6}\$ chance of not moving it at all, and if the hole is in the interior, there is a \$\frac{1}{9}\$ chance of not moving it at all. Those no-ops count as one of your 1000 moves, though!

A much simpler approach would be to pick one of the four cardinal directions and see whether that would result in a legal move. You would probably need to write that validation code elsewhere in the game anyway. There would then be no special cases in .shuffle() itself. The probabilities would all be equal. Sure, you might waste a few random numbers from the generator, but you're doing some of that already with the no-op moves.

Data representation

Passing a pair of numbers is awkward, especially since Java doesn't have a built-in Pair class, and you didn't write one. It would be nicer to be able to specify any position in the grid using a single number.

You could do that by linearizing the 2-D matrix into a 1-D array.

Suggested solution

import java.util.Random;

public class SlidingTilePuzzle {
    private int[] tiles = {
         1,  2,  3,  4,
         5,  6,  7,  8,
         9, 10, 11, 12,
        13, 14, 15,  0
    };
    private final int size;
    private int hole;                       // Index of the "0" tile

    public SlidingTilePuzzle() {
        this.size = (int)Math.sqrt(this.tiles.length);
        assert size * size == this.tiles.length;

        this.hole = this.tiles.length - 1;
        assert this.tiles[this.hole] == 0;
    }

    public void shuffle(int moves) {
        Random rand = new Random();
        int[] neighborOffsets = { -size, +size, -1, +1 }; // up down left right
        while (moves --> 0) {
            int neighbor;
            do {
                neighbor = this.hole + neighborOffsets[rand.nextInt(4)];
            } while (!this.canMove(neighbor));
            this.move(neighbor);
        }
    }

    /**
     * Tests whether a tile at the specified position can be moved into a
     * neighboring hole (i.e. whether the hole can be moved to the specified
     * position).
     */
    public boolean canMove(int pos) {
        if (pos < 0 || pos >= size * size) {
            return false;                   // No such position
        }
        int diff = this.hole - pos;
        if (diff == -1) {                   // Slide tile left (hole goes right)
            return pos % size != 0;         // ... unless tile is on left edge
        } else if (diff == +1) {            // Slide tile right (hole goes left)
            return this.hole % size != 0;   // ... unless hole is on left edge
        } else {
            return Math.abs(diff) == size;  // Slide vertically
        }
    }

    /**
     * Move the tile at the specified position into the neighboring hole (i.e.
     * move the hole to the specified position).
     */
    public void move(int pos) {
        if (!this.canMove(pos)) {
            throw new IllegalArgumentException("Illegal move");
        }
        assert this.tiles[this.hole] == 0;
        this.tiles[this.hole] = this.tiles[pos];
        this.tiles[this.hole = pos] = 0;
    }

    public int tileAt(int pos) {
        try {
            return this.tiles[pos];
        } catch (ArrayIndexOutOfBoundsException badPos) {            
            throw new IllegalArgumentException("No such position");
        }
    }

    public int getHole() {
        return this.hole;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder(size * size * 4);
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                int tile = this.tileAt(i * this.size + j);
                sb.append(String.format("%2s ", (tile == 0) ? "" : tile));
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    // Demonstration
    public static void main(String[] args) {
        SlidingTilePuzzle p = new SlidingTilePuzzle();
        for (int i = 0; i < 20; i++) {
            System.out.println(p);
            p.shuffle(1);
        }
    }
}