DFSアルゴリズム - 8-PuzzleまたはnXn-Game

Question

DFSアルゴリズムを解きたい。それはゲーム8-puzzlesまたはN x Nパズルについてです。

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

この配列が正常に動作します私の一般的なDFSのクラスに入り、：初めに私は（ゼロが空のフィールドを表す）のような二つの配列を持っています。私は他のタスクを正しく使用しました。しかし、ここでは完全を期すために、私のDFSクラスのbasic一部です：

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; 
} 

だから、最初は私のstart配列が第二として、第1パラメータと、私のtarget配列として渡します。

私のStateクラスでは、すべての可能性のある状態を返すgetNeighbours()メソッドを実装したいと思います。以下のような最初のラウンドなもので：

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

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

etc... 

そしてここでは私の問題です。どうすればそれができますか？それは最初の4つの操作で動作しますが、例外が発生します（ゼロまたは空のフィールドは例外として位置にないか、2つのゼロがあります）。何がそこに間違っていますか？

@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;  
} 

完全なコードhttps://gist.github.com/T0bbes/66d36326aa8878d5961880ce370ba82d

Answer 1

私はあなたのコードをチェックし、その例外を取得する理由は、ボードアレイは、すべての状態によって共有されています。 DFSは、多くのことを再帰とStackOverflowのを得ることができます

1. ：あなたは、その配列の深いコピーを作成する必要があり、あなたはこのコードを試すことができます。

   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; 
   } 
   

   しかし、あなたのコード内のいくつかの問題が残っています - スタックサイズを増やす必要があります（私にとっては-Xss100mが有効です）。スタックサイズを増やした後、コードはソリューションを出力することができますが、それは197144ステップを要します。

2. 実際、あなたが見るように、DFSは有効なソリューション（コードが正しい場合）のみを出力します。あなたはBFSを試してみるべきです。