使用DFS解决8益智游戏

Question

我正试图解决DFS从用BFS实现的此代码开始的8益智问题。做这件事最简单的方法是什么？我研究过的所有代码都是工作和不完整的，这使我陷入了比以前更加混乱的境地。

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拼图，但

与该代码的最佳方式，你应该能够仅通过改变主要方法，nextState并增加了实现它为DFS goDepth方法。

我建议分析一下这段代码，然后试着想象它在纸上的工作原理。在你完全理解它是如何工作的之后，你可以在其中实现DFS算法。