Knight's Tour Rekursion findet keine Lösung

Question

Knight's Tour wurde vorher gefragt, aber ich habe immer noch Probleme damit. Ich versuche eine Rekursion, um alle Zellen des Schachbretts zu besuchen, aber ich kann nicht mehr als 52 Besuche machen. Danach rückt es zurück und die Anzahl der besuchten Zellen zählt herunter. Hier ist mein Code:

public class Ch7E22_3 { 
    public static int[][] chess; 
    public static int[][] adjacent; 

    public static void main(String[] args) { 
     chess = new int[8][8]; 
     adjacent = new int[][] { { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 }, { 1, 2 }, { -1, 2 }, { 1, -2 }, 
       { -1, -2 } }; 
     initializeChess(); 
     move(1, 0, 0); 
    } 

    private static void move(int cnt, int row, int col) { 
     chess[row][col] = cnt; 
     if (cnt == (8 * 8)) { 
      System.out.println("You moved around all cells: " + cnt); 
     } else { 
      for (int i = 0; i < 8; i++) { 
       if (((row + adjacent[i][0] >= 0) && (row + adjacent[i][0]) < 8) 
         && ((col + adjacent[i][1] >= 0) && (col + adjacent[i][1] < 8))) { 
        if (chess[row + adjacent[i][0]][col + adjacent[i][1]] == 0) { 
         row = row + adjacent[i][0]; 
         col = col + adjacent[i][1]; 
         cnt++; 
         System.out.println(row + " " + col + " cnt = " + cnt); 
         move(cnt, row, col); 
        } 
       } 
      } 
     } 
     chess[row][col] = 0; 
    } 

    private static void initializeChess() { 
     for (int i = 0; i < 8; i++) { 
      for (int j = 0; j < 8; j++) { 
       chess[i][j] = 0; 
      } 
     } 
    } 
} 

Answer 1

Ein erstes Problem ist hier:

for (int i = 0; i < 8; i++) { 

Also, Sie haben die for-Schleife aus. Nehmen wir an, Sie bei 51.

mit cnt eingeben Jetzt haben Sie

if (... some overly complicated condition ...) { 
    ... cnt++ 
    move(cnt, 

Was jetzt geschieht, ist: zuerst Sie Ihre rekursive Aufrufe zu machen, und wahrscheinlich jeder Zeit Recht, wenn Hits zuerst. So erhöhen Sie cnt und recurse erneut. Daher zeigen Ihre Ausdrucke, wie sich cnt ständig erhöht.

Aber irgendwann endet die Rekursion - die If-Bedingung wird nicht mehr wahr. Also die rekursiv aufgerufene Methode ... endet. Aber bedenken Sie: Sie haben diese Methode aufgerufen ... von einem anderen Anruf an move. Und das könnte immer noch eine Schleife sein. Und noch wichtiger, dass move() hat seine eigene Version von cnt.

Um zu sehen, was ich meine: Ändern cnt von Methode lokal Variable zu einem Bereich Ihrer Klasse, ähnlich wie Ihre Vorstand! Wenn Sie das tun, werden Sie feststellen, dass Ihr Code tatsächlich druckt:

... 
3 7 cnt = 52 
2 4 cnt = 53 
... 
2 3 cnt = 64 
You moved around all cells: 64 
0 4 cnt = 65 
... 

tatsächlich später aufhören mit

4 0 cnt = 126 

Bedeutung: Druck von cnt Wirkung des Algorithmus nur eine Seite ist nicht wirklich funktioniert korrekt!

Endlich: Ich würde empfehlen, zu brechen Ihr, wenn die Bedingung in eine Reihe von kleinen Hilfsmethoden, wie

private static isXyz(...) 

und if-Anweisung innerhalb dass diese Methoden zu nennen - es mit Lesbarkeit dramatisch helfen würde!

Answer 2

Ihr Backtracking ist nicht korrekt. Wenn die letzte Zeile ausgeführt wird und chess[row][col] wieder auf Null zurückgesetzt wird, haben sich row und col mit ziemlicher Sicherheit geändert.

Es wäre besser, niemals row, col und cnt in Ihrer Methode zu ändern, sondern nur neue Werte in den rekursiven Aufruf zu übergeben.So etwas wie dies, obwohl ich nicht den Rest Ihrer Logik überprüft:

for (int i = 0; i < 8; i++) { 
     int nextrow = row + adjacent[i][0]; 
     int nextcol = col + adjacent[i][1]; 
     if (nextrow >= 0 && nextrow < 8 && 
       nextcol >= 0 && nextcol < 8) { 
      if (chess[nextrow][nextcol] == 0) { 
       System.out.println(nextrow + " " + nextcol + " cnt = " + (cnt+1)); 
       move(cnt+1, nextrow, nextcol); 
      } 
     } 
    } 

Um sicherzustellen, dass Sie in nur Modifizierung die Werte konsistent sind, die bis auf den nachfolgenden rekursive Aufruf übergeben werden, und die Änderung von ihnen nie innerhalb der Methode, können Sie die Parameter endgültig machen:

private static void move(final int cnt, final int row, final int col) { 
    ... 
}