java - N Queens 所有解决方案，目前显示 1

Question

经过一个月的调试，我编写了这个程序，我终于让它工作了，但是它只打印 1 解决 8 皇后问题，有谁知道什么我可以做些什么来让它打印所有的解决方案？代码会很有帮助，但如果您能指出要更改或添加的内容，我也可以使用。

    import java.util.Scanner;
    public class Queens
    {
    // squares per row or column
    public static final int BOARD_SIZE = 8; 

    // used to indicate an empty square
    public static final int EMPTY = 0; 

    // used to indicate square contains a queen
    public static final int QUEEN = 1; 

    private int board[][]; // chess board

    public Queens() {
        // -------------------------------------------------
        // Constructor: Creates an empty square board.
        // -------------------------------------------------
        board = new int[BOARD_SIZE][BOARD_SIZE];
    }  // end constructor         

    public void clearBoard() {
        // -------------------------------------------------
        // Clears the board.
        // Precondition: None.
        // Postcondition: Sets all squares to EMPTY.
        // ------------------------------------------------- 
        for(int j = 1; j < 8; j++) 
        {
            for(int k = 1; k < 8; k++) //Sets every column in this row to 0
            {
                board[j][k] = 0;
            }
            //moves on to next row and repeats
        }
    }  // end clearBoard

    public void displayBoard() {
        // -------------------------------------------------
        // Displays the board.
        // Precondition: None.
        // Postcondition: Board is written to standard 
        // output; zero is an EMPTY square, one is a square 
        // containing a queen (QUEEN).
        // -------------------------------------------------
        placeQueens(1);
        int N = board.length;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == 1) 
                {
                    System.out.print("Q ");
                } 
                else 
                {
                    System.out.print("_|");
                }
            }
            System.out.println();
        }
    } // end displayBoard

    public boolean placeQueens(int column) {
        // -------------------------------------------------
        // Places queens in columns of the board beginning 
        // at the column specified.
        // Precondition: Queens are placed correctly in 
        // columns 1 through column-1.
        // Postcondition: If a solution is found, each 
        // column of the board contains one queen and method 
        // returns true; otherwise, returns false (no 
        // solution exists for a queen anywhere in column 
        // specified).
        // -------------------------------------------------
        if (column > BOARD_SIZE) {
            return true;  // base case
        } 
        else {
            boolean queenPlaced = false;
            int row = 1;  // number of square in column

            while ( !queenPlaced && (row <= BOARD_SIZE) )  {
                // if square can be attacked
                if (isUnderAttack(row, column)) {
                    ++row;  // consider next square in column
                } // end if
                else { // place queen and consider next column
                    setQueen(row, column);
                    queenPlaced = placeQueens(column+1);
                    // if no queen is possible in next column,
                    if (!queenPlaced) {
                        // backtrack: remove queen placed earlier
                        // and try next square in column
                        removeQueen(row, column);
                        ++row;
                    } // end if
                } // end if
            } // end while
            return queenPlaced;
        } // end if
    } // end placeQueens

    private void setQueen(int row, int column) {
        // --------------------------------------------------
        // Sets a queen at square indicated by row and 
        // column.
        // Precondition: None.
        // Postcondition: Sets the square on the board in a 
        // given row and column to QUEEN.
        // --------------------------------------------------
        row = index(row);
        column = index(column);
        board[row][column] = 1; //Queen placed on square
    }  // end setQueen

    private void removeQueen(int row, int column) {
        // --------------------------------------------------
        // Removes a queen at square indicated by row and
        // column.
        // Precondition: None.
        // Postcondition: Sets the square on the board in a 
        // given row and column to EMPTY.
        // --------------------------------------------------
        column = index(column);
        for(int x = 0; x < 8 ; x++)
        {
            if(board[x][column] == 1)
            {
                board[x][column] = 0;
                x = 8;      
            }
        }

    }  // end removeQueen

    private boolean isUnderAttack(int row, int column) {
        // --------------------------------------------------
        // Determines whether the square on the board at a 
        // given row and column is under attack by any queens 
        // in the columns 1 through column-1.
        // Precondition: Each column between 1 and column-1 
        // has a queen placed in a square at a specific row. 
        // None of these queens can be attacked by any other
        // queen.
        // Postcondition: If the designated square is under 
        // attack, returns true; otherwise, returns false.
        // --------------------------------------------------

        //Taking 1-8 & returning 0-7 to suite array
        row = index(row);
        column = index(column);

        //Checks the rows & columns
        //Rows
        for(int i = 0; i < column && i < 8 && row < 8; i++)
        {
            //If there's a queen in that row, the queen is under attack
            if(board[row][i] == 1)
            {
                return true;
            }
        }
        //Column

        for(int j = 0; j < row && j < 8 && column < 8; j++)
        {
            //If there's a queen in that column, the queen is under attack
            if(board[j][column] == 1)
            {
                return true;
            }
        }

        //Check diagonals
        for(int i = row, j = column; i >= 0 && j >= 0 && i < 8 && j < 8; i--, j--)
        {
            //checks upper diagonal
            if(board[i][j] == 1)
            {
                return true;
            }
        }

        for(int i = row, j = column; i < board.length && j >= 0 && i < 8 && j < 8; i++, j--)
        {
            //checks lower diagonal
            if(board[i][j] == 1)
            {
                return true;
            }
        }
        //At this point the Queen is not being attacked
        return false;
    } // end isUnderAttack

    private int index(int number) {
        // --------------------------------------------------
        // Returns the array index that corresponds to
        // a row or column number.
        // Precondition: 1 <= number <= BOARD_SIZE.
        // Postcondition: Returns adjusted index value.
        // --------------------------------------------------
        return number - 1;
    }// end index

    public static void main(String[] args)
    {
        Queens eight = new Queens();
        eight.displayBoard();
    }
} // end Queens

Answer 1

displayBoard是您的驾驶习惯；不要让它在显示一个解决方案后停止，而是将其包装在一个循环中，只要 placeQueens 能够找到新的解决方案，该循环就会继续下去。

这意味着您需要调整placeQueens以从之前的棋盘状态继续。它已经在很大程度上做到了这一点；您只需要处理它到达最后一列的情况。例如，将第 8 个皇后向下移动一格，然后从上次停下的位置继续前进，或者返回到第 7 个皇后的下一个合法位置(因为您知道第 8 个皇后没有其他合法位置)。

在执行此操作时，您需要稍微更改这两个例程之间的接口(interface)，以便 placeQueens 不仅可以返回每个解决方案，还可以返回全部完成条件。这告诉 displayBoard 跳出循环(您添加的新包装器)。

这些描述足以让您继续前进吗？

<小时/>

在“不是真的”评论后进行编辑...

也许最容易编写的包装器是在 displayBoard 中。在顶部，您有 placeQueens(1)，请改为使用

col = 1
while(placeQueens(col)) {
   ... print the board as usual
   ... remove 8th queen; mark its position as unusable (say, with a value of -1)
   col = 8
}

调整 placeQueens，以便它从上次停止的位置继续:它将希望将第 8 个皇后放在同一个位置。当它发现该位置被标记为不可用时，重置标记并回溯到第 7 个皇后。此操作将让它继续并找到所有解决方案。

有更简洁的方法可以做到这一点，但我认为这个方法足以保留您当前的组织。理想情况下，您应该有一个在放置和打印过程中循环的驱动程序，但这主要是命名和上层组织的问题。

这能让你移动得足够好吗？