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

Question

我正在使用堆栈而不是递归调用来解决 N 皇后问题，以便找到 N 皇后的解决方案总数。我相信我的程序是有效的，只是我无法弄清楚如何打破寻找解决方案的循环。有哪些方法可以解决这个问题？这是我的计算机科学课程之一，使用 java。我已经尝试过我的朋友建议的方法，即在当前行位于棋盘内时暂时满足条件，但这导致在找到解决方案之前停止解决方案搜索出现一些问题。我还尝试在堆栈大小为1时跳出循环，但这仅在N = 4时有效，不适用于较大的N值，该程序也可能不适用于N > 4，尚未测试过还没有。当 N = 5 时以及当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)我预计程序最终会停止，但我遇到了无限循环，并且根据我尝试过的修复，出现 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;

                    }

并添加了 row > 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;

    }