Solving 8-Puzzle using DFS
I am looking for code in java that implement DFS and BFS for the 8-puzzle game by given initial state :
1 2 3
8 0 4
7 6 5
and Goal state
2 8 1
0 4 3
7 6 5
I need to print the solution path from initial to goal state (Not done yet)
This is the code I have. So far I have only been able to implement DFS. What my program does so far is it outputs SUCCESS once it finds the goal state. However it never gets to this point.
Can someone tell me where I am going wrong?
Answer
Ok, so your program is taking longer than expected. First we'll want to find out if it is stuck in an infinite loop, or just slow. To do that, let's have the program print its progress by adding the following to the main loop:
int statesVisited = 0;
while (OPEN.empty() == false && STATE == false) {
statesVisited++;
System.out.println(statesVisited);
We then see that the program visited a couple thousand states per second. Since our processor executes several billion instructions per second, this implies processing a state takes about a million cpu instructions. It shouldn't be that high, should it? So what could be causing this?
Generally speaking, we'd now use a profiler to measure just what part of the code all this time is spent in, but since the program is so short we can try guessing first. My first guess is that printing every state we visit could be quite expensive. To verify this, let's print only every 1000th state:
while (OPEN.empty() == false && STATE == false) {
statesVisited++;
if (statesVisited % 1000 == 0) {
System.out.println(statesVisited);
}
We that change in place, we notice that the first 5000 states are visited in under second, so printing was indeed significant. We also notice something curious: While the first 5000 states are visited in under a second, for some reason the program seems to get slower and slower. At 20000 states visited, it takes about a second to visit 1000 states, and it keeps getting worse. This is unexpected, as processing a state should not get more and more expensive. So we know some operation in our loop is getting increasingly more expensive. Let's review our code to identify which operation it could be.
Pushing and popping takes constant time regardless of the size of the collection. But you also use Stack.search and LinkedList.contains. Both these operations are documented to require iterating over the entire stack or list. So, let's output the sizes of these collections:
if (statesVisited % 1000 == 0) {
System.out.println(statesVisited);
System.out.println(OPEN.size());
System.out.println(CLOSED.size());
System.out.println();
}
After waiting a little while, we see:
40000
25947
39999
So OPEN contains 25000 elements, and CLOSED nearly 40000. That explains why processing a state keeps getting slower and slower. We'll therefore want to choose data structures with a more efficient contains operation, such as a java.util.HashSet or java.util.LinkedHashSet (which is a hybrid between a hash set and a linked list, permitting us the retrieve elements in the order they were added). Doing this, we get:
public static LinkedHashSet<String> OPEN = new LinkedHashSet<String>();
public static HashSet<String> CLOSED = new HashSet<String>();
public static boolean STATE = false;
public static void main(String args[]) {
int statesVisited = 0;
String start = "123804765";
String goal = "281043765";
String X = "";
String temp = "";
OPEN.add(start);
while (OPEN.isEmpty() == false && STATE == false) {
X = OPEN.iterator().next();
OPEN.remove(X);
int pos = X.indexOf('0'); // get position of ZERO or EMPTY SPACE
if (X.equals(goal)) {
System.out.println("SUCCESS");
STATE = true;
} else {
// generate children
CLOSED.add(X);
temp = up(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
temp = left(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
temp = down(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
temp = right(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
}
}
}
/*
* MOVEMENT UP
*/
public static String up(String s, int p) {
String str = s;
if (!(p < 3)) {
char a = str.charAt(p - 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p - 3)) + '0' + newS.substring(p - 2);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT DOWN
*/
public static String down(String s, int p) {
String str = s;
if (!(p > 5)) {
char a = str.charAt(p + 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p + 3)) + '0' + newS.substring(p + 4);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT LEFT
*/
public static String left(String s, int p) {
String str = s;
if (p != 0 && p != 3 && p != 7) {
char a = str.charAt(p - 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p - 1)) + '0' + newS.substring(p);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT RIGHT
*/
public static String right(String s, int p) {
String str = s;
if (p != 2 && p != 5 && p != 8) {
char a = str.charAt(p + 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p + 1)) + '0' + newS.substring(p + 2);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
public static void print(String s) {
System.out.println(s.substring(0, 3));
System.out.println(s.substring(3, 6));
System.out.println(s.substring(6, 9));
System.out.println();
}
which prints "SUCCESS" nearly instantly.