试图找出如何让这个 n 皇后方法在获得所有解决方案后停止，有哪些方法可以解决这个问题？

Question

我正在使用堆栈而不是递归调用来解决 N 皇后问题，以便找到 N 皇后的解决方案总数。我相信我的程序可以工作，除了我无法弄清楚如何跳出找到解决方案的循环。有哪些方法可以解决这个问题？

这是我的一门计算机科学类，使用 java。我已经尝试过我朋友的建议，在当前行位于板内时暂时设置条件，但这导致在找到解决方案之前停止解决方案搜索时出现一些问题。我还尝试在堆栈大小为 1 时跳出循环，但这仅在 N = 4 时有效，不适用于更大的 N 值，该程序也可能不适用于 N > 4，尚未测试还没有。

当 N = 5 且

时出现 EmptyStackException

Exception in thread "main" java.util.EmptyStackException
    at java.base/java.util.Stack.peek(Stack.java:102)
    at java.base/java.util.Stack.pop(Stack.java:84)
    at Assignment22.stacker(Assignment22.java:61)
    at Assignment22.main(Assignment22.java:11)

// gets number of solutions to N Queens
public static int stacker(boolean[][] board, int numQueens) {
        Stack<Integer> queensPos = new Stack<Integer>();
        int row = 0;
        int col = 0;
        int numSolutions = 0;

        // need to figure out how to tell program to
        // go back to previous row and remove queen
        // if col = 3 and row = 1, queen will always be placed there
        // however if queen is placed there, there is no solution
        // if row being worked on is in the board
        while (row <= board.length) {
            // if you have no more queens to place
            if (numQueens == 0) {
                // you have a solution
                for (int i = 0; i < queensPos.size(); i++) {
                    System.out.println(queensPos.get(i));
                }
                numSolutions += 1;
                // go back to last row
                row -= 1;
                // remove queen
                col = queensPos.pop();
                board[row][col] = false;
                // go back one row
                //row -= 1;
                numQueens += 1;
                col += 1;

            } else {
                // if there is a conflict and column is within board
                if (IsConflictPresent(board, row, col) && col < board[row].length - 1) {
                    // shift queen rightward
                    col += 1;
                // if column is out of board
                } else if (IsConflictPresent(board, row, col) && col == board[row].length - 1) {
                    // look at value of column, if it is at end of board
                    // go back to previous row
                    // looks at top of stack
                    col = queensPos.pop();  // <- EmptyStackException occurs here

                    if (row > 0) {
                        row -= 1;
                    }
                    board[row][col] = false;
                    numQueens += 1;
                    // attempt to solve problem where queen at end of 2nd row would keep getting placed
                    // appears to be working
                    if (!(col < board[row].length - 1)) {
                        col = queensPos.pop();

                        row -= 1;
                        board[row][col] = false;
                        numQueens += 1;
                        col += 1;
                    } else {
                        col += 1;
                    }
                } else  {
                // if queen can be placed
                    // place queen at row, col
                    board[row][col] = true;
                    queensPos.push(col);
                    numQueens -= 1;
                    // move to next row
                    row += 1;
                    // start at beginning of row
                    col = 0;

                    // when the below code is put in, EmptyStackException occurs when numQueens = 5
                    if (queensPos.size() == 1) {
                        row -= 1;
                        col = queensPos.pop();
                        numQueens += 1;
                    } 

                }
            }

        }
        return numSolutions;
    }

public static boolean IsConflictPresent(boolean[][] boardToCheck, int row, int col) {

        // figure out how to check one diagonal

        int i,j;
        int N = boardToCheck.length;
        // use 4 for loops
        // check on left side of row specified
        for (i = 0; i <= col; i++) {
            if (boardToCheck[row][i])
            {
                return true;
            }
        }

        for (i = 0; i < boardToCheck[row].length - 1; i++) {
            if (boardToCheck[i][col]) {
                return true;
            }
        }

        // to check diagonal, start at row 0 column 0, go up to row and column specified
        // upper diag on left side

        for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (boardToCheck[i][j]) {
                return true;
            }
        }
        // upper right diagonal check
        for (i = row, j = col; i >= 0 && j < N; i--, j++) {
            if (boardToCheck[i][j]) {
                return true;
            }
        }
        // lower diagonal on left side
        for (i = row, j = col; j >= 0 && i < N; i++, j--) {
            if (boardToCheck[i][j]) {
                return true;
            }
        }
        // lower diagonal on right side
        for (i = row, j = col; j < N && i < N; i++, j++) {
            if (boardToCheck[i][j]) {
                return true;
            }
        }


        return false;
    }

我希望程序最终会停止，但我得到了一个无限循环，并且，根据我尝试过的修复，ArrayIndexOutOfBoundsException 或 EmptyStackException

Answer 1

我发现的主要问题是当 N > 4 时，皇后不能放在最后一列的任何地方，所以我修改了这个条件

if (!(col < board[row].length - 1)) {
                        col = queensPos.pop();

                        row -= 1;
                        board[row][col] = false;
                        numQueens += 1;
                        col += 1;
                    } else {
                        col += 1;
                    }

并添加了行 > 0

的条件

最终堆垛机方法：

    public static int stacker(boolean[][] board, int numQueens) {
        Stack<Integer> queensPos = new Stack<Integer>();
        int row = 0;
        int col = 0;
        int numSolutions = 0;
        int colLastUsed = 0;
        // need to figure out how to tell program to
        // go back to previous row and remove queen
        // if col = 3 and row = 1, queen will always be placed there
        // however if queen is placed there, there is no solution
        // if row being worked on is in the board
        while (row <= board.length) {
            // if you have no more queens to place
            if (numQueens == 0) {
                // you have a solution
                for (int i = 0; i < board.length; i++) {
                    for (int j = 0; j < board[i].length; j++) {
                        if (board[i][j]) {
                            System.out.print("Q");
                        } else {
                            System.out.print("*");
                        }
                    }
                    System.out.println();
                }
                System.out.println();
                /*for (int i = 0; i < queensPos.size(); i++) {
                    System.out.print(queensPos.get(i) +" ");
                }
                System.out.println();*/
                numSolutions += 1;
                // go back to last row
                row -= 1;
                // remove queen
                col = queensPos.pop();
                board[row][col] = false;
                // go back one row
                //row -= 1;
                numQueens += 1;
                if (col < board.length - 1) {
                    // add one to col if it is not at end of row
                    col += 1;
                } else {
                    // go back another row
                    row -= 1;
                    col = queensPos.pop();

                    board[row][col] = false;

                    numQueens += 1;
                    col += 1;
                }
            // if there is a conflict and column is within board

            } else {
                if (col == board[row].length && row == 0) {
                    break;
                } else if (IsConflictPresent(board, row, col) && col < board[row].length - 1) {
                    // shift queen rightward
                    col += 1;
                    // if column is out of board
                } else if (IsConflictPresent(board, row, col) && col == board[row].length - 1) {
                    // look at value of column, if it is at end of board
                    // go back to previous row
                    // looks at top of stack
                    col = queensPos.pop();

                    if (row > 0) {
                        row -= 1;
                    }
                    board[row][col] = false;
                    numQueens += 1;
                    // attempt to solve problem where queen at end of 2nd row would keep getting placed
                    // appears to be working
                    if (!(col < board[row].length - 1) && row > 0) {
                        col = queensPos.pop();

                        row -= 1;
                        board[row][col] = false;
                        numQueens += 1;
                        col += 1;
                    } else {
                        col += 1;
                    }
                    // how to check to see if the column number you used
                } else {
                    // if queen can be placed
                    // place queen at row, col
                    board[row][col] = true;
                    queensPos.push(col);
                    numQueens -= 1;
                    // move to next row
                    row += 1;
                    // start at beginning of row
                    col = 0;

                }
            }

        }
        return numSolutions;
    }

试图找出如何让这个 n 皇后方法在获得所有解决方案后停止，有哪些方法可以解决这个问题？

Trying to figure out how to make this n queens method stop once it gets all all of the solutions, what are some ways to approach this problem?

java

stack

n-queens