数独再帰はバックトレイン中に問題があります。 （ブルートフォース）

Question

可能性の重複：
Sudoku solver in java, using backtracking and recursion

私は再帰とブルートフォースを使用して数独を解決するプログラムを作成しています。私の重要な問題は、どうやって止まってしまったのかを私が理解していないということです。

1. は数独でのゼロの数を探す：

   プログラムの一般的なアルゴリズムは次のようです。

2. 最初の0（getNextEmptyメソッドでこれを行います）の位置に数字を挿入します（insertNumberは値がスドクルールに準拠していることを確認し、そうであればtrueを返します）。

3. 次に、再帰呼び出しを行います。ゼロがなくなると終了します（nはゼロの数です）。

4. プログラムが停止したポイントに達すると、ピースを変更するためにバックトラックする必要があります。しかし、これはどのように可能ですか？

実際には、セルクラスは調整するセルの位置を[row、column]の形式の配列に保持します。そのセルに関連付けられた行、列、またはより小さなグリッドを返すメソッドがあります。

私は手持ちまたはすべてのコードを要求していませんが、正しい方向のちょっとした動きで十分です。再帰の理解に正当な関心があります。

public static int[][] getSolution(int[][] grid) { 
    for (int i = 0; i < 9; i++) { 
     System.arraycopy(grid[i], 0, SolveSudoku.grid[i], 0, 9); 
    }// end for 
    int n = getZeroes(); 
    return getSolution(n); 
}//end getSolution 

private static int[][] getSolution(int n) { 
    if (n == 0) { 
     return grid;   
    }//end if 
    Cell cell = getNextEmpty(); 
    boolean fits = false; 
    for (int i = 0; i <= 9; i++) { 
     fits = insertNumber(cell, i); 
     if (fits) { 
      break; 
     }else { 
      //I do not understand what I should do here 
     } 
    }//end for 
    return getSolution(n - 1); 
}//end getSolution 

Answer 1

右方向にナッジ。グリッドを解決するために必要なすべての情報を把握していないので、あなたのアプローチは少し微調整する必要があります。

private static int[][] getSolution(int n) { 
    if (n == 0) { 
     return grid;   
    }//end if 

    Cell cell = getNextEmpty(); 
    boolean fits = false; 
    for (int i = 0; i <= 9; i++) { 
     fits = insertNumber(cell, i); 
     if (fits) { 
      break; // means i fits in Cell 
     } else { 
      // i doesn't fit... try the next i 
      // don't need to do anything 
     } 
    }//end for 
    if (!fits) { 
     // There are no numbers that fit in this Cell 
     // What should happen? 
     // Did I make a bad guess? 
     // How do I BACKTRACK and correct a previous guess? 
    } 
    return getSolution(n - 1); 
}//end getSolution 

Answer 2

一般に、再帰的ブルートフォースでは、以下のコードに似た構文を使用します。これは、あなたが何らかの行動をした後にそれを数えることができるからです。それが新しい「出発位置」です。 だから、このようになります

private void Guess(int[][] grid) 
{ 
    if(/**grid is a solution **/) 
     //signal success 
    else 
    { 
     if(/*seed out any bad, unacceptable answers you may have missed*/) 
      return;//this includes cases when there are no more zeros 
     //for every possible move, 
     //make a modified grid, with one move done, and call 
     Guess(ModifiedGrid);//for every possible move, generally you can modify 
     //grid itself, because its passed by value 
    } 
}