n-puzzle DFS 解决方案适用于 2X2 但 StackOverflowError 适用于 3X3

Question

我的 npuzzle 解决方案适用于 2x2，但堆栈溢出错误适用于 3x3。我无法弄清楚出了什么问题。我正在使用 DFS 检查是否有任何路径有解决方案。算法， - 向左、向右、向上和向下移动棋子。 - 每次检查状态是否已被访问。 - 如果未访问标记已访问并检查它是否与目标状态匹配。我认为堆栈应该能够容纳所有状态，应该只有 181400 个状态吧？

请帮忙！

public class PuzzleSolvable {

public static final int N = 3;
public static int[][] s2 = new int[][]{{8, 2, 1},
                                       {-1, 4, 3},
                                       {7, 6, 5}};

public static void main(String[] args) {
    int[][] stage1 = new int[][]{ //needs 5 swaps
                                  {1, 2, 3},
                                  {4, 5, 6},
                                  {7, 8, -1}
    };

    /*int[][] stage1 = new int[][]{{1, 2},
                                 {4, -1}};
    int[][] stage2 = new int[][]{{-1, 1},
                                 {4, 2}};*/
    Map<String, Boolean> map = new HashMap<>();
    boolean solution = false;
    for (int i = 0; i <= 181440; i = i + 3000) {
        if (isSolvable(stage1, map, i)) {
            solution = true;
            break;
        }
    }

    if (solution) {
        System.out.println("Solution exists");
    }else{
        System.out.println("Solution does not exist");
    }
}

static boolean isSolvable(int[][] s1, Map<String, Boolean> map, int depth) {
    if (depth > 3000) {
        return false;
    }
    depth++;
    System.out.println(serializeArray(s1));
    System.out.println(map.size());
    if (map.get(serializeArray(s1)) != null) {
        return false;
    }
    if (equals(s1, s2)) {
        return true;
    }
    map.put(serializeArray(s1), true);

    return isSolvable(move(s1, 0), map, depth) ||
           isSolvable(move(s1, 1), map, depth) ||
           isSolvable(move(s1, 2), map, depth) ||
           isSolvable(move(s1, 3), map, depth);
}

static String serializeArray(int[][] arr) {
    String s = "";
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            s = s + arr[i][j];
        }
    }
    return s;
}

static boolean equals(int[][] s1, int[][] s2) {

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (s1[i][j] != s2[i][j]) {
                return false;
            }
        }
    }
    return true;
}

static int[][] move(int[][] arr, int direction) {
    int[][] array = new int[N][N];
    int posx = 0, posy = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            array[i][j] = arr[i][j];
            if (arr[i][j] == -1) {
                posx = i;
                posy = j;
            }
        }
    }

    switch (direction) {
        case 0://right
            if (posy < N - 1) {
                System.out.println("Swap right");
                swap(array, posx, posy, posx, posy + 1);
            }
            break;
        case 1://left
            if (posy > 0) {
                System.out.println("Swap left");
                swap(array, posx, posy, posx, posy - 1);
            }
            break;
        case 2://up
            if (posx > 0) {
                System.out.println("Swap up");
                swap(array, posx, posy, posx - 1, posy);
            }
            break;
        case 3://down
            if (posx < N - 1) {
                System.out.println("Swap down");
                swap(array, posx, posy, posx + 1, posy);
            }
            break;
    }
    return array;
}

static void swap(int[][] arr, int posx, int posy, int x, int y) {
    int temp = arr[posx][posy];
    arr[posx][posy] = arr[x][y];
    arr[x][y] = temp;
}}

已编辑： 使用递归深度限制器实现的工作版本更新了代码。

Answer 1

我认为堆栈溢出确实有道理。
如果您使用

表示的目标对其进行测试

static int[][] s2 = new int[][]{
    { 1,  2, 3},
    { 4, -1, 5},
    { 6,  7, 8}
};

并将初始状态设置为

int[][] stage5 = new int[][]{ //needs 5 swaps
    { 2,  3,   5},
    { 1,  4,  -1},
    { 6,  7,   8}
};

需要5次交换才能得到目标，isSolvable无一例外地被调用了54次。
如果将初始状态设置为

int[][] stage6 = new int[][]{ //needs 6 swaps
    { 2,  3,  5},
    { 1,  4,  8},
    { 6,  7, -1}
};

需要 6 次交换才能获得目标，isSolvable 被调用了大约 12000 次，并抛出 WhosebugError.

即使是像

这样简单的休息

recusiveTest(stage6,  new Random());

//overflows after less than 5k invokes
private static boolean recusiveTest(int[][] array, Random rand){
    System.out.println("counter " +isSolvedCounter++);
    array[rand.nextInt(2)][rand.nextInt(2)] = 0;
    return recusiveTest(array, rand);
}

在少于 5000 次运行后抛出 WhosebugError。
非递归 dfs 解决方案会更可靠。

Answer 2

这是一个递归深度有限的版本。它需要分析（它很慢）但它可以工作（通过一系列测试用例进行测试。虽然没有完全调试）：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class LimitedDfs {

    private static final int DEPTH_LIMIT = 3000;
    private static final int BLANK = 9;

    private static int[][] directions = {
            {-1, 0},  //up
            { 0,-1},  //left
            { 0, 1},  //right
            { 1, 0}   //down
    };

    private static int[][] target = new int[][]{
        { 1,  2,  3},
        { 4,  5,  6},
        { 7,  8,  9}
    };

    private static State targetState = new State(target);

    public static void main(String[] args) {

        int[][] swap31 = new int[][] {
            {3,5,1},
            {6,2,4},
            {8,7,9}
        };

        isSolvable(swap31);
    }

    static boolean isSolvable(int[][] stateData) {

        State state = new State(stateData);
        List<State> tested = new ArrayList<>();
        LinkedList<State> toBeTested = new LinkedList<>();
        toBeTested.add(state);
        boolean solution = false;

        System.out.print("working ");
        while (! toBeTested.isEmpty()) {

            if ( isSolvable(toBeTested, tested, 0)){
                solution = true;
                break;
            }
            System.out.print(".");
        }

        System.out.print(" Tested "+ tested.size() + " states. ");

        if (solution) {
            System.out.println("\n       -> Solution exists ");
        }else{
            System.err.println("\n       -> Solution does not exist ");
        }

        return solution;
    }

    static boolean isSolvable(LinkedList<State> toBeTested, List<State> tested, int depth) {

        if((depth ++ > DEPTH_LIMIT) || toBeTested.isEmpty()) {
            return false;
        }

        //else get last element in stack
        State state = toBeTested.peek();

        if (state.equals(targetState)) {
            return true;
        }

        int added = 0;
        for(int[] dir : directions) {

            State newState = move(state, dir);
            if((newState != null)  && ! tested.contains(newState)) {
                toBeTested.add(newState);
                tested.add(newState);
                added++;
                break;
            }
        }

        if(added == 0) { // means state was fully explored, remove it
            toBeTested.remove(state);
        }

        return isSolvable(toBeTested, tested, depth);
    }

    private static State move(State state, int[] dir) {

        int[][] stateData = state.getState();
        int size = stateData.length;

        int[][] newArray = new int[size][size];
        int posY = 0, posX = 0;
        for (int y = 0; y < size; y++) {
            for (int x = 0; x < size; x++) {
                newArray[y][x] = stateData[y][x];
                if (stateData[y][x] == BLANK) {
                    posY = y;
                    posX = x;
                }
            }
        }

        if( isValidAddress(posY + dir[0], posX + dir[1], size, size)) {
            swap(newArray, posY, posX,posY+ dir[0], posX+ dir[1]);
            return new State(newArray);
        }

        return null;
    }

    private static void swap(int[][] arr, int y1, int x1, int y2, int x2) {
        int temp = arr[y1][x1];
        arr[y1][x1] = arr[y2][x2];
        arr[y2][x2] = temp;
    }

    private static boolean isValidAddress(int rowIndex,int colIndex,
            int numberOfRows, int numberOfCols) {

        if((rowIndex <0) || (rowIndex >= numberOfRows)||
                (colIndex <0) || (colIndex >= numberOfCols)) {
            return false;
        }

        return true;
    }
}

class State {

    private final int[][] state;
    private final int hash;

    State(int[][] state) {
        this.state = state;
        hash = serializeArray(state).hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {  return true;    }
        if (obj == null) {  return false;   }
        if (getClass() != obj.getClass()) {
            return false;
        }

        return hash == obj.hashCode();
    }

    @Override
    public int hashCode() {
        return hash;
    }

    int[][] getState() {
        return state;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for(int[] array : state) {
            sb.append(Arrays.toString(array))
            .append("\n");
        }
        return sb.toString();
    }

    private static String serializeArray(int[][] array) {

        StringBuilder sb = new StringBuilder();

        for (int[] elements : array) {
            for (int element : elements) {
                sb.append(element);
            }
        }
        return sb.toString();
    }
}

n-puzzle DFS 解决方案适用于 2X2 但 StackOverflowError 适用于 3X3

n-puzzle DFS solution works for 2X2 but StackOverflowError for 3X3

java

recursion

stack-overflow

depth-first-search

sliding-tile-puzzle