益智游戏Android DFS算法

Question

我有一个名为 Islands and bridges 的 android 应用程序，也称为 Hashiwokakero

该应用程序使用一个二维数组，每次用户重新启动游戏时都会随机生成岛屿它形成一个数字从 0 到 4 的矩阵，其中 0 = 空，1-4 = 岛屿可以有 2 座桥出来一个岛连接另一个岛，目前的地图是无解的。为了解决这个游戏，用户需要使用桥梁连接岛屿，所以如果一个岛 = 4 它需要 4 个连接如果一个岛 = 2 它需要 2 个连接等等..

在我的研究中，我发现解决游戏的最佳算法是使用深度优先搜索 - article

我查看了关于的不同问题，但似乎找不到解决方案，因为我的数组类型为 String 而不是 integer。

问题如何应用DFS算法连接岛屿？

这是我的应用程序的屏幕截图。

创建简单地图 4x4 矩阵的函数：

private void InitializeEasy() {
      Random rand = new Random();
      String[][] debug_board_state = new String[4][4];
      setCurrentState(new State(WIDTH_EASY));
      for (int row = 0; row < debug_board_state.length; row++) {
          for (int column = 0; column < debug_board_state[row].length; column++) {
              debug_board_state[row][column] = String.valueOf(rand.nextInt(5));

          }
      }

      for (int row = 0; row < debug_board_state.length; row++) {
          for (int column = 0; column < debug_board_state[row].length; column++) {
              System.out.print(debug_board_state[row][column] + " ");
          }
          System.out.println();
      }
      for (int row = 0; row < WIDTH_EASY; ++row) {
          for (int column = 0; column < WIDTH_EASY; ++column) {
              for (int colNum = column - 1; colNum <= (column + 1); colNum += 1) {

                  getCurrentState().board_elements[row][column] = new BoardElement();
                  getCurrentState().board_elements[row][column].max_connecting_bridges = Integer.parseInt(debug_board_state[row][column]);
                  getCurrentState().board_elements[row][column].row = row;
                  getCurrentState().board_elements[row][column].col = column;

                  if (getCurrentState().board_elements[row][column].max_connecting_bridges > 0) {
                      getCurrentState().board_elements[row][column].is_island = true;
                  }
              }
          }
      }
  }

Answer 1

DFS可以应用于游戏状态。

伪算法：

随机选择一个（或根据其他标准）仍然需要桥梁的岛屿
在这个岛和它的一个邻居之间建一座桥（显然邻居也需要一座桥）
将游戏的新状态（例如该图的连接矩阵）推送到堆栈上
如果游戏包含不一致，从堆栈中弹出 1 个项目
回到第1步，使用栈顶作为当前状态

如前所述，这是一段伪代码。您将需要改进它以处理边缘情况。您还应该考虑防止分支因子变得太大的策略。

示例（未彻底测试，未彻底调试）：

int[][] STARTING_CLUES = {
        {2, 0, 0, 3, 0, 3},
        {0, 1, 4, 0, 4, 0},
        {0, 0, 0, 0, 0, 0},
        {3, 0, 3, 0, 2, 0},
        {0, 0, 0, 1, 0, 2},
        {2, 0, 4, 0, 2, 0}
};

void search(){

    Map<Point, List<Direction>> remainingOptions = new HashMap<>();

    Stack<Land> gameTree = new Stack<>();
    gameTree.push(new Land(STARTING_CLUES));

    while(true){

        Land state = gameTree.peek();
        int[] p = state.lowestTodo();
        if (p == null)
            System.out.println("solution found");

        // move to next game state
        int r = p[0];
        int c = p[1];
        System.out.println("expanding game state for node at (" + r + ", " + c + ")");

        List<Direction> ds = null;
        if(remainingOptions.containsKey(new Point(r,c)))
            ds = remainingOptions.get(new Point(r,c));
        else{
            ds = new ArrayList<>();
            for(Direction dir : Direction.values()) {
                int[] tmp = state.nextIsland(r, c, dir);
                if(tmp == null)
                    continue;
                if(state.canBuildBridge(r,c,tmp[0], tmp[1]))
                    ds.add(dir);
            }
            remainingOptions.put(new Point(r,c), ds);
        }

        // if the node can no longer be expanded, and backtracking is not possible we quit
        if(ds.isEmpty() && gameTree.isEmpty()){
            System.out.println("no valid configuration found");
            return;
        }

        // if the node can no longer be expanded, we need to backtrack
        if(ds.isEmpty()){
            gameTree.pop();
            remainingOptions.remove(new Point(r,c));
            System.out.println("going back to previous decision");
            continue;
        }

        Direction dir = ds.remove(0);
        System.out.println("connecting " + dir.name());
        remainingOptions.put(new Point(r,c), ds);

        Land nextState = new Land(state);
        int[] tmp = state.nextIsland(r,c,dir);
        nextState.connect(r,c, tmp[0], tmp[1]);
        gameTree.push(nextState);

    }

}

public static void main(String[] args) {
    new Main().search();
}

我还编写了一个实用程序 class 来处理需要建造桥梁的那块土地上的常见操作（比如寻找下一个可用岛屿，检查是否可以建造桥梁等）

public class Land {

private int[][] BRIDGES_TO_BUILD;

private boolean[][] IS_ISLAND;
private Direction[][] BRIDGES_ALREADY_BUILT;

public Land(int[][] bridgesToDo){
    BRIDGES_TO_BUILD = copy(bridgesToDo);

    int R = bridgesToDo.length;
    int C = bridgesToDo[0].length;
    BRIDGES_ALREADY_BUILT = new Direction[R][C];
    IS_ISLAND = new boolean[R][C];
    for(int i=0;i<R;i++) {
        for (int j = 0; j < C; j++) {
            BRIDGES_ALREADY_BUILT[i][j] = null;
            IS_ISLAND[i][j] = bridgesToDo[i][j] > 0;
        }
    }
}

public Land(Land other){
    BRIDGES_TO_BUILD = copy(other.BRIDGES_TO_BUILD);
    int R = BRIDGES_TO_BUILD.length;
    int C = BRIDGES_TO_BUILD[0].length;
    BRIDGES_ALREADY_BUILT = new Direction[R][C];
    IS_ISLAND = new boolean[R][C];
    for(int i=0;i<R;i++) {
        for (int j = 0; j < C; j++) {
            BRIDGES_ALREADY_BUILT[i][j] = other.BRIDGES_ALREADY_BUILT[i][j];
            IS_ISLAND[i][j] = other.IS_ISLAND[i][j];
        }
    }
}

public int[] next(int r, int c, Direction dir){
    int R = BRIDGES_TO_BUILD.length;
    int C = BRIDGES_TO_BUILD[0].length;

    // out of bounds
    if(r < 0 || r >=R || c < 0 || c >= C)
        return null;


    // motion vectors
    int[][] motionVector = {{-1, 0},{0,1},{1,0},{0,-1}};
    int i = Arrays.asList(Direction.values()).indexOf(dir);

    // calculate next
    int[] out = new int[]{r + motionVector[i][0], c + motionVector[i][1]};

    r = out[0];
    c = out[1];

    // out of bounds
    if(r < 0 || r >=R || c < 0 || c >= C)
        return null;

    // return
    return out;
}

public int[] nextIsland(int r, int c, Direction dir){
    int[] tmp = next(r,c,dir);
    if(tmp == null)
        return null;
    while(!IS_ISLAND[tmp[0]][tmp[1]]){
        tmp = next(tmp[0], tmp[1], dir);
        if(tmp == null)
            return null;
    }
    return tmp;
}

public boolean canBuildBridge(int r0, int c0, int r1, int c1){
    if(r0 == r1 && c0 > c1){
        return canBuildBridge(r0, c1, r1, c0);
    }
    if(c0 == c1 && r0 > r1){
        return canBuildBridge(r1, c0, r0, c1);
    }
    if(r0 == r1){
        int[] tmp = nextIsland(r0, c0, Direction.EAST);
        if(tmp[0] != r1 || tmp[1] != c1)
            return false;
        if(BRIDGES_TO_BUILD[r0][c0] == 0)
            return false;
        if(BRIDGES_TO_BUILD[r1][c1] == 0)
            return false;
        for (int i = c0; i <= c1 ; i++) {
            if(IS_ISLAND[r0][i])
                continue;
            if(BRIDGES_ALREADY_BUILT[r0][i] == Direction.NORTH)
                return false;
        }
    }
    if(c0 == c1){
        int[] tmp = nextIsland(r0, c0, Direction.SOUTH);
        if(tmp[0] != r1 || tmp[1] != c1)
            return false;
        if(BRIDGES_TO_BUILD[r0][c0] == 0 || BRIDGES_TO_BUILD[r1][c1] == 0)
            return false;
        for (int i = r0; i <= r1 ; i++) {
            if(IS_ISLAND[i][c0])
                continue;
            if(BRIDGES_ALREADY_BUILT[i][c0] == Direction.EAST)
                return false;
        }
    }
    // default
    return true;
}

public int[] lowestTodo(){
    int R = BRIDGES_TO_BUILD.length;
    int C = BRIDGES_TO_BUILD[0].length;

    int[] out = {0, 0};
    for (int i=0;i<R;i++) {
        for (int j = 0; j < C; j++) {
            if(BRIDGES_TO_BUILD[i][j] == 0)
                continue;
            if (BRIDGES_TO_BUILD[out[0]][out[1]] == 0)
                out = new int[]{i, j};
            if (BRIDGES_TO_BUILD[i][j] < BRIDGES_TO_BUILD[out[0]][out[1]])
                out = new int[]{i, j};
        }
    }
    if (BRIDGES_TO_BUILD[out[0]][out[1]] == 0) {
        return null;
    }
    return out;
}

private int[][] copy(int[][] other){
    int[][] out = new int[other.length][other.length == 0 ? 0 : other[0].length];
    for(int r=0;r<other.length;r++)
        out[r] = Arrays.copyOf(other[r], other[r].length);
    return out;
}

public void connect(int r0, int c0, int r1, int c1){
    if(r0 == r1 && c0 > c1){
        connect(r0, c1, r1, c0);
        return;
    }
    if(c0 == c1 && r0 > r1){
        connect(r1, c0, r0, c1);
        return;
    }
    if(!canBuildBridge(r0, c0, r1, c1))
        return;

    BRIDGES_TO_BUILD[r0][c0]--;
    BRIDGES_TO_BUILD[r1][c1]--;

    if(r0 == r1){
        for (int i = c0; i <= c1 ; i++) {
            if(IS_ISLAND[r0][i])
                continue;
            BRIDGES_ALREADY_BUILT[r0][i] = Direction.EAST;
        }
    }
    if(c0 == c1){
        for (int i = r0; i <= r1 ; i++) {
            if(IS_ISLAND[i][c0])
                continue;
            BRIDGES_ALREADY_BUILT[i][c0] = Direction.NORTH;
        }
    }
}
}

益智游戏Android DFS算法

Puzzle Game Android DFS algorithm

java

algorithm

android

depth-first-search