Skip to content

Instantly share code, notes, and snippets.

@chheller

chheller/Driver.java

Created March 8, 2017 08:20
Show Gist options
  • Save chheller/73755e1ceec2910e08bedbf5344b02ef to your computer and use it in GitHub Desktop.
Save chheller/73755e1ceec2910e08bedbf5344b02ef to your computer and use it in GitHub Desktop.
Download ZIP
An implementation of BFS to solve a classic sliding puzzle problem.
Raw
Driver.java
package main;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.TreeSet;
class StateComparator implements Comparator<State> {
public int compare(State a, State b) {
for (int i = 0; i < 22; i++) {
if (a.state[i] < b.state[i])
return -1;
else if (a.state[i] > b.state[i])
return 1;
}
return 0;
}
}
public class Driver {
public static boolean[][] map;
public static int[][] shapes = { { 1, 3, 2, 3, 1, 4, 2, 4 }, { 1, 5, 1, 6, 2, 6 }, { 2, 5, 3, 5, 3, 6 },
{ 3, 7, 3, 8, 4, 8 }, { 4, 7, 5, 7, 5, 8 }, { 6, 7, 7, 7, 6, 8 }, { 5, 4, 5, 5, 5, 6, 4, 5 },
{ 6, 4, 6, 5, 6, 6, 7, 5 }, { 8, 5, 8, 6, 7, 6 }, { 6, 2, 6, 3, 5, 3 }, { 5, 1, 6, 1, 5, 2 } };
private static Viz viz;
public static LinkedList<State> BFS() {
StateComparator comp = new StateComparator();
TreeSet<State> set = new TreeSet<State>(comp);
// HashSet<byte[]> set = new HashSet<byte[]>();
Queue<State> queue = new LinkedList<State>();
LinkedList<State> path = new LinkedList<State>();
State root = new State(null);
queue.add(root);
set.add(root);
while (!queue.isEmpty()) {
// if (queue.size() % 10000 == 0)
// System.out.println(queue.size());
State state = queue.remove();
viz.view.draw(state.state);
if (state.state[0] == 4 && state.state[1] == -2) {
while (state.parent != null) {
path.add(state);
state = state.parent;
}
return path;
}
ArrayList<State> frontier_states = Search_Frontier(state.state);
for (State frontier_state : frontier_states) {
if (!set.contains(frontier_state)) {
State newState = new State(state, frontier_state.state);
queue.add(newState);
set.add(newState);
}
}
}
return null;
}
private static ArrayList<State> Search_Frontier(byte[] state) {
//TODO Find the frontier
ArrayList<State> return_states = new ArrayList<State>();
byte[][] possible_states = new byte[44][22];
for (int i = 0; i < 11; i++) {
byte[] possible_state_up = Arrays.copyOf(state, state.length);
byte[] possible_state_down = Arrays.copyOf(state, state.length);
byte[] possible_state_left = Arrays.copyOf(state, state.length);
byte[] possible_state_right = Arrays.copyOf(state, state.length);
possible_state_up[i * 2 + 1] = (byte) (possible_state_up[i * 2 + 1] - 1);
possible_states[i * 4] = Arrays.copyOf(possible_state_up, possible_state_up.length);
possible_state_down[i * 2 + 1] = (byte) (possible_state_down[i * 2 + 1] + 1);
possible_states[i * 4 + 1] = Arrays.copyOf(possible_state_down, possible_state_down.length);
possible_state_left[i * 2] = (byte) (possible_state_left[i * 2] - 1);
possible_states[i * 4 + 2] = Arrays.copyOf(possible_state_left, possible_state_left.length);
possible_state_right[i * 2] = (byte) (possible_state_right[i * 2] + 1);
possible_states[i * 4 + 3] = Arrays.copyOf(possible_state_right, possible_state_right.length);
}
/* byte[][] possible_states = {{0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,0} ,
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0}};
ArrayList<State> return_states = new ArrayList<State>();
*/
for (int i = 0; i < 44; i++) {
if (canDraw(possible_states[i]))
return_states.add(new State(null, possible_states[i]));
}
return return_states;
}
private static boolean canDraw(byte[] state) {
initMap();
if (!drawPiece(state[0] + shapes[0][0], state[1] + shapes[0][1], state[0] + shapes[0][2],
state[1] + shapes[0][3], state[0] + shapes[0][4], state[1] + shapes[0][5], state[0] + shapes[0][6],
state[1] + shapes[0][7]))
return false;
if (!drawPiece(state[2] + shapes[1][0], state[3] + shapes[1][1], state[2] + shapes[1][2],
state[3] + shapes[1][3], state[2] + shapes[1][4], state[3] + shapes[1][5]))
return false;
if (!drawPiece(state[4] + shapes[2][0], state[5] + shapes[2][1], state[4] + shapes[2][2],
state[5] + shapes[2][3], state[4] + shapes[2][4], state[5] + shapes[2][5]))
return false;
if (!drawPiece(state[6] + shapes[3][0], state[7] + shapes[3][1], state[6] + shapes[3][2],
state[7] + shapes[3][3], state[6] + shapes[3][4], state[7] + shapes[3][5]))
return false;
if (!drawPiece(state[8] + shapes[4][0], state[9] + shapes[4][1], state[8] + shapes[4][2],
state[9] + shapes[4][3], state[8] + shapes[4][4], state[9] + shapes[4][5]))
return false;
if (!drawPiece(state[10] + shapes[5][0], state[11] + shapes[5][1], state[10] + shapes[5][2],
state[11] + shapes[5][3], state[10] + shapes[5][4], state[11] + shapes[5][5]))
return false;
if (!drawPiece(state[12] + shapes[6][0], state[13] + shapes[6][1], state[12] + shapes[6][2],
state[13] + shapes[6][3], state[12] + shapes[6][4], state[13] + shapes[6][5], state[12] + shapes[6][6],
state[13] + shapes[6][7]))
return false;
if (!drawPiece(state[14] + shapes[7][0], state[15] + shapes[7][1], state[14] + shapes[7][2],
state[15] + shapes[7][3], state[14] + shapes[7][4], state[15] + shapes[7][5], state[14] + shapes[7][6],
state[15] + shapes[7][7]))
return false;
if (!drawPiece(state[16] + shapes[8][0], state[17] + shapes[8][1], state[16] + shapes[8][2],
state[17] + shapes[8][3], state[16] + shapes[8][4], state[17] + shapes[8][5]))
return false;
if (!drawPiece(state[18] + shapes[9][0], state[19] + shapes[9][1], state[18] + shapes[9][2],
state[19] + shapes[9][3], state[18] + shapes[9][4], state[19] + shapes[9][5]))
return false;
if (!drawPiece(state[20] + shapes[10][0], state[21] + shapes[10][1], state[20] + shapes[10][2],
state[21] + shapes[10][3], state[20] + shapes[10][4], state[21] + shapes[10][5]))
return false;
return true;
}
private static boolean drawPiece(int x1, int y1, int x2, int y2, int x3, int y3) {
if (map[y1][x1])
map[y1][x1] = false;
else
return false;
if (map[y2][x2])
map[y2][x2] = false;
else
return false;
if (map[y3][x3])
map[y3][x3] = false;
else
return false;
return true;
}
private static boolean drawPiece(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
if (map[y1][x1])
map[y1][x1] = false;
else
return false;
if (map[y2][x2])
map[y2][x2] = false;
else
return false;
if (map[y3][x3])
map[y3][x3] = false;
else
return false;
if (map[y4][x4])
map[y4][x4] = false;
else
return false;
return true;
}
/*
* private static boolean canDraw(byte[] state) {
*
* boolean[][] scope_map = new boolean[10][10]; for (int i = 0; i < 10; i++)
* { scope_map[i] = Arrays.copyOf(map[i], map[i].length); }
*
* for (int i = 0; i < 11; i++) {
*
* for (int j = 0; j < shapes[i].length / 2; j++) {
*
* int mapx = state[i * 2] + shapes[i][j * 2 + 1]; int mapy = state[i * 2 +
* 1] + shapes[i][j * 2 + 2]; // System.out.println(String.format("Id %1$d
* Shape (%2$d,%3$d) // Map (%4$d,%5$d)\nState %6$s",i, shapes[i][j * 2 + //
* 1],shapes[i][j * 2 + 2],mapx, mapy,Arrays.toString(state) )); //
* printMap(scope_map);
*
* if (mapx < 0 || mapy < 0 || mapx > 10 || mapy > 10) return false; else if
* (!scope_map[mapy][mapx]) { // System.out.println("Error!"); return false;
* } else { scope_map[mapy][mapx] = false; } } } return true; }
*/
public static void main(String[] args) throws Exception {
initMap();
viz = new Viz();
// printMap();
LinkedList<State> path = BFS();
printAnswer(path);
System.out.println(path.size());
}
private static void printMap(boolean[][] map) {
for (boolean[] row : map) {
for (boolean bool : row) {
System.out.print((bool) ? " " : 0);
}
System.out.println();
}
System.out.println();
}
private static void initMap() {
map = new boolean[10][10];
for (boolean[] row : map)
Arrays.fill(row, true);
for (int i = 0; i < 10; i++) {
map[i][0] = false;
map[i][9] = false;
}
for (int i = 1; i < 9; i++) {
map[0][i] = false;
map[9][i] = false;
}
map[1][1] = false;
map[1][2] = false;
map[2][1] = false;
map[7][1] = false;
map[8][1] = false;
map[8][2] = false;
map[1][7] = false;
map[1][8] = false;
map[2][8] = false;
map[8][7] = false;
map[7][8] = false;
map[8][8] = false;
map[3][4] = false;
map[4][4] = false;
map[4][3] = false;
}
private static void hardcodeStates() {
byte[] state = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
ArrayList<State> return_states = new ArrayList<State>();
byte[][] possible_states = new byte[44][22];
for (int i = 0; i < 11; i++) {
byte[] possible_state_up = Arrays.copyOf(state, state.length);
byte[] possible_state_down = Arrays.copyOf(state, state.length);
byte[] possible_state_left = Arrays.copyOf(state, state.length);
byte[] possible_state_right = Arrays.copyOf(state, state.length);
possible_state_up[i * 2 + 1] = (byte) (possible_state_up[i * 2 + 1] - 1);
possible_states[i * 4] = Arrays.copyOf(possible_state_up, possible_state_up.length);
possible_state_down[i * 2 + 1] = (byte) (possible_state_down[i * 2 + 1] + 1);
possible_states[i * 4 + 1] = Arrays.copyOf(possible_state_down, possible_state_down.length);
possible_state_left[i * 2] = (byte) (possible_state_left[i * 2] - 1);
possible_states[i * 4 + 2] = Arrays.copyOf(possible_state_left, possible_state_left.length);
possible_state_right[i * 2] = (byte) (possible_state_right[i * 2] + 1);
possible_states[i * 4 + 3] = Arrays.copyOf(possible_state_right, possible_state_right.length);
}
for (int i = 0; i < 44; i++) {
System.out.print("{");
for (int j = 0; j < 22; j++) {
System.out.print(possible_states[i][j] + ",");
}
System.out.print("}");
System.out.println();
}
}
private static void printAnswer(LinkedList<State> states) {
for (State state : states) {
System.out.println(String.format("(%1$s,%2$s) (%3$s,%4$s) (%5$s,%6$s) (%7$s,%8$s) (%9$s,%10$s) (%11$s,%12$s) (%13$s,%14$s) (%15$s,%16$s) (%17$s,%18$s) (%19$s,%20$s) (%21$s,%22$s) ", state.state[0],state.state[1],state.state[2],state.state[3],state.state[4],state.state[5],state.state[6],state.state[7],state.state[8],state.state[9],state.state[10],state.state[11],state.state[12],state.state[13],state.state[14],state.state[15],state.state[16],state.state[17],state.state[18],state.state[19],state.state[20],state.state[21]));
}
}
}
Raw
State.java
package main;
public class State {
State parent;
byte[] state;
public State(State parent) {
this.parent = parent;
this.state = new byte[22];
}
public State(State parent, byte[] state) {
this.parent = parent;
this.state = state;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment