3
我正試圖解決DFS從用BFS實現的此代碼開始的8益智問題。做這件事最簡單的方法是什麼?我研究過的所有代碼都是工作和不完整的,這使我陷入了比以前更加混亂的境地。使用DFS解決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);
}
}
}
我知道它不是這樣,但我必須使用它,它很枯燥,它的一個lisp版本需要很長的時間來運行,以查明它是否正常工作。因此我正在嘗試這個。 – Johnny