Modifying this 8-puzzle code to print the intermediate states to reach the solution

Question

About the 8 Puzzle Problem

// Breadth First Search Usage in the common Eight Puzzle Problem.

import java.util.*;

class EightPuzzle {

    Queue<String> q = new LinkedList<String>();    // Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS.
    Map<String,Integer> map = new HashMap<String, Integer>(); // HashMap is used to ignore repeated nodes

    public static void main(String args[]){


     String str="087465132";     // Input the Board State as a String with 0 as the Blank Space

     EightPuzzle e = new EightPuzzle();   // New Instance of the EightPuzzle
     e.add(str,0);        // Add the Initial State

     while(e.q.peek()!=null){

      e.up(e.q.peek());     // Move the blank space up and add new state to queue
      e.down(e.q.peek());     // Move the blank space down
      e.left(e.q.peek());     // Move left
      e.right(e.q.remove());    // Move right and remove the current node from Queue
     }
     System.out.println("Solution doesn't exist");
    }

    //Add method to add the new string to the Map and Queue
    void add(String str,int n){
     if(!map.containsKey(str)){
      map.put(str,n);
      q.add(str);
     }
    }

    /* Each of the Methods below Takes the Current State of Board as String. Then the operation to move the blank space is done if possible.
          After that the new string is added to the map and queue.If it is the Goal State then the Program Terminates.
    */
    void up(String str){
     int a = str.indexOf("0");
     if(a>2){
      String s = str.substring(0,a-3)+"0"+str.substring(a-2,a)+str.charAt(a-3)+str.substring(a+1);
      add(s,map.get(str)+1);
      if(s.equals("123456780")) {
       System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
       System.exit(0);
      }
     }
    }
    void down(String str){
     int a = str.indexOf("0");
     if(a<6){
      String s = str.substring(0,a)+str.substring(a+3,a+4)+str.substring(a+1,a+3)+"0"+str.substring(a+4);
      add(s,map.get(str)+1);
      if(s.equals("123456780")) {
       System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
       System.exit(0);
      }
     }
    }
    void left(String str){
     int a = str.indexOf("0");
     if(a!=0 && a!=3 && a!=6){
      String s = str.substring(0,a-1)+"0"+str.charAt(a-1)+str.substring(a+1);
      add(s,map.get(str)+1);
      if(s.equals("123456780")) {
       System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
       System.exit(0);
      }
     }
    }
    void right(String str){
     int a = str.indexOf("0");
     if(a!=2 && a!=5 && a!=8){
      String s = str.substring(0,a)+str.charAt(a+1)+"0"+str.substring(a+2);
      add(s,map.get(str)+1);
      if(s.equals("123456780")) {
       System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
       System.exit(0);
      }
     }
    }
}

I want to modify the code so that it prints the intermediate states used to reach the solution, instead of just saying the level on which the solution was reached.

For example, given this board

1 4 2
3 0 5
6 7 8

(as String 142305678)

I want it to print:

1 4 2
3 0 5
6 7 8

(as the String 142305678)

1 0 2
3 4 5
6 7 8

(as the String 102345678)

0 1 2
3 4 5
6 7 8

(as the String 012345678)

By looking at the code, I believe this intermediate strings are getting stored via the add method into the Queue:

void add(String str,int n){
     if(!map.containsKey(str)){
      map.put(str,n);
      q.add(str);
     }
    }

I have no experience working with HashMap, how would I look into the intermediate states stored there?

Answer 1

Actually, the solution appears to be stored in the queue. The map is only used to detect repeated states.

When it's finished, pop each item off the queue and print it out.

Answer 2

Here's how I addressed your request to get the trail linking start to goal:

1. Organized the imports to make explicit which utility classes are being used.
2. Renamed variables to clarify meaning/role of each.
3. Added the stateHistory map to relate each state to its predecessor.
4. Refactored the duplicated completion-check code out of each movement method into a separate checkCompletion method.
5. Modified the add method to take new and old states (internalized the depth lookup to that method) and to maintain the stateHistory map as well as the stateDepth map and agenda queue.
6. Modified the checkCompletion method to walk the stateHistory back from the goal state (once reached) to the original state (the one with no predecessor).

---

Running the modified code produces this output:

Solution Exists at Level 28 of the tree
123456780 at 28
123450786 at 27
120453786 at 26
102453786 at 25
152403786 at 24
152043786 at 23
152743086 at 22
152743806 at 21
152743860 at 20
152740863 at 19
150742863 at 18
105742863 at 17
145702863 at 16
145072863 at 15
045172863 at 14
405172863 at 13
475102863 at 12
475162803 at 11
475162083 at 10
475062183 at 9
475602183 at 8
475682103 at 7
475682130 at 6
475680132 at 5
470685132 at 4
407685132 at 3
487605132 at 2
487065132 at 1
087465132 at 0

Further modification to print the sequence in forward order (start-to-goal, rather than backwards from goal-to-start) is left as an exercise to the student.

---

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

class EightPuzzle {

    Queue<String> agenda = new LinkedList<String>();    // Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS.
    Map<String,Integer> stateDepth = new HashMap<String, Integer>(); // HashMap is used to ignore repeated nodes
    Map<String,String> stateHistory = new HashMap<String,String>(); // relates each position to its predecessor

    public static void main(String args[]){

        String str="087465132";                                 // Input the Board State as a String with 0 as the Blank Space

        EightPuzzle e = new EightPuzzle();              // New Instance of the EightPuzzle
        e.add(str, null);                                                   // Add the Initial State

        while(!e.agenda.isEmpty()){
            String currentState = e.agenda.remove();
            e.up(currentState);                                       // Move the blank space up and add new state to queue
            e.down(currentState);                                     // Move the blank space down
            e.left(currentState);                                     // Move left
            e.right(currentState);                          // Move right and remove the current node from Queue
        }

        System.out.println("Solution doesn't exist");
    }

    //Add method to add the new string to the Map and Queue
    void add(String newState, String oldState){
        if(!stateDepth.containsKey(newState)){
            int newValue = oldState == null ? 0 : stateDepth.get(oldState) + 1;
            stateDepth.put(newState, newValue);
            agenda.add(newState);
            stateHistory.put(newState, oldState);
        }
    }

    /* Each of the Methods below Takes the Current State of Board as String. Then the operation to move the blank space is done if possible.
      After that the new string is added to the map and queue.If it is the Goal State then the Program Terminates.
     */
    void up(String currentState){
        int a = currentState.indexOf("0");
        if(a>2){
            String nextState = currentState.substring(0,a-3)+"0"+currentState.substring(a-2,a)+currentState.charAt(a-3)+currentState.substring(a+1);
            checkCompletion(currentState, nextState);
        }
    }

    void down(String currentState){
        int a = currentState.indexOf("0");
        if(a<6){
            String nextState = currentState.substring(0,a)+currentState.substring(a+3,a+4)+currentState.substring(a+1,a+3)+"0"+currentState.substring(a+4);
            checkCompletion(currentState, nextState);
        }
    }
    void left(String currentState){
        int a = currentState.indexOf("0");
        if(a!=0 && a!=3 && a!=6){
            String nextState = currentState.substring(0,a-1)+"0"+currentState.charAt(a-1)+currentState.substring(a+1);
            checkCompletion(currentState, nextState);
        }
    }
    void right(String currentState){
        int a = currentState.indexOf("0");
        if(a!=2 && a!=5 && a!=8){
            String nextState = currentState.substring(0,a)+currentState.charAt(a+1)+"0"+currentState.substring(a+2);
            checkCompletion(currentState, nextState);
        }
    }

    private void checkCompletion(String oldState, String newState) {
        add(newState, oldState);
        if(newState.equals("123456780")) {
            System.out.println("Solution Exists at Level "+stateDepth.get(newState)+" of the tree");
            String traceState = newState;
            while (traceState != null) {
                System.out.println(traceState + " at " + stateDepth.get(traceState));
                traceState = stateHistory.get(traceState);
            }
            System.exit(0);
        }
    }

}

Answer 3

A small enhancement to Joel Neely's version: initializing e.stateDepth.put(null, -1); simplifies the logic in the add method, int newValue = stateDepth.get(oldState) + 1;.