このバックトラッキングでのみ最初の解決策を見つける方法

Question

私は可能な最初の解決策のみを返すSudokuソルバーを作成しようとしています。 私はすべての可能な解決方法をvoidメソッドで表示することができましたが、最初の検索では止められません。

私は、好ましい方法は、boolean型メソッドに切り替えて、ツリーまでtrueを返すことです知っている - が、私はそれを書くための正しい方法を見つけることができません。

私はいつもコンパイルエラー（method must return boolean）を試してみました。

public boolean recursiveSolve(int line, int column) { 
    if(line == N) // N is the board size (9) 
     return true; 
    // if Cell is not empty - continue 
    if(board1.getCell(line, column) != 0) { 
     return nextCell(line, column); 
    } 
    // if Cell empty - solve 
    else { 
     for(int i = 1; i <= N; i++) { 
      board1.setCell(line, column, i); // set value to cell 
      if(board1.boardIsOk())   // check if the board is legal 
       return nextCell(line, column); // continue 
     } 
     board1.setCell(line, column, 0);  // backtrack 
    } 
} 

private boolean nextCell(int line, int column) { 
    if(column < 8) 
     return recursiveSolve(line, column+1); // progress up the row 
    else 
     return recursiveSolve(line+1, 0);  // progress down the lines 
} 

ご協力いただければ幸いです。

Answer 1

への変更は

 if(board1.boardIsOk())   // check if the board is legal 
      return nextCell(line, column); // continue 

ここでは、ほとんどの再帰的なバックトラックの問題のいくつかの擬似コードです。

すでに解決策がある場合は、成功を報告してください。 （現在位置のすべての可能な選択）のために

{

は、その選択を行い、パスに沿ってステップを取ります。

再帰を使用して、新しい位置から問題を解決します。

再帰呼び出しが成功した場合は、次の高いレベルの に報告してください。

ループの先頭にある状態を復元するために、現在の選択肢から復帰します。

}

レポートが失敗しました。

ここにスタンフォードからの講義に基づくいくつかの実際のコードがあります。私はJavaでそれを書き直してコメントを書きました。

Boolean SolveSudoku(int[][] grid) 
{ 
    int row, col; 

    if(!FindUnassignedLocation(grid, row, col)) 
     //all locations successfully assigned 
     return true; 

    for(int num = 1; num <= 9; num++) 
    { 
     //if number is allowed to be placed in the square 
     if(NoConflicts(grid, row, col, num)) 
     { 
      //place the number in the square 
      grid[row][col] = num; 

      //recur, if successful then stop 
      if(SolveSudoku(grid)) 
       return true; 

      //undo and try again 
      grid[row][col] = UNASSIGNED; 
     } 
    } 
    //this triggers backtracking from early decisions 
    return false; 
} 

いくつかの方法を実装するだけで済みます。これはかなり簡単です。

Answer 2

 if(board1.boardIsOk()) {   // check if the board is legal 
      boolean solved = nextCell(line, column); // continue 
      if (solved) { 
       return true; 
      ] 
     } 
    ... 
    return false;