3
ボード全体を占有するためにチェスボードに8つの司教を設定するプログラムを書く仕事があります。最初の解決策が見つかったら、それは終了し、すべてを印刷します。ここに私の書かれたコードはJavaであり、私はバックトラックを使ってそれを仕上げることに苦労している（その場所はコードにコメントされている）。8ボード全体を占領する司教[バックトラック]
/*
* 0 - not occupied square
* 1 - bishop standing square
* 2 - occupied square (diagonal)
*/
public class BishopsBT {
public int [][] solution;
final int N = 8; // number of squares in column and row (chess board)
final int solved = 120; //Sum of 1's and 2's in case of all occupied board
int sum; //current sum of board
public BishopsBT(){
solution = new int [N][N] ;
}
public void solve() {
if(placeBishops(0)){
//print the result
clear(); // clears all 2's
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(" " + solution[i][j]);
}
System.out.println();
}
} else{
System.out.println("NO SOLUTION EXISTS");
}
}
public boolean placeBishops (int bishop){
for (int row = 0; row < N; row++) {
// check if bishop can be placed
if (canPlace(solution, row, bishop)) {
// place the bishop
solution[row][bishop] = 1;
}
}
if (allSpaceOccupied()) {
return true;
} else {
// SOME BACKTRACKING CODE HERE
return false;
}
}
// check if bishop can be placed at matrix[row][column]
public boolean canPlace(int[][] matrix, int row, int column) {
// we need to check all diagonals
// whether no bishop is standing there
for (int i = row, j = column; i >= 0 && j >= 0; i--, j--) {
if (matrix[i][j] == 1) {
return false;
}
}
for (int i = row, j = column; i >= 0 && j < matrix.length; i--, j++) {
if (matrix[i][j] == 1) {
return false;
}
}
for (int i = row, j = column; i < matrix.length && j >= 0; i++, j--) {
if (matrix[i][j] == 1) {
return false;
}
}
for (int i = row, j = column; i < matrix.length && j < matrix.length; i++, j++) {
if (matrix[i][j] == 1) {
return false;
}
}
// if we are here that means we are safe to place Bishop
return true;
}
public boolean allSpaceOccupied() {
// clears previously occupied space
clear();
// occupies new space
for (int i = 0; i < solution.length; i++) {
for (int j = 0; j < solution.length; j++) {
if (solution[i][j] == 1) diagonalOccupy(i,j);
}
}
sum = 0;
// counts sum of occupied space
for (int i = 0; i < solution.length; i++) {
for (int j = 0; j < solution.length; j++) {
sum += solution [i][j];
}
}
if (sum == solved) return true;
// else
return false;
}
public void diagonalOccupy(int row, int column) {
// writes 2 in each bishop's occupied square
for (int i = row, j = column; i >= 0 && j >= 0; i--, j--) {
if (solution[i][j] == 0) {
solution[i][j] = 2;
}
}
for (int i = row, j = column; i >= 0 && j < solution.length; i--, j++) {
if (solution[i][j] == 0) {
solution[i][j] = 2;
}
}
for (int i = row, j = column; i < solution.length && j >= 0; i++, j--) {
if (solution[i][j] == 0) {
solution[i][j] = 2;
}
}
for (int i = row, j = column; i < solution.length && j < solution.length; i++, j++) {
if (solution[i][j] == 0) {
solution[i][j] = 2;
}
}
}
// clears all 2's on the board
public void clear() {
for (int i = 0; i < solution.length; i++) {
for (int j = 0; j < solution.length; j++) {
if (solution[i][j] == 2) solution[i][j] = 0;
}
}
}
public static void main(String[] args) {
BishopsBT q = new BishopsBT();
q.solve();
}
}
私のプログラムは、最初の列に司教を入れて、このレイアウトはすべてのスペースを占めていないということです。もちろん、私は単にすべてを3列目に置くことができ、問題は解決されます。しかし、私はバックトラックを使用し、どのように考えている必要があります。アイデアやヒントがあれば、本当にうれしく思います。
あなたはそれを非常に技術的に説明することができ、とても感謝しています。私はあなたのアドバイスを使ってコードを書き直しましたが、（i == 8）、すべてのスペースが占有されていない場合の対処方法はまだ分かりません。私はそれが何らかの他の枝であるべきだと思う傾向があります。 – Unknown
付録：私は単純にfalseを返すことができますが、その場合、プログラムは8人のビショップの位置を変更しようとしますが、解決策は決して出ません。その場合、私は一歩以上後退しなければなりません。 – Unknown
あなたが解決策を見つけて、ボードの状態を元に戻す前に呼び出し元の再帰関数に 'true'値を伝播した場合にのみ' true'を返す場合、解答が見つかると、ボードはすべてのビショップを正しく配置する必要があります。 （if（place（i + 1、j + 1））が真を返すif（ 'if（place）（place））; –