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> {
    /**
     * Return the manhattan distance between {@code this} and {@code other},
     * which gets computed as the sum over all pieces (ignoring the empty field).
     *
     * 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 children();

    /**
     *  Return a board differing by a single swap. This gets used for nearly-solving unsolvable problems.
     *
     *  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 static com.google.common.base.Preconditions.checkArgument;

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

import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Splitter;
import com.google.common.collect.Lists;
import com.google.common.primitives.Longs;
import com.google.common.primitives.UnsignedLongs;

/**
* Represents the standard 4x4 board.
*
* Terminology:
* Index is a number between 0 and 15 denoting the position on the board.
* Piece is a numb

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:

• Change indexToRow(), indexToCol(), and toIndex() to reverse the meanings of rows and columns.

• 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 addChildrenTo(Collection result) {
    final int col = indexToCol(indexOfHole);
    final int row = indexToRow(indexOfHole);
    if (col > 0)      result.add(move(indexOfHole-1,    3));
    if (col  0)      result.add(move(indexOfHole-SIZE, 1));
    if (row  1234
 *           5678
 *           9abc
 *  ROW 0 -> def
 *
 * So for example, correctCoord[0][5] would look up the correct row
 * for "5" in the final position, which is row 2.  CorrectCoord[1][5]
 * 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.
 *
 * 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 > 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));

    // 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 wi

StackExchange Code Review Q#87292, answer score: 5