1

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

Solution.n 是对另一个类中的静态 int 变量的引用。它的值表示棋盘的边缘。示例...对于 8-Queens 问题，我们创建一个大小为 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

4

2 回答 2

2

你有几个小错误 - 例如，你有循环从0to Solution.n，包括在内，而他们应该去Solution.n-1。然而，大多数错误可以通过选择更合适的数据结构来消除。

想一想：你不需要一个完整的NxN板来决定皇后的位置：

  • 每行有一个皇后，所以皇后的数量就是它的行。
  • 每列有一个皇后，所以你需要一个数组boolean[N]来知道哪些行被占用。
  • 每个上升对角线都有一个皇后，所以你需要一个数组boolean[2N-1]来知道哪些上升对角线被采用。

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

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

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

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

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

于 2013-09-27T01:49:05.237 回答
0

这个答案不能解决你的问题，因为我不相信你的错误是在你粘贴的代码中，但这是你的代码，写得更接近我的写法：

// 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()，并清理了一些测试和循环。

于 2013-09-27T02:06:11.370 回答