N-Queens使用堆栈，找不到错误。

Question

我已经尝试完成我的家庭作业项目，并正在寻求帮助找到一个漏洞。我使用回溯算法来寻找N-皇后问题的所有解。我主要关心的是我的冲突方法--它在堆栈类中。它的目的是检测要传递的Queen对象(冲突方法的参数1)是否与董事会上的任何其他皇后位于同一行、列或对角线上。传入冲突方法的皇后对象存储在queen类中，它的位置通过Point类的实例进行记录。我的代码在我创建的Queen类中使用了两个方法，即public int getRow()和public int getColumn()。两者都返回一个int。第二个参数是一个名为board的2d数组(或数组数组)。已在板上的皇后区在此数组中表示，布尔值为true。false的布尔值表示板上的空正方形。

N是对另一个类中的静态int变量的引用。它的值表示板的边缘。Example...for 8-Queens问题，我们创建了一个大小为8的2d数组。Solution.n被减少1，等于2d数组的最后一个索引。

以下是代码：

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;
}

我确信这个代码片段包含一个bug，但是如果我错了，那么我很抱歉浪费了你的时间。

你的帮助将不胜感激。谢谢！:D

Answer 1

这里有几个小bugs -例如，您有从0到Solution.n的循环，包含这些循环，而它们应该转到Solution.n-1。然而，大多数错误可以通过选择更合适的数据结构来消除。

想想看:你不需要一个完整的NxN董事会来决定女王的位置：

• 每排有一个皇后，所以女王的号码是它的一行。
• 每个列都有一个皇后，因此您需要一个boolean[N]数组来知道使用了哪些行。
• 每个提升对角线有一个皇后，所以您需要一个boolean[2N-1]数组来知道哪个提升对角线被取了。
• 每个下降的对角线有一个皇后，所以您需要一个boolean[2N-1]数组来知道哪个下降的对角线被取下来。 boolean[]列=新booleanN；boolean[]升序=新布尔烯2*N1；boolean[]降序=新布尔烯2*N1；

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

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

就这样-不需要循环！现在，您可以使用这三个数组而不是正方形板来编码您的回溯算法。

Answer 2

这个答案不会解决您的问题，因为我不相信您的错误出现在您粘贴的代码中，但是下面是您的代码，编写得更接近于如何编写它：

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

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

// returns true if the position is valid given the board size
//  (as defined by Solution)
private boolean validPosition(int row, int col)
{
    if(0 > row || row > Solution.n){ return false; }
    if(0 > col || col > Solution.n){ return false; }
    return true;
}

// returns true when diagonal is safe
private boolean checkDiagonal(Queen x, boolean [][] board) 
{
    int row, col;

    // Down Left
    row = x.getRow();                           // "Start" on current position
    col = x.getColumn();
    while(true)
    {
        row--; col--;                           // Take a step in the direction
        if(!validPosition(row, col)){ break; }  // Stop if we've left the board
        if(board[row][col]){ return false; }    // Check whether it's occupied
    }

    // Down Right
    row = x.getRow();
    col = x.getColumn();
    while(true)
    {
        row--; col++;
        if(!validPosition(row, col)){ break; }
        if(board[row][col]){ return false; }
    }

    // Up Right
    row = x.getRow();
    col = x.getColumn();
    while(true)
    {
        row++; col++;
        if(!validPosition(row, col)){ break; }
        if(board[row][col]){ return false; }
    }

    // Up Left
    row = x.getRow();
    col = x.getColumn();
    while(true)
    {
        row++; col--;
        if(!validPosition(row, col)){ break; }
        if(board[row][col]){ return false; }
    }
    return true;
}

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

}

它简化了许多逻辑，添加了一个辅助函数validPosition()，并清理了一些测试和循环。