Ich habe eine Aufgabe, ein Programm zu schreiben, das 8 Bischöfe im Schachbrett aufstellt, um ganzes Brett zu besetzen. Es sollte enden, wenn die erste Lösung gefunden wird und alles ausdrucken. Hier ist mein geschriebener Code in Java, und ich habe Schwierigkeiten damit, ihn mit Backtracking zu beenden (dieser Ort wird im Code kommentiert).8 Bischöfe zu besetzen ganzes Brett [Backtracking]
/*
* 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();
}
}
Die Sache ist die, dass mein Programm im Moment Bischöfe in der ersten Spalte legt und dieses Layout nicht besetzen den ganzen Raum. Natürlich könnte ich einfach alles in die dritte Spalte setzen und das Problem ist gelöst. Allerdings muss ich Backtracking verwenden und habe keine Ahnung wie. Wenn Sie irgendwelche Ideen oder Tipps haben, würde ich mich freuen, sie zu hören.
Es war extrem hilfreich, da Sie es sehr technisch erklären konnten und ich schätze das sehr. Ich habe den Code mit deinem Ratschlag neu geschrieben, aber ich habe immer noch keine Idee, was ich tun soll, falls (i == 8) und der gesamte Platz nicht belegt ist. Ich neige dazu zu glauben, dass es eine Art anderer Zweig sein sollte. – Unknown
Anhang: Ich könnte einfach falsch zurückgeben, aber in diesem Fall wird das Programm nur versuchen, die Läuferposition der Acht zu ändern, und ich werde niemals eine Lösung finden. In diesem Fall muss ich mehr als einen Schritt zurück gehen. – Unknown
Wenn Sie 'true' nur zurückgeben, wenn Sie eine Lösung gefunden haben und den 'true'-Wert an die aufrufende rekursive Funktion weitergeben, bevor Sie den Zustand des Boards wiederherstellen, sollte die Platine alle Bishops korrekt platziert haben, wenn eine Lösung gefunden wird. (Die Zeile 'if (place (i + 1, j + 1)) gibt" true "zurück;" oben "tut das: Wenn Sie' true' zurückgeben, tun Sie dies sofort ohne aufzuräumen.) –