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<State> SET = new HashSet<State>() {
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<State> 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();
preparedStatement = dbConnection.prepareStatement(insertTableSQL);
byte[] initialState = {1, -1, -1, -1, 5, 6, -1, -1, 9, 10, -1, -1, 13, -1, -1, 0};
State s = new State(0, initialState);
QUEUE.add(s);
State current = null;
int numInserted = 0;
while (!QUEUE.isEmpty()) {
numInserted++;
if (numInserted % 20000 == 0) {
System.out.println(numInserted + " " + current.getMoves());
}
current = QUEUE.remove();
SET.add(current);
preparedStatement.setBytes(1, current.getState());
preparedStatement.setInt(2, current.getMoves());
preparedStatement.executeUpdate();
for (State n : findNeighbours(current)) {
if (!SET.contains(n)) {
SET.add(n);
if (!QUEUE.contains(n)) {
QUEUE.add(n);
}
}
}
}
System.out.println("Recorded inserted :D");
} catch (SQLException e) {
System.out.println(e);
} finally {
if (preparedStatement != null) {
preparedStatement.close();
}
if (dbConnection != null) {
dbConnection.close();
}
}
public static ArrayList<State> findNeighbours(State currentState) {
byte[] state = currentState.getState();
ArrayList<State> neighbours = new ArrayList<>();
for (int i = 0; i < state.length; i++) {
if (state[i] == 0) {
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);
}
if (i % 4 != 3) {
byte[] right = new byte[16];
System.arraycopy(state, 0, right, 0, right.length);
byte temp = right[i];
right[i] = right[i + 1];
right[i + 1] = temp;
State s = new State(currentState.getMoves() + 1, right);
neighbours.add(s);
}
if (i > 3) {
byte[] up = new byte[16];
System.arraycopy(state, 0, up, 0, up.length);
byte temp = up[i];
up[i] = up[i - 4];
up[i - 4] = temp;
State s = new State(currentState.getMoves() + 1, up);
neighbours.add(s);
}
if (i < 12) {
byte[] down = new byte[16];
System.arraycopy(state, 0, down, 0, down.length);
byte temp = down[i];
down[i] = down[i + 4];
down[i + 4] = temp;
State s = new State(currentState.getMoves() + 1, down);
neighbours.add(s);
}
}
}
return neighbours;
}
public static class State {
int moves;
byte[] composition;
public State(int moves, byte[] composition) {
this.moves = moves;
this.composition = composition;
}
public int getMoves() {
return moves;
}
public void setMoves(int moves) {
this.moves = moves;
}
public byte[] getState() {
return composition;
}
}
