Logic for shuffling sliding puzzle

Question

I'm working on a sliding puzzle, one little project as a hobby, and yesterday I thought that instead of working on an algorithm to figure out a solved puzzle, it would be easier to make an algorithm that "shuffles" the tiles from a solved position. I came up with this and it works, but I don't know if it's elegant enough or it could be compressed into fewer lines of code because if I had to go back to it I think it could be tiresome.

public int[] moveTile(int clickedRow, int clickedCol, int x, int y) {
  // { ... moves the tile ... }
  return new int[]{clickedRow + y, clickedCol + x}; //returns new tile position on the grid
}

public void shuffle() {
  int[] currTile = {tileGrid.length - 1, 0}; // first move, to the right
  for (int i = 0; i < 1000; i++) { // it's set to 1000 for testing 
    if (currTile[0] == tileGrid.length - 1 && currTile[1] == tileGrid[0].length - 1) { // top right
      // can move left or down
      if (ran.nextBoolean()) {
        currTile = moveTile(currTile[0], currTile[1], 0, -1);
      } else {
        currTile = moveTile(currTile[0], currTile[1], -1, 0);
      }
    } else if (currTile[0] == 0 && currTile[1] == 0) { // bottom left
      // can move up or right
      if (ran.nextBoolean()) {
        currTile = moveTile(currTile[0], currTile[1], 0, 1);
      } else {
        currTile = moveTile(currTile[0], currTile[1], 1, 0);
      }
    } else if (currTile[0] == 0 && currTile[1] == tileGrid.length - 1) { // bottom right
      // can move up or left
      if (ran.nextBoolean()) {
        currTile = moveTile(currTile[0], currTile[1], -1, 0); // left
      } else {
        currTile = moveTile(currTile[0], currTile[1], 0, 1); // up
      }
    } else if (currTile[0] == 0 && currTile[1] > 0 && currTile[1] < tileGrid.length - 1) { // bottom row
      //can move up, left or right
      if (ran.nextBoolean()) {
        currTile = moveTile(currTile[0], currTile[1], 0, 1); // up
      } else {
        currTile = moveTile(currTile[0], currTile[1], ran.nextInt(1 + 1 + 1) - 1, 0); // left or right
      }
    } else if (currTile[0] == tileGrid.length - 1
                   && currTile[1] > 0 && currTile[1] < tileGrid.length - 1) { // top row
      //can move down, left or right
      if (ran.nextBoolean()) {
        currTile = moveTile(currTile[0], currTile[1], 0, -1); // down
      } else {
        currTile = moveTile(currTile[0], currTile[1], ran.nextInt(1 + 1 + 1) - 1, 0); // left or right
      }
    } else if (currTile[1] == 0
                   && currTile[0] > 0 && currTile[0] < tileGrid.length - 1) { // left column
      //can up down or right
      if (ran.nextBoolean()) {
        currTile = moveTile(currTile[0], currTile[1], 1, 0); // right
      } else {
        currTile = moveTile(currTile[0], currTile[1], 0, ran.nextInt(1 + 1 + 1) - 1); // up or down
      }
    } else if (currTile[1] == tileGrid.length - 1
                   && currTile[0] > 0 && currTile[0] < tileGrid.length - 1) { // right column
      //can move up or down or left
      if (ran.nextBoolean()) {
        currTile = moveTile(currTile[0], currTile[1], -1, 0); // left
      } else {
        currTile = moveTile(currTile[0], currTile[1], 0, ran.nextInt(1 + 1 + 1) - 1); // up or down
      }
    } else if (currTile[0] == tileGrid.length - 1 && currTile[1] == 0) {
      //can only move right or down
      if (ran.nextBoolean()) {
        currTile = moveTile(currTile[0], currTile[1], 1, 0);
      } else {
        currTile = moveTile(currTile[0], currTile[1], 0, -1);
      }
    } else if (currTile[0] == 0 && currTile[1] == tileGrid.length) {
      //can only move top or left
      if (ran.nextBoolean()) {
        currTile = moveTile(currTile[0], currTile[1], 0, 1);
      } else {
        currTile = moveTile(currTile[0], currTile[1], -1, 0);
      }
    } else {
      // can move in any direction
      if (ran.nextBoolean()) {
        currTile = moveTile(currTile[0], currTile[1], ran.nextInt(1 + 1 + 1) - 1, 0);
      } else {
        currTile = moveTile(currTile[0], currTile[1], 0, ran.nextInt(1 + 1 + 1) - 1);
      }
    }
  }
}

As clarification, currTile is the hole, swapping it with random tiles will shuffle the puzzle.

In the first state, currTile (hole) is in the top left of the grid: int[] currTile = {tileGrid.length - 1, 0};

tileGrid.length = amount of rows, -1 = top row, as top row = number of rows -1.

0 = col to the left.

Answer 1

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);
        }
    }
}

Answer 2

(Disclaimer: I'm not a Java-expert).

Moving the tile

You intentionally left this one as a black box, to keep it out of scope, I think, but I'd still like to comment.

public int[] moveTile(int clickedRow, int clickedCol, int x, int y) {
  // { ... moves the tile ... }
  return new int[]{clickedRow + y, clickedCol + x}; //returns new tile position on the grid
}

But, see the asymmetry. The first and last argument get summed, and the second and third get summed. Let me rename the arguments a bit to make it clear what is going on:

public int[] moveTile(int posVertical, int posHorizontal, int shiftHorizontal, int shiftVertical) {
  // { ... moves the tile ... }
  return new int[]{posVertical + shiftVertical, posHorizontal + shiftHorizontal}; //returns new tile position on the grid
}

A more logical definition would be

public int[] moveTile(int posVertical, int posHorizontal, int shiftVertical, int shiftHorizontal) {
  // { ... moves the tile ... }
  return new int[]{posVertical + shiftVertical, posHorizontal + shiftHorizontal}; //returns new tile position on the grid
}

(Just swap the last two arguments).

Now, I realise you probably can't do that, but please do consider it. It makes reasoning about the code (at least for me) a lot easier, because then you can somewhat read it as

newPos = oldPos + shift

No-op moves?

Consider the following line

currTile = moveTile(currTile[0], currTile[1], ran.nextInt(1 + 1 + 1) - 1, 0);

First of all, the 1 + 1 + 1 could as well be written 3, but the point is: ran.nextInt(1 + 1 + 1) sometimes returns 1 (and other times 0 or 2). In that case, you'd call moveTile(currTile[0], currTile[1], 0, 0), which is basically a do-nothing operation. In fact, I'd hope that moveTile would throw an error in this case, but I can't check your code there, so I'll assume it will happily move whatever you tell it to.

Unreachable conditional?

One of the conditionals in your code is the following:

} else if (currTile[0] == 0 && currTile[1] == tileGrid.length) {

if currTile[1] were to be tileGrid.length, it would be off the board. So I don't know why you're testing for that.

Too much conditionals?

One of the first things to note is that you have a lot of conditions. I've counted 10 top-level conditions on currentTile.

Also, looking at their order is as follows:

• Top right
• Bottom left
• Bottom right
• Bottom center
• Top center
• Left center
• Right center
• Top left
• (the erroneous one) [Almost bottom right]
• Center

Inside that are 1 or more conditionals using booleans. Ouch.

Unfair distribution?

Looking at the following piece of code:

  ...
} else if (currTile[0] == 0 && currTile[1] > 0 && currTile[1] < tileGrid.length - 1) { // bottom row
  //can move up, left or right
  if (ran.nextBoolean()) {
    currTile = moveTile(currTile[0], currTile[1], 0, 1); // up
  } else {
    currTile = moveTile(currTile[0], currTile[1], ran.nextInt(1 + 1 + 1) - 1, 0); // left or right
  }
} ...

In this case, there are 3 valid moves. Moving up gets chosen with a probability of 50%, left, do-nothing and right would each be chosen with probability 16%. In a fair case, I'd expect all three to be called with about 33% probability.

Improving?

Where to start?

When looking at code, there are two ways I consider if it needs improving. Sometimes I try to look inside-out, and sometimes I look at it from a distance and think 'no'. This is the second case. I want to get rid of the huge if-tree. To do that, you need to consider what each of the branches is doing. And because all branches differ (a bit), that is actually not that easy for me.

Making it more fair.

However, thinking inside out is still the way to improve. Because the first thing I want to fix is the unfair distribution and the no-op moves. So let us take the one with the unfair distribution, and try to make it fair.

  ...
} else if (currTile[0] == 0 && currTile[1] > 0 && currTile[1] < tileGrid.length - 1) { // bottom row
  //can move up, left or right
  if (ran.nextBoolean()) {
    currTile = moveTile(currTile[0], currTile[1], 0, 1); // up
  } else {
    currTile = moveTile(currTile[0], currTile[1], ran.nextInt(1 + 1 + 1) - 1, 0); // left or right
  }
} ...

What do we need to do to make it fair? Make sure that it always does a valid move, and makes all the moves with an equal probability. How can we do that? Let's just enumerate the possibilities. We currently have (expanding the ran.nextInt(3) - 1 to all its expansions)

{ 0, 1} // up
{-1, 0} // left
{ 0, 0} // do-nothing
{ 1, 0} // right

So, we remove the do-nothing

{ 0, 1} // up
{-1, 0} // left
{ 1, 0} // right

Now we assign it to a value. (Disclaimer: this is where I get hazy on exact Java semantics. Let's hope it works.).

int[][] deltas = {{0, 1}, {-1, 0}, {1, 0}};
int[] delta = deltas.get(ran.nextInt(deltas.length));
currTile = moveTile(currTile[0], currTile[1], delta[0], delta[1]);

Applying it everywhere

This same treatment can be given to all the separate blocks, giving the form

int[][] deltas;
if ([[piece is in upper right]]) {
  deltas = new int[][]{{-1, 0}, {0, -1}};
  int[] delta = deltas.get(ran.nextInt(deltas.length));
  currTile = moveTile(currTile[0], currTile[1], delta[0], delta[1]);
} else if ... {
  deltas = new int[][]{...};
  int[] delta = deltas.get(ran.nextInt(deltas.length));
  currTile = moveTile(currTile[0], currTile[1], delta[0], delta[1]);
} else if ... {
...
} else {
  deltas = new int[][]{...};
  int[] delta = deltas.get(ran.nextInt(deltas.length));
  currTile = moveTile(currTile[0], currTile[1], delta[0], delta[1]);
}

Moving same lines out of if

Notice how the last two lines always read the same? Let's move them outside the if blocks.

int[][] deltas;
if ([[piece is in upper right]]) {
  deltas = new int[][]{{-1, 0}, {0, -1}};
} else if ... {
  deltas = new int[][]{...};
} else if ... {
...
} else {
  deltas = new int[][]{...};
}
int[] delta = deltas.get(ran.nextInt(deltas.length));
currTile = moveTile(currTile[0], currTile[1], delta[0], delta[1]);

Seeing patterns

So now the movement is cleanly separated outside the if blocks, as well as the determining of which of the moves to make. But we still have 9 conditionals, but luckily they are quite short, and we can start to see patterns.

To 'see' the patterns, you need to think about the physical form of the game a bit. When is {0, 1} (move up) part of the list? Well, always except for when currentTile[0] == tileGrid.length - 1 (That is, always, except when the hole is at the top). Similar statements can be made for {1, 0}, {-1, 0} and {0, -1}.

public List<int[2]> getNeighbourDeltas(int row, int column) {
  ArrayList<int[2]> deltas = new ArrayList();
  if (row > 0) {
    deltas.append(new int[]{0, -1});
  }
  if (row < tileGrid.length - 1) {
    deltas.append(new int[]{0, 1});
  }
  if (column > 0) {
    deltas.append(new int[]{-1, 0});
  }
  if (column < tileGrid.length - 1) {
    deltas.append(new int[]{1, 0});
  }
  return deltas;
}

Note that the cases are quite simple: If I'm not at the bottom, I can move down. If I'm not at the left, I can move to the left.

List <int[2]> deltas = getNeighbourDeltas(currTile[0], currTile[1]);
int[] delta = deltas.get(ran.nextInt(deltas.length));
currTile = moveTile(currTile[0], currTile[1], delta[0], delta[1]);

So now we moved from 9 if-blocks to just 4. But don't let that fool you. There are still 9 paths through there. (In theory it should be 2 ** 4 = 16, but for decent enough tileGrid.lengths, you never reach both 'up' and 'down' in the same lookup, giving you 3 * 3 = 9 paths.

Finally.

In the end, I got rid of the long list of conditionals by recognising the pattern: Each of the conditionals was looking up a set of valid moves, except they were hard-coded.

The resulting pattern is quite understandable:

• Get a list of tiles I can move into place.
• Choose a tile at random.
• Move it into place.

And isn't that how you normally shuffle?

(Disclaimer: none of the code as-written will compile, unless by a freak accident of nature. Again, Java is not my native language.)