java - N-皇后使用堆栈，找不到错误

Question

我已尝试完成我的作业项目，并正在寻求帮助查找错误。我正在使用回溯算法来查找 N 皇后问题的所有解决方案。我主要关心的是我的冲突方法 - 它位于堆栈类内。其目的是检测正在传递的皇后对象(冲突方法的参数 1)是否与棋盘上的任何其他皇后位于同一行、列或对角线上。传递到冲突方法的皇后对象存储在 Queen 类中，并借助 Point 类的实例记录其位置。我的代码使用我创建的 Queen 类中的两个方法:public int getRow() 和 public int getColumn()。两者都返回一个 int。第二个参数是一个名为 board 的二维数组(或数组的数组)。棋盘上已经存在的皇后在此数组中用 boolean 值 true 表示。 boolean 值 false 表示棋盘上有一个空方 block 。

Solution.n 是对另一个类中静态 int 变量的引用。它的值表示棋盘的边缘。示例...对于 8-皇后问题，我们创建一个大小为 8 的二维数组。Solution.n 减 1 以等于二维数组的最后一个索引。

这是代码:

public boolean conflict(Queen x, boolean [][] board) //conflict method
{
    if(checkColumn(x, board) == false)
        return true; //conflict
    else if(checkRow(x, board) == false)
        return true; //conflict
    else if(checkDiagonal(x, board) == false )
        return true; //conflict
    else
        return false; //no conflict on board
}



private boolean checkColumn(Queen x, boolean [][] board)//returns true when column is safe
{
    int col = x.getColumn();
    for(int row = 0; row <= Solution.n; row++)
    {
        if(board[row][col] == true) //queen is in this column
        {
            return false;
        }
    }
    return true;
}

private boolean checkRow(Queen x, boolean [][] board) //returns true when row is safe
{
    int row = x.getRow();
    for(int col = 0; col <= Solution.n; col++)
    {
        if(board[row][col] == true) //queen is in this row
        {
            return false;
        }
    }
    return true;
}

private boolean checkDiagonal(Queen location, boolean [][] board) //returns true when diagonal is safe
{
    int row, col;
    row = location.getRow() - 1;
    col = location.getColumn() - 1;
    while(row >=0 && col >= 0) //iterate down-left
    {
        if(board[row][col] == true) //queen found?
        {
            return false;
        }
        row--;
        col--;
    }
    row = location.getRow() - 1;
    col = location.getColumn() + 1;
    while(row != -1 && col <= Solution.n) //iterate down-right
    {
        if(board[row][col] == true) //queen found?
        {

            return false;
        }
        row--;
        col++;
    }
    row = location.getRow() + 1;
    col = location.getColumn() + 1;
    while(row <= Solution.n && col <= Solution.n) //iterate up-right
    {
        if(board[row][col] == true) //queen found?
        {
            return false;
        }
        row++;
        col++;
    }
    row = location.getRow() +1;
    col = location.getColumn()-1;
    while(row <= Solution.n && col != -1) //iterate up-left
    {
        if(board[row][col] == true) //queen found?
        {
            return false;
        }
        row++;
        col--;
    }
    return true;
}

我确信这段代码包含一个错误，但如果我错了，那么我为浪费您的时间而道歉:P

我们将非常感谢您的帮助。谢谢! :D

Answer 1

其中有几个小错误 - 例如，您有从 0 到 Solution.n(包含在内)的循环，而它们应该转到 解决方案.n-1。然而，大多数错误可以通过选择更合适的数据结构来消除。

想一想:您不需要完整的 NxN 棋盘来决定皇后的位置:

• 每行有一个皇后，因此皇后的编号就是该行。
• 每列有一个皇后，因此您需要一个 boolean[N] 数组来了解占用了哪些行。
• 每个升对角线有一个皇后，因此您需要一个 boolean[2N-1] 数组来了解采用了哪些升对角线。

• 每个降对角线有一个皇后，因此您需要一个 boolean[2N-1] 数组来知道采用哪些降对角线。

  boolean 值[]列=新 boolean 值[N]； boolean 值[]升序=新 boolean 值[2*N-1]；boolean[] 降序 = new boolean[2*N-1];

此时您已获得所需的一切:您需要三个 boolean 线性数组，而不是一个方形 boolean[N][N] 数组。这也可以让您更快地进行检查:

int c = x.getColumn();
int r = x.getRow();
boolean conflict = columns[c]
                || ascending[r+c]
                || descending[N-r+c];

就是这样 - 不需要循环!现在您可以使用这三个数组而不是方板来编写回溯算法。