Ändern das 8-puzzle code zum drucken der Zwischenstufen zum erreichen der Lösung

Hier, wie ich richten Sie Ihre Anfrage an Holen Sie sich die trail Verknüpfung von start zu Ziel:

1. Organisiert die Importe explizit zu machen, die utility-Klassen verwendet werden.
2. Umbenannt Variablen zu klären, Bedeutung/Rolle jedes einzelnen.
3. Hinzugefügt, die stateHistory Karte zu beziehen, die jeder Staat zu seinem Vorgänger.
4. Umgestaltet werden, Sie den doppelten Abschluss-check code, der aus jeder Bewegung-Methode in eine separate checkCompletion Methode.
5. Geändert add Methode, um neuen und alten Bundesländern (verinnerlicht, Tiefe lookup-Methode) und zur Aufrechterhaltung der stateHistory Karte sowie die stateDepth Karte und agenda Warteschlange.
6. Geändert checkCompletion Methode laufen die stateHistory wieder aus dem Ziel-Zustand (einmal erreicht), um den ursprünglichen Zustand (den man mit keinen Vorgänger).

Läuft der geänderte code erzeugt diese Ausgabe:

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

Weitere änderung zum drucken der Sequenz in aufsteigender Reihenfolge (start-zu-Ziel, anstatt rückwärts vom Ziel-zum-start) ist Links als eine übung für die Schüler.

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);
        }
    }

}

Eine kleine Verbesserung zu Joel Neely ' s-version: bei der Initialisierung e.stateDepth.put(null, -1); vereinfacht die Logik in der add-Methode int newValue = stateDepth.get(oldState) + 1;.