DFS-Algorithmus - 8-Puzzle oder nXn-Spiel

Question

Ich möchte einen DFS-Algorithmus lösen. Es geht um das Spiel 8-puzzles oder N x N Puzzle. Am Anfang habe ich zwei Arrays wie (die Null steht ein leeres Feld):

int[][] start = {{0,1,2}, {4,5,3}, {7,8,6}}; 
int[][] target = {{1,2,3}, {1,5,6}, {7,8,0}}; 

Diese Arrays geht in meine generische DFS-Klasse, die gut funktioniert. Ich habe es von anderen Aufgaben richtig benutzt. Aber für die Vollständigkeit ist hier der basic Teil meiner DFS-Klasse:

private static boolean search(State node, State target) { 
    if (node.equals(target)) 
     return true; 

    for (State neighbour : node.getNeighbours()) { 
     if (!visited.contains(neighbour)) { 
      predMap.put(neighbour,node); 
      visited.add(neighbour); 
      if (search(neighbour, target)){ 
       return true; 
      } 
     } 
    } 
    return false; 
} 

So zunächst meine start Array als ersten Parameter und meine target Array als zweite passieren. In meiner State Klasse möchte ich die Methode implementieren, die alle möglichen Zustände zurückgeben soll. In der ersten Runde etwas wie:

First: 
|0|1|2| 
|4|5|3| 
|7|8|6| 

Second (rotated zero): 
|1|0|2| 
|4|5|3| 
|7|8|6| 

etc... 

Und hier ist mein Problem. Wie kannst du das tun? Es funktioniert für die ersten 4 Operationen, aber dann bekomme ich eine Ausnahme (Die Null oder das leere Feld ist nicht auf der Position als ausgenommen oder es gibt zwei Nullen). Was ist da falsch?

@Override 
public List<State> getNeighbours() { 
    List<State> neighbours = new LinkedList<>(); 

    // possibles moves... 
    final int startX = (freeX - 1 < 0) ? freeX : freeX - 1; 
    final int startY = (freeY - 1 < 0) ? freeY : freeY - 1; 
    final int endX = (freeX + 1 > N - 1) ? freeX : freeX + 1; 
    final int endY = (freeY + 1 > N - 1) ? freeY : freeY + 1; 

    for (int row = startX; row <= endX; row++) { 
     for (int column = startY; column <= endY; column++) { 
      int tmp = board[row][column]; 
      board[row][column] = board[freeX][freeY]; 
      board[freeX][freeY] = tmp; 

      // Just show the table... 
      System.out.println("=== BEFORE ==="); 
      for (int[] x : board) { 
       System.out.println(Arrays.toString(x)); 
      } 

      neighbours.add(new State(board, freeX + row, freeY + column)); 

      board[freeX][freeY] = board[row][column]; 
      board[row][column] = tmp; 

      // Just show the table... 
      System.out.println("=== AFTER ==="); 
      for (int[] x : board) { 
       System.out.println(Arrays.toString(x)); 
      } 
     } 
    } 

    return neighbours;  
} 

vollständige Code https://gist.github.com/T0bbes/66d36326aa8878d5961880ce370ba82d

Answer 1

ich Ihren Code überprüft, den Grund bekommen diese Ausnahme ist, das Board Array von jedem Staat geteilt wird. Sie sollten eine tiefe Kopie des Arrays, und Sie können diesen Code versuchen:

public Board(int[][] board, int x, int y){ 
    if (board[x][y]!=0) 
     throw new IllegalArgumentException("Field (" +x+","+y+") must be free (0)."); 
    this.board = new int[board.length][board[0].length]; 
    for (int i = 0; i < this.board.length; i++) 
     for (int j = 0; j < this.board[i].length; j++) 
      this.board[i][j] = board[i][j]; 
    this.freeX = x; 
    this.freeY = y; 
    this.N = board.length; 
} 

Aber es gibt noch einige Probleme in Ihrem Code:

1. DFS viel Rekursion kann und ein Stackoverflow - Sie sollten die Stapelgröße erhöhen (-Xss100m funktioniert für mich). Nach Erhöhung der Stack-Größe, kann Ihr Code eine Lösung ausgeben, aber es dauert 197144 Schritte ...

2. In der Tat, wie Sie sehen, DFS-Ausgabe nur eine gültige Lösung (wenn Ihr Code korrekt ist), nicht die optimale Lösung. Sie sollten BFS versuchen.