java - DFS 益智游戏解算器 (java)

Question

我在 8 益智游戏中使用 DFS 求解器。此代码打印树中的所有 child ，直到正确状态，但我只想打印正确的解决方案。

我的输出:

120
345
678

125
340
678

102
345
678

125
348
670

125
304
678

142
305
678

012
345
678

预期输出:

120 
345
678

102 
345 
678

012 
345 
678

代码:

public class puzzle {

    public static LinkedHashSet<String> OPEN = new LinkedHashSet<String>();
    public static HashSet<String> CLOSED = new HashSet<String>();
    public static boolean STATE = false;

    public static void main(String args[]) {
        int statesVisited = 0;

        String start = "120345678";
        String goal = "012345678";
        String X = "";
        String temp = "";

        OPEN.add(start);

        while (OPEN.isEmpty() == false && STATE == false) {
            X = OPEN.iterator().next();
            OPEN.remove(X);
            print(X);

            int pos = X.indexOf('0'); // get position of ZERO or EMPTY SPACE
            if (X.equals(goal)) {
                System.out.println("SUCCESS");
                STATE = true;
            } else {
                // generate children
                CLOSED.add(X);

                temp = up(X, pos);
                if (!(temp.equals("-1")))
                    OPEN.add(temp);
                temp = down(X, pos);
                if (!(temp.equals("-1")))
                    OPEN.add(temp);
                    temp = left(X, pos);
                if (!(temp.equals("-1")))
                    OPEN.add(temp);
                temp = right(X, pos);
                if (!(temp.equals("-1")))
                    OPEN.add(temp);
            }

        }
    }
    /*
     * MOVEMENT UP
     */
    public static String up(String s, int p) {
        String str = s;
        if (!(p < 3)) {
            char a = str.charAt(p - 3);
            String newS = str.substring(0, p) + a + str.substring(p + 1);
            str = newS.substring(0, (p - 3)) + '0' + newS.substring(p - 2);
        }
        // Eliminates child of X if its on OPEN or CLOSED
        if (!OPEN.contains(str) && CLOSED.contains(str) == false)
            return str;
        else
            return "-1";
    }

    /*
     * MOVEMENT DOWN
     */
    public static String down(String s, int p) {
        String str = s;
        if (!(p > 5)) {
            char a = str.charAt(p + 3);
            String newS = str.substring(0, p) + a + str.substring(p + 1);
            str = newS.substring(0, (p + 3)) + '0' + newS.substring(p + 4);
        }

        // Eliminates child of X if its on OPEN or CLOSED
        if (!OPEN.contains(str) && CLOSED.contains(str) == false)
            return str;
        else
            return "-1";
    }

    /*
     * MOVEMENT LEFT
     */
    public static String left(String s, int p) {
        String str = s;
        if (p != 0 && p != 3 && p != 7) {
            char a = str.charAt(p - 1);
            String newS = str.substring(0, p) + a + str.substring(p + 1);
            str = newS.substring(0, (p - 1)) + '0' + newS.substring(p);
        }
        // Eliminates child of X if its on OPEN or CLOSED
        if (!OPEN.contains(str) && CLOSED.contains(str) == false)
            return str;
        else
            return "-1";
    }

    /*
     * MOVEMENT RIGHT
     */
    public static String right(String s, int p) {
        String str = s;
        if (p != 2 && p != 5 && p != 8) {
            char a = str.charAt(p + 1);
            String newS = str.substring(0, p) + a + str.substring(p + 1);
            str = newS.substring(0, (p + 1)) + '0' + newS.substring(p + 2);
        }
        // Eliminates child of X if its on OPEN or CLOSED
        if (!OPEN.contains(str) && CLOSED.contains(str) == false)
            return str;
        else
            return "-1";
    }

    public static void print(String s) {
        System.out.println(s.substring(0, 3));
        System.out.println(s.substring(3, 6));
        System.out.println(s.substring(6, 9));
        System.out.println();


    }
}

Answer 1

DFS 返回它找到的第一条路径。要获得最短路径，请使用 BFS。
你可以使用 map

private static Map<String, List<String>> paths = new HashMap<>();

将每个节点(状态)映射到通向它的路径:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;

public class puzzle {

    private static LinkedHashSet<String> OPEN = new LinkedHashSet<>();
    private static HashSet<String> CLOSED = new HashSet<>();
    private static Map<String, List<String>> paths = new HashMap<>();
    public static boolean STATE = false;


    public static void main(String args[]) {

        String start = "120345678";
        String goal =  "012345678";
        String X = "";
        String temp = "";
        OPEN.add(start);
        paths.put(start, Arrays.asList(start));

        while (OPEN.isEmpty() == false && STATE == false) {
            X = OPEN.iterator().next();
            OPEN.remove(X);
            print(X);


            int pos = X.indexOf('0'); // get position of ZERO or EMPTY SPACE
            if (X.equals(goal)) {
                System.out.println("SUCCESS" +"\n" + paths.get(X));
                STATE = true;
            } else {
                // generate children
                CLOSED.add(X);

                temp = up(X, pos);
                if (!temp.equals("-1")) {
                    OPEN.add(temp);
                    updatePaths(temp, paths.get(X));
                }
                temp = down(X, pos);
                if (!temp.equals("-1")) {
                    OPEN.add(temp);
                    updatePaths(temp, paths.get(X));
                }
                    temp = left(X, pos);
                if (!temp.equals("-1")) {
                    OPEN.add(temp);
                    updatePaths(temp, paths.get(X));
                }
                temp = right(X, pos);
                if (!temp.equals("-1")) {
                    OPEN.add(temp);
                    updatePaths(temp, paths.get(X));
                }
            }
        }
    }

    static void updatePaths(String s, List<String> path){

        if(paths.containsKey(s)) return;
        List<String> newPath = new ArrayList<>(path);
        newPath.add(s);
        paths.put(s, newPath);
    }

    /*
     * MOVEMENT UP
     */
    public static String up(String s, int p) {
        String str = s;
        if (!(p < 3)) {
            char a = str.charAt(p - 3);
            String newS = str.substring(0, p) + a + str.substring(p + 1);
            str = newS.substring(0, p - 3) + '0' + newS.substring(p - 2);
        }
        // Eliminates child of X if its on OPEN or CLOSED
        if (!OPEN.contains(str) && CLOSED.contains(str) == false)
            return str;
        else
            return "-1";
    }

    /*
     * MOVEMENT DOWN
     */
    public static String down(String s, int p) {
        String str = s;
        if (!(p > 5)) {
            char a = str.charAt(p + 3);
            String newS = str.substring(0, p) + a + str.substring(p + 1);
            str = newS.substring(0, p + 3) + '0' + newS.substring(p + 4);
        }

        // Eliminates child of X if its on OPEN or CLOSED
        if (!OPEN.contains(str) && CLOSED.contains(str) == false)
            return str;
        else
            return "-1";
    }

    /*
     * MOVEMENT LEFT
     */
    public static String left(String s, int p) {
        String str = s;
        if (p != 0 && p != 3 && p != 7) {
            char a = str.charAt(p - 1);
            String newS = str.substring(0, p) + a + str.substring(p + 1);
            str = newS.substring(0, p - 1) + '0' + newS.substring(p);
        }
        // Eliminates child of X if its on OPEN or CLOSED
        if (!OPEN.contains(str) && CLOSED.contains(str) == false)
            return str;
        else
            return "-1";
    }

    /*
     * MOVEMENT RIGHT
     */
    public static String right(String s, int p) {
        String str = s;
        if (p != 2 && p != 5 && p != 8) {
            char a = str.charAt(p + 1);
            String newS = str.substring(0, p) + a + str.substring(p + 1);
            str = newS.substring(0, p + 1) + '0' + newS.substring(p + 2);
        }
        // Eliminates child of X if its on OPEN or CLOSED
        if (!OPEN.contains(str) && CLOSED.contains(str) == false)
            return str;
        else
            return "-1";
    }

    public static void print(String s) {
       System.out.println(s.substring(0, 3));
       System.out.println(s.substring(3, 6));
       System.out.println(s.substring(6, 9));
       System.out.println();
    }
}

在线代码可以审核执行here和一个重构版here