java - このバックトラッキングだけで最初の解を見つける方法

Question

最初の可能なソリューションのみを返す数独ソルバーを作成しようとしています。void メソッドを使用してすべての可能なソリューションを印刷することができましたが、最初の検索で停止することはできません。

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

以下は、ほとんどの再帰的バックトラッキングの問題に対する疑似コードです。

すでに解決済みの場合は、成功を報告してください。

for (現在の位置で可能なすべての選択肢) {

その選択をして、道に沿って一歩を踏み出してください。

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

再帰呼び出しが成功した場合、次の上位レベルに成功を報告します。

現在の選択を取り消して、ループの開始時の状態を復元します。

}

失敗を報告します。

これは、スタンフォード大学の講義に基づいた実際のコードです。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
            return nextCell(line, column); // continue

の中へ

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