益智游戏Android DFS算法 [英] Puzzle Game Android DFS algorithm
本文介绍了益智游戏Android DFS算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我有一个名为Islands和bridge的android应用程序，也称为
这是函数t o创建一个简单的地图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;
}
}
}
}
}
解决方案
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（找到解决方案）;
//移动到下一个游戏状态
int r = p [0];
int c = p [1];
System.out.println（扩展节点的游戏状态为（+ r +，+ c +））;
列表< 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）;
如果（tmp == null）
继续;
if（state.canBuildBridge（r，c，tmp [0]，tmp [1]））
ds.add（dir）;
}
remainingOptions.put（new Point（r，c），ds）;
}
//如果节点无法再展开，并且无法回溯，我们退出
if（ds.isEmpty（）&& gameTree.isEmpty（ ））{
System.out.println（找不到有效配置）;
返回;
}
//如果节点无法再展开，我们需要回溯
if（ds.isEmpty（））{
gameTree.pop（） ;
remainingOptions.remove（new Point（r，c））;
System.out.println（回到之前的决定）;
继续;
}
方向dir = ds.remove（0）;
System.out.println（connected+ dir.name（））;
remainingOptions.put（new Point（r，c），ds）;
土地nextState =新土地（州）;
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 =新方向[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;
}
}
}
公共土地（其他土地）{
BRIDGES_TO_BUILD = copy（other.BRIDGES_TO_BUILD）;
int R = BRIDGES_TO_BUILD.length;
int C = BRIDGES_TO_BUILD [0] .length;
BRIDGES_ALREADY_BUILT =新方向[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] =其他.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;
//越界
if（r< 0 || r> = R || c< 0 || c> = C）
返回null ;
//运动矢量
int [] [] motionVector = {{-1,0}，{0,1}，{1,0}，{0， -1}};
int i = Arrays.asList（Direction.values（））。indexOf（dir）;
//计算下一个
int [] out = new int [] {r + motionVector [i] [0]，c + motionVector [i] [1]};
r = out [0];
c = out [1];
//越界
if（r< 0 || r> = R || c< 0 || c> = C）
返回null ;
//返回
退出;
}
public int [] nextIsland（int r，int c，Direction dir）{
int [] tmp = next（r，c，dir）;
if（tmp == null）
返回null;
while（！IS_ISLAND [tmp [0]] [tmp [1]]）{
tmp = next（tmp [0]，tmp [1]，dir）;
if（tmp == null）
返回null;
}
返回tmp;
}
public boolean canBuildBridge（int r0，int c0，int r1，int c1）{
if（r0 == r1&& c0> c1）{
返回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）
返回false;
if（BRIDGES_TO_BUILD [r0] [c0] == 0）
返回false;
if（BRIDGES_TO_BUILD [r1] [c1] == 0）
返回false;
for（int i = c0; i< = c1; i ++）{
if（IS_ISLAND [r0] [i]）
继续;
if（BRIDGES_ALREADY_BUILT [r0] [i] == Direction.NORTH）
返回false;
}
}
if（c0 == c1）{
int [] tmp = nextIsland（r0，c0，Direction.SOUTH）;
if（tmp [0]！= r1 || tmp [1]！= c1）
返回false;
if（BRIDGES_TO_BUILD [r0] [c0] == 0 || BRIDGES_TO_BUILD [r1] [c1] == 0）
返回false;
for（int i = r0; i< = r1; i ++）{
if（IS_ISLAND [i] [c0]）
继续;
if（BRIDGES_ALREADY_BUILT [i] [c0] == Direction.EAST）
返回false;
}
}
//默认
返回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）
继续;
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;
}
退出;
}
private int [] [] copy（int [] [] other）{
int [] [] out = new int [other.length] [other。长度== 0？ 0：其他[0] .length];
for（int r = 0; r< other.length; r ++）
out [r] = Arrays.copyOf（其他[r]，其他[r] .length）;
退出;
}
public void connect（int r0，int c0，int r1，int c1）{
if（r0 == r1&& c0> c1）{
connect（r0，c1，r1，c0）;
返回;
}
if（c0 == c1&& r0> r1）{
connect（r1，c0，r0，c1）;
返回;
}
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]）
继续;
BRIDGES_ALREADY_BUILT [r0] [i] = Direction.EAST;
}
}
if（c0 == c1）{
for（int i = r0; i< = r1; i ++）{
if（IS_ISLAND [ i] [c0]）
继续;
BRIDGES_ALREADY_BUILT [i] [c0] = Direction.NORTH;
}
}
}
}
I have a android application called Islands and bridges also known as Hashiwokakero
The application uses A 2 Dimensional array that spawns the Islands randomly everytime the user restarts the game It form a Matrix with number from 0 to 4 where 0=null and 1-4 = Island There can be 2 bridges comming out of one Island to connect the other , The map at the moment is not solvable. To solve the game the user needs to connect the islands using bridges so if an island = 4 it needs 4 connection to it if an island = 2 it needs 2 connection and so on..
in my research i found out that the best algorithm to solve the game is to use Depth first search - article
I have looked at different question on here but can't seem to find a solution as my array is of type String rather than integer.
QUESTION how can apply a DFS algorithm to connect the islands?
here is a screenshot of my application.
This the function to create a easy map 4x4 matrix:
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;
}
}
}
}
}
解决方案
DFS could be applied to the game state.
Pseudo algorithm:
- pick a random (or by some other criterium) island that still needs bridges
- build a bridge between this island and one of its neighbors (obviously a neighbor that also needs a bridge)
- push the new state of the game (for instance the connectivity matrix of this graph) on a stack
- if the game contains inconsistencies, pop 1 item from the stack
- go back to step 1, using the top of the stack as the current state
As I mentioned, this is a piece of pseudo-code. You will need to refine it to handle edge-cases. You should also think about strategies to prevent the branching factor from becoming too large.
example (not thoroughly tested, not thoroughly debugged):
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();
}
I also wrote a utility class that handles the common operations on the piece of land on which bridges need to be built (like finding the next available island, checking whether a bridge can be built, etc)
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算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
