4

8 クイーン問題のコーディングに問題があります。私はそれを解決するのに役立つクラスをコーディングしましたが、何らかの理由で何か間違っています。私は何が起こるべきかをある程度理解しています。

また、再帰を使用して解決する必要がありますが、私が読んだバックトラッキングの使用方法がわからないため、位置が正当かどうかを確認するメソッドで使用しました。

私のボードはString [] [] board = { { "O", "O"...8行8列のetcです。概念的に間違っている場合や、Java の重大な間違いを犯している場合は、そう言ってください :D ありがとう!

public void solve () {
    int Queens = NUM_Queens - 1;
    while (Queens > 0) {
        for (int col = 0; col < 8; col++) {
            int row = -1;
            boolean c = false;
            while (c  = false && row < 8) {
                row ++;
                c = checkPos (row, col);
            }
            if (c == true) {
                board[row][col] = "Q";
                Queens--;
            }
            else 
                System.out.println("Error");
        }
    }
    printBoard ();
}

// printing the board
public void printBoard () {
    String ret = "";
    for (int i = 0; i < 8; i++) {
        for (int a = 0; a < 8; a++)
            ret += (board[i][a] + ", ");
        ret += ("\n");
    }
    System.out.print (ret);
}

// checking if a position is a legitimate location to put a Queen
public boolean checkPos (int y, int x) {
    boolean r = true, d = true, u = true, co = true;
    r = checkPosR (y, 0);
    co = checkPosC (0, x);
    int col = x;
    int row = y;
    while (row != 0 && col != 0 ) { //setting up to check diagonally downwards
        row--;
        col--;
    }
    d = checkPosDD (row, col);
    col = x;
    row = y;
    while (row != 7 && col != 0 ) { //setting up to check diagonally upwards
        row++;
        col--;
    }
    d = checkPosDU (row, col);
    if (r = true && d = true && u = true && co = true)
        return true;
    else
        return false;
}

// checking the row
public boolean checkPosR (int y, int x) {
    if (board[y][x].contentEquals("Q"))
            return false;
    else if (board[y][x].contentEquals("O") && x == 7)
        return true;
    else //if (board[y][x].contentEquals("O"))  
        return checkPosR (y, x+1);
}

// checking the column
public boolean checkPosC (int y, int x) {
    if (board[y][x].contentEquals("Q"))
            return false;
    else if (board[y][x].contentEquals("O") && y == 7)
        return true;
    else //if (board[y][x].contentEquals("O"))  
        return checkPosR (y+1, x);
}

// checking the diagonals from top left to bottom right
public boolean checkPosDD (int y, int x) {
    if (board[y][x].contentEquals("Q"))
        return false;
    else if (board[y][x].contentEquals("O") && (x == 7 || y == 7))
        return true;
    else //if (board[y][x].contentEquals("O"))  
        return checkPosR (y+1, x+1);
}

 // checking the diagonals from bottom left to up right
public boolean checkPosDU (int y, int x) {
    if (board[y][x].contentEquals("Q"))
        return false;
    else if (board[y][x].contentEquals("O") && (x == 7 || y == 0))
        return true;
    else //if (board[y][x].contentEquals("O"))  
        return checkPosR (y-1, x+1);
    }
}
4

2 に答える 2

1

これは宿題なので、解決策ですが、コードではありません。

単一の列で発生する必要があることのみを処理するメソッドを作成してみてください。これは、再帰を使用することになっている場所です。解決策が存在するかどうかを確認してバックトラックを行い、存在しない場合は、最後の変更を取り消して (つまり、クイーンの位置を変更して)、もう一度やり直してください。問題の 1 つの部分 (1 つの列) だけに注目すると、すべての列について同時に考えるよりもはるかに簡単になります。

Quetzalcoatl が指摘しているようfalseに、最初のループで変数に代入しています。あなたはおそらくそれをしたくないでしょう。コンパイラですべての警告を常に有効にし (-Xlint を指定して javac を実行)、それらを修正する必要があります。

于 2013-03-05T14:55:52.433 に答える
-1

あなたはある種のブルートフォースを試みていますが、すでに述べたように、再帰はありません。あなたのプログラムは、最初に可能な位置にクイーンを置こうとします。しかし、結局解決策は見つかりません。したがって、最初の仮定 (最初のクイーンの位置) は無効です。この状態に戻らなければなりません。また、checkPos(x,y) が true ではなく false であると想定する必要があります。

ここでいくつかのヒント:

  1. 前述のように、NPEint[N] queensはより適切な表現です。
  2. 位置は一意でなければならないため、sum(queens) は 0+1+2+3+4+5+6+7=28 でなければなりません。
  3. 新しいクイーンの位置だけをチェックするのではなく、全体の状況をチェックすることができます。N^2 のすべての (i,j) \in クイーン(i) = j に対して、abs(ki) == abs(lj) で (k,l) != (i,j) が存在しない場合は有効です。
于 2013-03-05T11:33:30.587 に答える