2016-03-29 4 views
3

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.

Antwort

2

Ihre Lösung geht davon aus, dass alle Läufer in verschiedenen Reihen platziert werden müssen. Dies gilt nicht für alle Lösungen. (Es gibt eine Lösung, wo alle Bischöfe in der dritten oder vierten Spalte sind. Sie suchen nicht nach allen Lösungen, aber wenn Sie wären, würden Sie viele Lösungen durch diese Annahme verpassen.)

Sie auch don Ich brauche die canPlace Kontrolle: Es gibt keine Beschränkung, dass die Bischöfe sich nicht gegenseitig bedrohen können. (Dies könnte eine gültige Technik sein, um die Suche zu beschleunigen, aber auch hier werden Sie einige Lösungen übersehen, wenn Sie es anwenden. Wenn Sie es verwenden wollen, müssen Sie nicht alle diagonalen Zellen nach bereits platzierten Bischöfen überprüfen; ist genug, ob die aktuelle Zelle als „besetzt“ oder bedroht markiert wurde überprüfen.)

Wenn Sie einen Brute-Force-Ansatz mit Rückzieher verwenden wollen, können Sie alle möglichen Kombinationen von Bischöfen testen. Das sind C (64, 8) oder 4,426,165,368 Kombinationen.

Sie können die Möglichkeiten drastisch reduzieren, aber nicht durch die Annahme, dass die Läufer in verschiedenen Reihen sein müssen. Beachten Sie stattdessen, dass Ihre Lösung aus zwei unabhängigen Lösungen besteht. Ein Läufer auf einem weißen Feld kann nur weiße Felder bedrohen und ein Läufer auf einem schwarzen Feld kann nur schwarze Felder bedrohen. So finden Sie eine Lösung, um vier Bischöfe auf dem Brett zu setzen, die alle weißen Quadrate bedrohen. Dann

(Wenn Sie alle Lösungen finden wollen, finden alle k Teillösungen und kombinieren sie zu k ² Komplettlösungen.)

Diese Trennung von Fällen schneidet die möglichen Anordnungen nach unten zu testen C (32, 8) oder 35,960. Ihre Strategie, nur Konfigurationen in Betracht zu ziehen, in denen es genau einen Läufer pro Reihe gibt, prüft 8^8 (ungefähr 16 Millionen) Möglichkeiten. Es vermisst einige Lösungen und überprüft meny Konfigurationen, wo nicht vier Bischöfe auf weißen Quadraten und vier auf schwarzen Quadraten sind.

Das Prinzip der Rückverfolgung wurde in der anderen Antwort gegeben.Wenn Sie die 32 weißen Quadrate wie folgt beschriften:

01 02 03 04 
    05 06 07 08 
09 10 11 12 
    13 14 15 16 
17 18 19 20 
    21 22 23 24 
25 26 27 28 
    29 30 31 32 

können Sie einen rekursiven Ansatz wie diese verwenden (in pseudo-Java):

bool place(int i, int start) { 
    if (i == 8) { 
     if (allOccupied()) { 
      print(); 
      return true; 
     } 
    } else { 
     for (int j = start, j < 32; j++) { 
      int row = j/4; 
      int col = 2 * (j % 4) + row % 2; 

      // add bishop at (col, row) 
      // save occupancy matrix 
      // add threat by (col, row) to matrix 

      if (place(i + 1, j + 1)) return true; 

      // revert matrix to saved matrix 
      // remove bishop from (col, row) 
     } 
    } 

    return false; 
} 

und starten Sie es mit

place(0, 0); 
+0

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

+0

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

+0

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.) –

0

Sie sollten etwas tun:

public boolean placeBishops (int bishop){ 
    if(bishop == 8){ 
     if(allSpaceOccupied()){ 
      //Print the board here, i.e found the solution 
      //also check the indexing of the bishop, 
      //i have assumed that they start from 0 
      return true; 
     }else{ 
      return false; 
     } 
    } 
    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; 
      boolean found = placeBishops(bishop+1); 
      if(found == true) return true; 
      solution[row][bishop] = 0; 
     } 
    } 
    return false; 
} 

können wir überprüfen, ob ein Platz für einen paticular Bischof gut ist oder nicht, und dementsprechend den Bischof Graf erhöhen, wenn wir die Lösung gehen nach unten nicht finden, dass Pfad, setzen wir die solution array für den aktuellen Bischof Index und die entsprechende Zeile für den Bischof, so dass wir nach einer anderen möglichen Lösung suchen können.

+0

Dies würde gut funktionieren, wenn die canPlace-Methode jede Bedingung überprüfen würde (wie beim Königinnen-Problem: Sie prüfen nur, ob es keine Königin in Zeile, Spalte oder Diagonale gibt und platzieren Sie sie). Hier prüft die canPlace-Methode nur, ob es in der Diagonale des Platzes keinen Läufer gibt (weil das uninteressant wäre, den Läufer an einen solchen Ort zu setzen). Es bedeutet aber auch, dass wir Platz 8 haben können und der gesamte Raum nicht besetzt wäre. Also ich glaube, wir müssen allSpaceOccupied() Methode irgendwie ... – Unknown

+0

Was genau funktioniert allspacecupied Funktion tun? – uSeemSurprised

+0

Es prüft, ob der gesamte Speicherplatz belegt ist, und gibt wahr oder falsch zurück. Zum Beispiel canPlace verwenden wir können wie diese Bischöfe setzen: 1 xxxxxxx 1 xxxxxx 0 1 xxxxx 0 0 1 xxxx 0 0 0 1 xxxx 0 0 0 1 xxxxx 0 0 1 xxxxxx 0 1 xxxxxxx Allerdings ist hier nicht der gesamte Platz belegt, daher müssen wir nach einer anderen Lösung suchen. – Unknown