バックトラッキングによる 8 クイーン問題の実装でいくつかの問題が発生しています。私のコードはもうエラーをスローしていませんが、見つかった解決策が間違っています。これが私のコードです：
public class Queens {
public int[] field = new int[8];
public static void main(String[] args) {
new Queens();
}
public Queens() {
initField();
if (backtrack(0)) {
out();
}
}
boolean backtrack(int i) {
while (i < 8) {
if (danger(i)) {
field[i] += 1;
if (field[i] < 8) {
return backtrack(i);
} else {
field[i] = 0;
field[i - 1] += 1;
return backtrack(i - 1);
}
} else {
if (field[i] < 8) {
if (i == 7) {
return true;
} else {
return backtrack(i + 1);
}
} else {
field[i] = 0;
field[i - 1] += 1;
return backtrack(i - 1);
}
}
}
return false;
}
public void initField() {
for (int i = 0; i < 8; i++) {
field[i] = 0;
}
}
public boolean danger(int i) {
for (int j = i - 1; j >= 0; j--) {
if (field[i] == field[j]) {
return true;
}
if (Math.abs(field[i] - i) == Math.abs(field[j] - j)) {
return true;
}
}
return false;
}
public void out() {
for (int i = 0; i < 8; i++) {
System.out
.println("Line: " + (i + 1) + ", Field: " + (field[i] + 1));
}
}
}
そして、これは出力です：
Line: 1, Field: 4
Line: 2, Field: 8
Line: 3, Field: 7
Line: 4, Field: 5
Line: 5, Field: 3
Line: 6, Field: 6
Line: 7, Field: 2
Line: 8, Field: 1
クイーン 2 と 3 の位置、およびクイーン 7 と 8 の位置は違法です。コードの間違いを検索しましたが、何も見つからないのではないかと心配しています。
/e: Danger メソッドを次のように変更しました。
public boolean danger(int i) {
for (int j = i - 1; j >= 0; j--) {
if (field[i] == field[j]) {
return true;
}
if (Math.abs(field[i] - i) == Math.abs(field[j] - j)) {
return true;
}
if(Math.abs(field[i] + i) == Math.abs(field[j] + j)) {
return true;
}
}
return false;
}
質問には答えましたが、まだいくつかのバグを修正する必要があります._.