使用DFS解决8谜题游戏 - java

我正在尝试从BFS实现的此代码开始，解决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);
    }
}

}

参考方案

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

使用该代码，只需更改main方法nextState并添加goDepth方法，就应该能够将其实现为DFS。

我建议分析此代码，然后尝试可视化其在纸上的工作方式。确切了解其工作原理后，您可以毫无问题地在其中实现DFS算法。

Java:找到特定字符并获取子字符串 - java

我有一个字符串4.9.14_05_29_16_21，我只需要获取4.9。数字各不相同，所以我不能简单地获得此char数组的前三个元素。我必须找到最正确的.并将其子字符串化直到那里。我来自Python，因此我将展示Python的实现方法。def foobar(some_string): location = some_string.rfind('.&…

Java-搜索字符串数组中的字符串 - java

在Java中，我们是否有任何方法可以发现特定字符串是字符串数组的一部分。我可以避免出现一个循环。例如String [] array = {"AA","BB","CC" }; string x = "BB" 我想要一个if (some condition to tell wheth…

如何转义将成为字符串一部分的斜线？ - java

我很难找到一种方法来逃避这些引用，String key = StringUtils.substringBetween(html, "class=\"category_keyword\"", ">"); 特别是这部分："class=\"category_keyword…

Java RegEx中的单词边界\ b - java

我在使用\b作为Java Regex中的单词定界符时遇到困难。对于text = "/* sql statement */ INSERT INTO someTable"; Pattern.compile("(?i)\binsert\b");找不到匹配项Pattern insPtrn = Pattern.compile(&…

在Map中，如果我们使用现有键进行修改，则不会获得ConcurrentModificationException - java

我有以下代码，我希望从情况2的情况下抛出ConcurrentModificationException，但它运行成功。据我所知，如果我对地图中的单个键执行相同的操作，则不会抛出异常，因为here但是当我重现这种具有两个案例的多个密钥的场景时，通过新密钥修改。通过现有密钥进行修改。情况1： Map<String,String> mp = new H…