# Optimized board representation for the 4x4 sliding puzzle

Inspired by this question and my answer to it I told myself I could try an optimized version for a 4x4 puzzle. There are only $16!$ possible states, so the state fits into a single long. However, representing the state as a primitive is ugly and precludes generalizations to bigger puzzles.

Before reviewing please note my slightly different conventions.

To keep it general, there's an abstract parent class:

/** Represents a Slidig Puzzle Board. All instances must be immutable. */
public abstract class Board<B extends Board<B>> {
/**
* Return the manhattan distance between {@code this} and {@code other},
* which gets computed as the sum over all pieces (ignoring the empty field).
*
* <p>Note that this is a valid lower bound on the necessary number of steps.
*/
public abstract int distanceTo(B other);

/** Return the 2-4 children obtained by moving a neighboring piece to the empty field. */
public abstract Collection<B> children();

/**
*  Return a board differing by a single swap. This gets used for nearly-solving unsolvable problems.
*
*  <p>The operation must be self-inverse.
*/
public abstract B alternative();
}


Currently, there's a single implementation, which packs its state into a single long and uses another one for mapping pieces to indexes (i.e., positions numbered from 0 to 15). This allows a very efficient distance calculation as described here.

package maaartin.pazl;

import java.util.Collection;
import java.util.List;
import java.util.regex.Pattern;

/**
* Represents the standard 4x4 board.
*
* <p>Terminology:<ul>
* <li>Index is a number between 0 and 15 denoting the position on the board.
* <li>Piece is a number between 0 and 15 with 0 denoting the empty space.
*/
public class FifteenBoard extends Board<FifteenBoard> {
/**
* Create a new board by interpreting the input as list of pieces. Accepts two formats:<ul>
*
* <li>List of sixteen space-separated decimal numbers like
*     {@code "11 15 12 0 14 10 2 13 7 6 9 8 3 5 4 1"}
* <li>List of four underscore-separated groups of four hexadecimal digits like
*     {@code "0123_4567_89AB_CDEF"}
*
*/
static FifteenBoard from(String input) {
checkArgument(INPUT_STRING_PATTERN.matcher(input).matches());
return FifteenBoard.from(parseStringToLong(input));
}

/**
* Create a new board by interpreting every digit of the argument as the piece on the corresponding index,
* where 0 denotes the empty place.
*/
static FifteenBoard from(long indexToPiece) {
checkArgument(isValidBoard(indexToPiece));
return new FifteenBoard(indexToPiece, dual(indexToPiece));
}

private FifteenBoard(long indexToPiece, long pieceToIndex) {
assert pieceToIndex == dual(indexToPiece);
this.indexToPiece = indexToPiece;
this.pieceToIndex = pieceToIndex;
}

private static long parseStringToLong(String input) {
long result = 0;
if (input.contains(" ")) {
final List<String> split = Splitter.on(" ").splitToList(input);
checkArgument(split.size() == 16);
for (final String s : split) {
final int n = Integer.parseInt(s);
checkArgument(0<=n && n<16);
result = (result << 4) + n;
}
} else {
return UnsignedLongs.parseUnsignedLong(input.replaceAll("_", ""));
}
return result;
}

@VisibleForTesting static int indexToRow(int index) {
assert 0 <= index && index < INDEX_LIMIT;
return index & 3;
}

@VisibleForTesting static int indexToCol(int index) {
assert 0 <= index && index < INDEX_LIMIT;
return index >> 2;
}

@VisibleForTesting static int toIndex(int col, int row) {
assert 0 <= col && col < SIZE;
assert 0 <= row && row < SIZE;
return 4*col + row;
}

@VisibleForTesting static long dual(long data) {
long result = 0;
for (int index=0; index<SIZE*SIZE; ++index) result += (long) index << (4 * get(data, index));
assert isValidBoard(result);
return result;
}

/** Return true if {@code data} in hexadecimal contain all hexadecimal digits. */
private static boolean isValidBoard(long data) {
int bitset = 0;
for (int index=0; index<SIZE*SIZE; ++index) bitset |= 1 << get(data, index);
return bitset == 0xFFFF;
}

/**
* Return a string representation of {@code this}, consisting of 4 groups of 4 hexadecimal digits.
* The groups are separated by an underscore and each corresponds with a puzzle row.
* Every digit corresponds with a piece, with 0 denoting the empty position.
*/
@SuppressWarnings("boxing") @Override public String toString() {
return String.format("%04X_%04X_%04X_%04X",
(indexToPiece>>48) & 0xFFFF,
(indexToPiece>>32) & 0xFFFF,
(indexToPiece>>16) & 0xFFFF,
(indexToPiece>>00) & 0xFFFF);
}

@Override public boolean equals(Object obj) {
if (!(obj instanceof FifteenBoard)) return false;
// The other field can be ignored as it's the dual.
return indexToPiece == ((FifteenBoard) obj).indexToPiece;
}

@Override public int hashCode() {
// This may be a premature optimization, but something like Long.hashCode might lead to too many collisions.
final long result = (123456789 * indexToPiece);
return Longs.hashCode(result);
}

@Override public int distanceTo(FifteenBoard other) {
// Every pair of bits in x and y is one coordinate.
// The coordinates of the empty space don't matter and therefore get excluded via & ~15.
// For all others, we compute the sum of absolute values of their differences.
// See https://codereview.stackexchange.com/a/86907/14363.
final long x = pieceToIndex  & ~15;
final long y = other.pieceToIndex & ~15;
final long xor = x^y;
// High bit per pair will contain whether the pair is 3, low bit is garbled.
final long is3 = xor & (xor << 1);

// High bit per pair will contain whether the pair is non-zero, low bit is garbled.
final long x2 = x | (x << 1);
final long y2 = y | (y << 1);

// High bit per pair will contain whether both pairs are non-zero, low bit is garbled.
final long is0 = x2 & y2;

// High bit per pair will contain whether the pairs need correction, low bit is 0.
final long isBoth = (is3 & is0) & HIGH;
final long val = xor ^ isBoth; // only invert the bits set in both is3 and is0

// Count the high bits twice and the low bits ones.
return Long.bitCount(val) + Long.bitCount(val & HIGH);
}

@Override public Collection<FifteenBoard> children() {
}

final int emptyIndex = pieceToIndex(0);
final int col = indexToCol(emptyIndex);
final int row = indexToRow(emptyIndex);
if (col > 0) result.add(swap(emptyIndex, emptyIndex-4));
if (col < SIZE-1) result.add(swap(emptyIndex, emptyIndex+4));
if (row > 0) result.add(swap(emptyIndex, emptyIndex-1));
if (row < SIZE-1) result.add(swap(emptyIndex, emptyIndex+1));
return result;
}

@Override public FifteenBoard alternative() {
// Swap the first two non-empty positions.
final int index1 = indexToPiece(0) == 0 ? 2 : 0;
final int index2 = indexToPiece(1) == 0 ? 2 : 1;
return swap(index1, index2);
}

/**
* Swap the two pieces at the indexes given by the arguments.
*
* <p>This is a valid move iff the indexes correspond to neighboring positions and one of the positions is empty.
*/
private FifteenBoard swap(int index1, int index2) {
final long piece1 = indexToPiece(index1);
final long piece2 = indexToPiece(index2);
final long pieceXor = piece1 ^ piece2;
final long childIndexToPiece = indexToPiece ^ (pieceXor << 4*index1) ^ (pieceXor << 4*index2);
final long indexXor = index2 ^ index1;
final long childPieceToIndex = pieceToIndex ^ (indexXor << 4*piece1) ^ (indexXor << 4*piece2);
return new FifteenBoard(childIndexToPiece, childPieceToIndex);
}

@VisibleForTesting int indexToPiece(int index) {
return get(indexToPiece, index);
}

@VisibleForTesting int pieceToIndex(int piece) {
return get(pieceToIndex, piece);
}

private static int get(long data, int index) {
return (int) ((data >>> (4*index)) & 0xF);
}

private static final long HIGH = 0xAAAAAAAAAAAAAAAAL;
private static final Pattern INPUT_STRING_PATTERN = Pattern.compile("(\\d+ ){15}\\d+|(\\w{4}_){3}\\w{4}");

private static final int SIZE = 4;
private static final int INDEX_LIMIT = SIZE*SIZE;

@VisibleForTesting final long indexToPiece;
@VisibleForTesting final long pieceToIndex;
}


Additionally, there's a FifteenBoardTest and a some additional files on GitHub, which are not yet ready for a review.

## Row and column confusion

I downloaded the code and played around with it. One thing that quickly confused me was the way that "rows" and "columns" were labelled. For example, given this puzzle:

    0 1 2 3
4 5 6 7
8 9 A B
C D E F


I would imagine "row 0" to be 0 1 2 3 and "row 3" be C D E F. Similarly, I think of "column 0" as 0 4 8 C and "column 3" as 3 7 B F.

However, the code instead does something different. "Row 0" is actually F B 7 3. Not only does is the row vertical, it also runs from bottom to top. "Column 0" is actually F E D C. Which is similarly strange.

My suggestion for fixing this is twofold:

1. Change indexToRow(), indexToCol(), and toIndex() to reverse the meanings of rows and columns.
2. Print the board out in "littleendian" order. Right now, the least significant 4 bits is considered "row 0, column 0", which makes sense when thinking about how to index long. But if the board is printed in "bigendian" order like it currently is, that makes row 0, column 0 the bottom rightmost tile which is strange. The board parser would need to change as well.

## First alternate board format

Since the point of the code is optimizing the 4x4 puzzle and distance calculation, I tried to think of things that could improve the current solution. I came up with a way to make the distance calculation even faster by using a different board encoding. If you change pieceToIndex into two longs called pieceToRow and pieceToCol, and then encoded the rows and columns with the following 3-bit encoding:

0 = 000
1 = 001
2 = 011
3 = 111


Then you could calculate the distance between two boards like this:

public int distanceTo(Board other)
{
return Long.bitCount(pieceToRow ^ other.pieceToRow) +
Long.bitCount(pieceToCol ^ other.pieceToCol);
}


I didn't attempt to code up this board format because I came up with another idea (see below). Theoretically, this board format would be faster for distance calculation but slower to generate new boards due to the more complicated swap() function that would be needed. Only one of pieceToRow or pieceToCol would need to change for a swap, though.

## Second alternate board format

After thinking about it some more, I came up with an idea based on the fact that you only ever care about the distance from the current board to the "solved" board. At least, that was what the original question cared about. If that assumption is true, then you don't really even need to have a fast distance calculation function. What you can do instead is just store the distance between the board and the solved board. Then when you move a piece and create a new board, you can calculate the new distance based on the piece that moved. This new distance will be exactly +1 or -1 from the old distance.

So this new board format stores:

long indexToPiece; // Same as before
int  distance;     // Distance to solved puzzle
int  indexOfHole;  // Since there is no pieceToIndex, we need a quick
// way of finding the index of the hole.


The first time you create a board (from a string), it calculates distance and indexOfHole the slow way. After that, everything is calculated from the previous board. Here are the most important functions that I changed (note that I kept the same bigendian ordering of the board to keep it compatible with the original code, but I did reverse meaning of "row" and "column"):

private Collection<FifteenBoard> addChildrenTo(Collection<FifteenBoard> result) {
final int col = indexToCol(indexOfHole);
final int row = indexToRow(indexOfHole);
if (col > 0)      result.add(move(indexOfHole-1,    3));
if (col < SIZE-1) result.add(move(indexOfHole+1,    2));
if (row > 0)      result.add(move(indexOfHole-SIZE, 1));
if (row < SIZE-1) result.add(move(indexOfHole+SIZE, 0));
return result;
}

/* This array gives the correct row or column index for the given
* number in the final position, which looks like this:
*
*   COL 3 --v  v-- COL 0
*  ROW 3 -> 1234
*           5678
*           9abc
*  ROW 0 -> def
*
* So for example, correctCoord would look up the correct row
* for "5" in the final position, which is row 2.  CorrectCoord
* would look up the column for "5" which is column 3.
*/
static final int [][] correctCoord = {
{ 0, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0 },
{ 0, 3, 2, 1, 0, 3, 2, 1, 0, 3, 2, 1, 0, 3, 2, 1 }
};

/**
* Swap the piece at the given index with the hole.
*
* <p>This is a valid move iff the index corresponds to a neighbor
* of the hole.
*
* @direction        0 = up, 1 = down, 2 = left, 3 = right.
*/
private FifteenBoard move(int index, int direction) {
final int  piece      = indexToPiece(index);
final long pieceXor   = ((long) piece << 4*index) |
((long) piece << 4*indexOfHole);
final long childIndexToPiece = indexToPiece ^ pieceXor;

final int  goodCoord = correctCoord[direction >> 1][piece];
final int  holeCoord = ((direction & 0x2) == 0) ?
indexToRow(indexOfHole) : indexToCol(indexOfHole);
final int  childDistance = distance + (((direction & 1) == 0) ?
/* left /up   */ (goodCoord <= holeCoord ? -1 : 1) :
/* right/down */ (goodCoord >= holeCoord ? -1 : 1));

// The hole is where the piece used to be.
return new FifteenBoard(childIndexToPiece, childDistance, index);
}


The full code is at Github here. There are some changes I made that are incompatible with the original, such as changing the distanceTo(Board) function into a distance() function. I ran a simple speed test that tested the generation of new boards and retrieving the distance of each new board. The new format is about 10-20% faster than the old one, but I didn't test it rigorously.

• "Row and column confusion" - I actually never cared, which is which and it's no surprise that I've got it wrong. "reverse the meanings of rows and columns" - done. "Print the board out in "littleendian" order" - using big endian is important to me as I can look at the numbers in hex and see everything. I guess, I'll adapt the other parts instead (indexToCol and similar don't need to be fast as they'll be used just in the class initialization). – maaartinus Apr 25 '15 at 18:07
• "First alternate board format" - that's a cool idea. Unfortunately, most of the time gets eaten by the GC, so making any object bigger could be bad. However, I have to limit the memory consumption somehow and then I'll come back to this idea. +++ "Second alternate board format" - I want to implement some bidirectional search using a front-to-front evaluation, so I'm hesitant to give up distanceTo. – maaartinus Apr 25 '15 at 18:16

## Magic Numbers

    private static final int SIZE = 4;


You've defined this constant, but somehow there seem to be an awful lot of 4s (and 16s) left lying around. I think this is a particularly egregious example:

        if (col < SIZE-1) result.add(swap(emptyIndex, emptyIndex+4));


## Use functions to clarify your intent

    if (col > 0) result.add(swap(emptyIndex, previousColumn(emptyIndex));
if (col < SIZE-1) result.add(swap(emptyIndex, nextColumn(emptyIndex));
if (row > 0) result.add(swap(emptyIndex, previousRow(emptyIndex));
if (row < SIZE-1) result.add(swap(emptyIndex, nextRow(emptyIndex));


or perhaps even

    if (! firstColumn(col)) result.add(swap(emptyIndex, previousColumn(emptyIndex));


## Don't repeat yourself

All of those statements are the same, aren't they?

for(int neighbor : getNeighbors(emptyIndex)) {
}


You could use the same row/column math as the basis of getNeighbors. Or you could notice that the list of neighbors is a property of the cell that doesn't change over the course of the game (only the location of the empty tile changes). So you could use a lookup table

int [][] locations = { {nextColumn(0), nextRow(0)}
, {previousColumn(1), nextColumn(1), nextRow(1)}
, ...
, {previousColumn(15), previousRow(15)}};


You could probably make that logic even cleaner with a builder.

## Eschew encoding

    final int emptyIndex = pieceToIndex(0);


0 isn't empty, it's a number that you have chosen to represent the "empty piece" in the board. At a minimum, this should be a constant:

    final int emptyIndex = pieceToIndex(EMPTY_SPACE);

• I disagree with the part "Use functions to clarify your intent" as it'd mean using 8 functions to "clarify" those 4 lines. I implemented the "Don't repeat yourself" part, though it's not as nice as I expected: It moves all the boring stuff into the initialization of the int[][] locations. Concerning the rest: +1 and thanks! – maaartinus Apr 25 '15 at 18:02