Storing configurations of states to a database - Breadth First Search

I have wrote some code to store all possible configurations of a set of numbers in the sliding tile puzzle but the process of doing slow is very slow.

Say, for instance, I have a sliding tile puzzle with the goal state of {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0} where the 0 represents the blank tile which other tiles can move into.

I have performed a breadth first search from the goal configuration to find all possible configurations for the given subset of tiles:

The image above displays the numbers that I am storing all permutations for, so every other tile is represented by a -1, other than the 0 because I need this to move tiles. I perform the breadth-first search from the goal state because each new iteration adds one to the number of moves, so each time it looks for possible moves (neighbours) in my code it adds 1 to it.

My question is, is there any way I can speed up this process? I have currently stored 60,000 states in 15 minutes of execution time and there are a total of \$\frac{16!}{(16-6)!} = 5765760\$ states, so this will take a very long time. Also, the time will grow as I am storing the states in a seen list.

```
static Set SET = new HashSet() {
private static final long serialVersionUID = 1L;

@Override
public boolean contains(Object obj) {
State v = (State) obj;
for (State mad : this) {
if (Arrays.equals(mad.getState(), v.getState())) {

return true;
}
}
return false;
}

};
static Queue QUEUE = new LinkedList<>();

public static void main(String[] args) throws SQLException {
// TODO code application logic here

Connection dbConnection = null;
PreparedStatement preparedStatement = null;
String insertTableSQL = "INSERT INTO six_six_three.six"
+ "(STATE, VALUE) VALUES"
+ "(?,?)";
try {
dbConnection = getDBConnection();

Prefer interfaces to implementations

public static ArrayList findNeighbours(State currentState) {

Consider

public static List findNeighbours(State currentState) {

This way you can change from ArrayList to another implementation at just one place: the initialization.

Remember what you know

for (int i = 0; i < state.length; i++) {
        if (state[i] == 0) {

Note that each state knows where the empty spot is when you create it. So why iterate to find the empty spot? Just store it. Then you can get just say

int i = state.getEmptyIndex();

That saves looping at the cost of a little more memory.

Pick your data type

You use a byte[] to store the state. That's easy to access, but it's hard to copy and store. Consider using a long instead. Each square takes four bits to hold. Determining the neighbors is a little more complicated, but not terribly so. And best of all, you can say things like

if (!seen.contains(next)) {
        neighbours.add(next);
    }

Where seen can be a HashSet.

Third time refactor

There's a rule of thumb. If you're doing something once, just write it out for that purpose. If you do it a second time, copy and paste and then modify to fit. If you do it a third time, refactor so that you're just calling one method three times with different data. This isn't an absolute rule. Sometimes it makes sense to put the code in a method the first or second time. But it almost always makes sense by the third time.

You have the same basic code written four times.

if (i % 4 != 0) {
                byte[] left = new byte[16];
                System.arraycopy(state, 0, left, 0, left.length);
                byte temp = left[i];
                left[i] = left[i - 1];
                left[i - 1] = temp;
                State s = new State(currentState.getMoves() + 1, left);
                neighbours.add(s);

            }

You can call a method for this.

int column = i % WIDTH;
    if (column > 0) {
        move(-1, currentState, neighbours);
    }

And define move as

private void move(int direction, State current, List neighbours) {
    State next = current.move(direction);
    if (!SET.contains(next)) {
        neighbours.add(next);
    }
}

And define that move as

public State move(int direction) {
    int index = getEmptyIndex();
    long next = swapBits(composition, index, index + direction, BIT_WIDTH);
    return new State(getMoves() + 1, next, index + direction);
}

And we can get swapBits from here:

public long swapBits(long n, int from, int to, int width) {
    from *= width;
    to *= width;
    long xor = ((n >> from) ^ (n >> to)) & ((1U << width) - 1);
    return n ^ ((xor << from) | (xor << to));
}

You don't provide enough context for testing, so I haven't tried to run this. There may need to be tweaking.

This looks more complicated but it should actually use less memory.

if (column = WIDTH) {
        move(-WIDTH, currentState, neighbours);
    }
    if (i < SIZE - WIDTH) {
        move(WIDTH, currentState, neighbours);
    }

The remaining three possible moves.

Note that I also saved i % 4 as column so as not to repeat that. I also find that easier to read.

I added constants for WIDTH, which would be 4, SIZE as 16, and BIT_WIDTH as 4. Other possible triplets include 3, 9, and 4.

Performance

The hope was that a more aggressive check of the seen tracker would help here. Other than that, this shouldn't make much difference.

@Override
    public boolean contains(Object obj) {
        State v = (State) obj;
        for (State mad : this) {
            if (Arrays.equals(mad.getState(), v.getState())) {

                return true;
            }
        }
        return false;
    }

So every time you call SET.contains or SET.add (which calls contains), you do an Arrays.equals on each and every member of the SET. You took an \$\mathcal{O}(1)\$ operation and turned it into a \$\mathcal{O}(n)\$. Why? You could have just made this a List with the same performance. Instead of overriding HashSet.contains, consider what happens if you override State.hashCode.

current = QUEUE.remove();
                SET.add(current);

You also call SET.add ever time you remove something from the queue. And you remove every valid state from the queue. I.e. \$\mathcal{O}(n)\$ times. So now we're up to \$\mathcal{O}(n^2)\$. You only add to the queue once without adding to the set. So just move the SET.add to where you put the initial state in the queue.

if (!SET.contains(n)) {
                        SET.add(n);
                        if (!QUEUE.contains(n)) {
                            QUEUE.add(n);
                        }
                    }

You can trim this down.

```
if (!SET.contains(n)) {
SET.add(n);
QUEUE.

StackExchange Code Review Q#154847, answer score: 4