java:使用深度优先搜索实现8皇后

Question

我试图实现8皇后，使用深度搜索任何初始状态--对于空板(在板上没有皇后)，它很好地工作，但是如果有解决方案，我需要它为初始状态工作，如果这个初始状态没有解决方案，它将打印出没有解决方案。

这是我的代码：

public class depth {
   public static void main(String[] args) {
       //we create a board
       int[][] board = new int[8][8];
       board [0][0]=1;
       board [1][1]=1;
       board [2][2]=1;
       board [3][3]=1;
       board [4][4]=1;
       board [5][5]=1;
       board [6][6]=1;
       board [7][7]=1;

       eightQueen(8, board, 0, 0, false);
       System.out.println("the solution as pair");
       for(int i=0;i<board.length;i++){
           for(int j=0;j<board.length;j++)
               if(board[i][j]!=0)

               System.out.println("  ("+i+" ,"+j +")");
       }
       System.out.println("the number of node stored in memory "+count1);
   }
      public static int count1=0;
     public static void eightQueen(int N, int[][] board, int i, int j, boolean found) {

    long startTime = System.nanoTime();//time start

    if (!found) {
        if (IsValid(board, i, j)) {//check if the position is valid
            board[i][j] = 1;

            System.out.println("[Queen added at (" + i + "," + j + ")");
            count1++;
            PrintBoard(board);


            if (i == N - 1) {//check if its the last queen
                found = true;
                PrintBoard(board);
                double endTime = System.nanoTime();//end the method time

                double duration = (endTime - startTime)*Math.pow(10.0, -9.0);
                System.out.print("total Time"+"= "+duration+"\n");
            }
            //call the next step
            eightQueen(N, board, i + 1, 0, found);
        } else {

            //if the position is not valid & if reach the last row we backtracking
            while (j >= N - 1) {
                int[] a = Backmethod(board, i, j);
                i = a[0];
                j = a[1];

                System.out.println("back at (" + i + "," + j + ")");
                PrintBoard(board);
            }
            //we do the next call
            eightQueen(N, board, i, j + 1, false);
        }
    }

}

public static int[] Backmethod(int[][] board, int i, int j) {
    int[] a = new int[2];
    for (int x = i; x >= 0; x--) {
        for (int y = j; y >= 0; y--) {
            //search for the last queen
            if (board[x][y] != 0) {
                //deletes the last queen and returns the position
                board[x][y] = 0;
                a[0] = x;
                a[1] = y;
                return a;
            }
        }
    }
    return a;
}

public static boolean IsValid(int[][] board, int i, int j) {

    int x;
    //check the queens in column
    for (x = 0; x < board.length; x++) {
        if (board[i][x] != 0) {
            return false;
        }
    }
    //check the queens in row
    for (x = 0; x < board.length; x++) {
        if (board[x][j] != 0) {
            return false;
        }
    }
    //check the queens in the diagonals
    if (!SafeDiag(board, i, j)) {
        return false;
    }
    return true;
}

public static boolean SafeDiag(int[][] board, int i, int j) {

    int xx = i;
    int yy = j;
    while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) {
        if (board[xx][yy] != 0) {
            return false;
        }
        yy++;
        xx++;
    }
    xx = i;
    yy = j;
    while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) {
        if (board[xx][yy] != 0) {
            return false;
        }
        yy--;
        xx--;
    }
    xx = i;
    yy = j;
    while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) {
        if (board[xx][yy] != 0) {
            return false;
        }
        yy--;
        xx++;
    }
    xx = i;
    yy = j;
    while (yy >= 0 && xx >= 0 && xx < board.length && yy < board.length) {
        if (board[xx][yy] != 0) {
            return false;
        }
        yy++;
        xx--;
    }
    return true;
}
public static void PrintBoard(int[][] board) {
    System.out.print(" ");
    for (int j = 0; j < board.length; j++) {
        System.out.print(j);
    }
    System.out.print("\n");
    for (int i = 0; i < board.length; i++) {
        System.out.print(i);
        for (int j = 0; j < board.length; j++) {
            if (board[i][j] == 0) {
                System.out.print(" ");
            } else {
                System.out.print("Q");
            }
        }
        System.out.print("\n");
    }
}


}

例如，对于这个初始状态，它给出了以下错误：

Exception in thread "main" java.lang.StackOverflowError

我被卡住了，我认为错误是无限需要如何解决这个问题的方法。

任何想法都会有帮助，谢谢。

注:宽是二维数组，当我把(1)表示在这一点上的皇后。

note2:我们把初始状态放在下面的工作状态中：

       board [0][0]=1;
       board [1][1]=1;
       board [2][2]=1;
       board [3][3]=1;
       board [4][4]=1;
       board [5][5]=1;
       board [6][6]=1;
       board [7][1]=1; 

Answer 1

编辑:添加条件输出提示。

在@StephenC的回答中添加：

这是一段非常复杂的代码，尤其是如果您不熟悉Java编程的话。

我执行了您的代码，它一遍又一遍地输出这段代码。

back at (0,0)
 01234567
0
1 Q
2  Q
3   Q
4    Q
5     Q
6      Q
7       Q
back at (0,0)

然后用这个崩溃

Exception in thread "main" java.lang.StackOverflowError
    at java.nio.Buffer.<init>(Unknown Source)
    ...
    at java.io.PrintStream.print(Unknown Source)
    at java.io.PrintStream.println(Unknown Source)
    at Depth.eightQueen(Depth.java:56)
    at Depth.eightQueen(Depth.java:60)
    at Depth.eightQueen(Depth.java:60)
    at Depth.eightQueen(Depth.java:60)
    at Depth.eightQueen(Depth.java:60)
    ...

我的第一反应总是添加一些System.out.println(...)来找出问题出在哪里，但这在这里行不通。

我看到的唯一两种选择是

• 熟悉调试器并使用它逐步完成并分析为什么它从不停止循环
• 把它拆开伙计！你怎么能希望在不把它分解成可消化的块的情况下解决这样一个巨大的问题？

更不用说，八皇后的概念一开始就很复杂。

另一种想法是：

System.out.println()不像当前实现的那样有用，因为它有无限的输出。调试器是更好的解决方案，但另一种选择是以某种方式限制输出。例如，在顶部创建一个计数器。

private static final int iITERATIONS = 0;

而不是

System.out.println("[ANUMBERFORTRACING]: ... USEFUL INFORMATION ...")

使用

conditionalSDO((iITERATIONS < 5), "[ANUMBERFORTRACING]: ... USEFUL INFORMATION");

以下是功能：

private static final void conditionalSDO(boolean b_condition, String s_message)  {
   if(b_condition)  {
       System.out.println(s_message);
   }
}

另一种选择是不限制输出，而是限制将其写入文件。

我希望这些信息对你有帮助。

(注意:我编辑了OP的代码以便可编译。)

Answer 2

您询问了关于如何解决这个问题的想法(与解决方案不同！)下面有几个提示：

提示#1：

如果您在递归程序中获得一个StackOverflowError，它可能意味着两件事中的一件：

• 你的问题太“深”了
• 您的代码中有一个bug，导致它无限递归。

在这种情况下，问题的深度很小(8)，所以这必须是一个递归错误。

提示2：

如果检查堆栈跟踪，将看到堆栈中每个调用的方法名称和行号。这..。还有一些想法..。应该可以帮助您了解代码中的递归模式(如已实现的！)。

提示#3：

用调试器卢克..。

提示#4：

如果你想让别人读你的代码，那就多注意你的风格。您的缩进在最重要的方法中搞砸了，您已经犯下了(IMO)不可饶恕的罪过，即忽略Java样式标识符的规则。方法名称必须以小写字母开头，类名必须以大写字母开头。

(我很快就停止读你的代码了.(原则上)

Answer 3

尝试在IsValid所在的行中修改您的方法for (x = 0; x < board.length - 1; x++)。

public static boolean IsValid(int[][] board, int i, int j) {
    int x;
    //check the queens in column
    for (x = 0; x < board.length - 1; x++) {
        if (board[i][x] != 0) {
            return false;
        }
    }
    //check the queens in row
    for (x = 0; x < board.length - 1; x++) {
        if (board[x][j] != 0) {
            return false;
        }
    }
    //check the queens in the diagonals
    if (!SafeDiag(board, i, j)) {
        return false;
    }
    return true;
}