java - 使用 DFS 解决 8 谜游戏

Question

我正在尝试从使用 BFS 实现的这段代码开始使用 DFS 解决 8-puzzle 问题。最简单的方法是什么？我研究过的所有代码要么可以工作，要么不完整，这让我比以前更加困惑。

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 1

DFS 并不是解决 8 个难题的最佳方法，但是，

使用该代码，您应该能够通过仅更改 main 方法 nextState 并添加 goDepth 方法来将其实现为 DFS。

我建议分析这段代码，然后尝试在纸上想象它是如何工作的。当你确切地理解了它的工作原理之后，你就可以毫无问题地在其中实现DFS算法了。