1

宿題のプロジェクトを完了しようとしましたが、バグを見つける手助けを求めています。バックトラッキング アルゴリズムを使用して、N クイーン問題のすべての解を見つけています。私の主な関心事は、スタック クラス内にある競合メソッドです。その目的は、渡された Queen オブジェクト (conflict メソッドのパラメーター 1) がボード上の他のクイーンと同じ行、列、または対角線にあるかどうかを検出することです。conflict メソッドに渡された Queen オブジェクトは Queen クラス内に格納され、その場所は Point クラスのインスタンスを使用して記録されます。私のコードでは、私が作成した Queen クラスで public int getRow() と public int getColumn() の 2 つのメソッドを使用しています。どちらも int を返します。2 番目のパラメーターは、board という名前の 2 次元配列 (または配列の配列) です。すでにボードにあるクイーンは、ブール値 true でこの配列に示されます。

Solution.n は、別のクラスの static int 変数への参照です。その値はボードの端を示します。例...8-Queens 問題の場合、サイズ 8 の 2 次元配列を作成します。Solution.n は、2 次元配列の最後のインデックスと等しくなるように 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

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 に答える