Solving 8-Puzzle using DFS

Question

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?

Demitria

He's talking about that (en.wikipedia.org/wiki/15_puzzle), but in 3x3 version. It is called "Taquin" in french. – Galvanic

Answer 1

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.

Rusk

I have really learnt alot from your explanation. Thanks so much! – Demitria

I was just wondering how would I use the LinkedHashSet as a stack. So basically LIFO. In the code you presented, its FIFO. – Demitria

I don't know of a LIFO map in the JDK, so I'd use two data structures: A stack for keeping track of the order, and a HashSet for efficient membership testing. – Rusk

There is an error in the "left" method. p should not be 0, 3, or 6. Not 0,3,or 7. – Bicorn

Answer 2

I would suggest you to use the Hipster library to solve the 8-puzzle easily, using BFS, DFS, A*, IDA* etc. There is a full example here (it may help you to design your search strategy).

If you are interested, the basic steps to solve the problem are first define the functions that allow you to traverse the state-space search problem and then pick up one algorithm to search over the state-space problem. In order to create a search problem, you can use the ProblemBuilder class:

SearchProblem p = 
  ProblemBuilder.create()
    .initialState(Arrays.asList(5,4,0,7,2,6,8,1,3))
    .defineProblemWithExplicitActions()
    .useActionFunction(new ActionFunction<Action, List<Integer>>() {
    @Override
    public Iterable<Action> actionsFor(List<Integer> state) {
        // Here we compute the valid movements for the state
        return validMovementsFor(state);
    }
    }).useTransitionFunction(new ActionStateTransitionFunction<Action, List<Integer>>() {
    @Override
    public List<Integer> apply(Action action, List<Integer> state) {
        // Here we compute the state that results from doing an action A to the current state
        return applyActionToState(action, state);
    }
    }).useCostFunction(new CostFunction<Action, List<Integer>, Double>() {
    @Override
    public Double evaluate(Transition<Action, List<Integer>> transition) {
        // Every movement has the same cost, 1
        return 1d;
    }
    }).build();

Once you have your problem definition, you can select any algorithm to solve it:

System.out.println(Hipster.createDijkstra(p).search(Arrays.asList(0,1,2,3,4,5,6,7,8)));

You can read more details about the 8-puzzle problem and how to solve it with Hipster in this presentation https://speakerdeck.com/pablormier/hipster-an-open-source-java-library-for-heuristic-search

Shoshone

Answer 3

You shouldn't push in your open Stack combinations that were already added to it. (Plus, an ArrayDeque would be better, Stack is an old class, see he javadoc http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:

Deque stack = new ArrayDeque(); )

To avoid exploring countless times the same states, you must use a Set as your closed list and verify that the state you are trying to add in the open list were never added to the closed list.

Also, you might be more comfortable using byte[] arrays (not int[] to save memory) rather than strings to perform your operations.

To sum up, you could structure your code like that :

public class Taquin {
    private byte[][] state = new byte[3][3];

    public Taquin(String s) { ... }
    public List<Taquin> successors() { ... }
    public boolean isSolvable(Taquin goal) { ... }
    //Necessary to use the Set !////////////
    public int hashCode() { ... }
    public boolean equals(Object o) { ... }
    public String toString() { ...state }
    ////////////////////////////////////////

    public void solve(Taquin goal) { 
        if (isSolvable(goal)) {
            Deque<Taquin> open   = new ArrayDeque<>();
            Set<Taquin>   closed = new HashSet<>();
            closed.add(this);
            open.add(this);

            Taquin current = this;
            //if isSolvable is correct you should never encounter open.isEmpty() but for safety, test it
            while (!current.equals(goal) && !open.isEmpty()) {
                current = open.pop();
                System.out.println(current);
                for (Taquin succ : current.successors())
                    //we only add to the open list the elements which were never "seen"
                    if (closed.add(succ))
                        open.add(succ);
            }
            System.out.println("Success");
        } else
            System.out.println("No solution");
    }
}

This has the advantage of being generic for any kind of search in a graph. If you wanted to solve another puzzle, you would just modify the method I didn't implement (which are actually part of a Node interface). If you wanted to change the algorithm for example A star which is often used for the 8-puzzle, you would just change the solve method. I hope this sample of code will help you.

Galvanic