益智游戏Android DFS算法

我有一个名为Islands和bridge的android应用程序,也称为Hashiwokakero

应用程序使用A 2 Dimensional数组,每次用户重新启动游戏时随机生成群岛它形成一个数字从0到4的矩阵,其中0 = null和1-4 =岛可以有2个桥从一个岛出来连接另一方面,目前的地图无法解决。 为了解决游戏,用户需要使用网桥连接岛屿,因此如果岛屿= 4则需要4个连接,如果岛屿= 2则需要2个连接等等。

在我的研究中,我发现解决游戏的最佳算法是使用深度优先搜索 – 文章

我在这里看了不同的问题,但似乎无法找到解决方案,因为我的数组是String类型而不是integer

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

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

这个函数创建了一个简单的map 4×4矩阵:

 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  0) { getCurrentState().board_elements[row][column].is_island = true; } } } } } 

DFS可以应用于游戏状态。

伪算法:

  1. 挑选一个仍需要桥梁的随机(或其他一些标准)岛屿
  2. 在这个岛屿和它的一个邻居之间建立一座桥梁(显然是一个也需要桥梁的邻居)
  3. 在堆栈上推送游戏的新状态(例如此图的连接矩阵)
  4. 如果游戏包含不一致,请从堆栈中弹出1项
  5. 返回步骤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> remainingOptions = new HashMap<>(); Stack 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 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(); } 

我还写了一个实用程序类来处理需要构建桥的陆地上的常见操作(比如找到下一个可用的岛,检查是否可以构建桥等)

 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 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 || 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 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; } } } }