9

ブルートフォースバックトラッキングを使用して数独グリッドを解決する非常に単純なアルゴリズムを実装しようとしています。私が直面している問題は、数独グリッドを表す 2 次元配列の空のセルの行と列に対応するとというSudokuクラスの 2 つのインスタンス変数を実装に含めたことです。rowcol

私のsolve()メソッドが実行されると、最初に空のセルがないかどうかがチェックされます。この場合、パズルはすでに完成しています。それ以外の場合、同じメソッドが空のセルの行と列をインスタンス変数rowとグリッドを含むオブジェクトにcol割り当てます。Sudokuその後、 for ループは、メソッド呼び出しによって空のセルに配置できる数字を検証しますisSafe(int n)(このメソッドは、パズルの制約が満たされているかどうかを確認します。完全に機能することを保証できます)。そのため、メソッドは空のセルに数値を配置し、オブジェクトでメソッドisSafe()を再帰的に呼び出します。solve()Sudoku

満たすことができない制約にヒットした場合0、最後rowにa を再割り当てし、colそれが満たされました。ここで問題が発見されました！プログラムは常に変数rowとcol変数を更新しているため、古いインスタンスは再帰呼び出しごとに失われます。プログラムがバックトラックしたときにアクションを取り消すことができるように、この値を保存する方法を見つけようとしています。colそれぞれをスタックにプッシュすることを考えrowましたが、どこに行けばいいのか本当にわかりません。

この問題にアプローチする簡単な方法を誰か教えてもらえますか? クラス全体は含まれていません。役立つと思われる場合はお知らせください。投稿します。

class Sudoku {
    int SIZE, N, row, col;
    int Grid[][];    

    public boolean solve() {
        if (!this.findNextZero()) return true;

        for (int num = 1; num <= 9; num++) {
            if (isSafe(num)) {
                this.Grid[this.row][this.col] = num;

                if (this.solve()) return true;

                this.Grid[this.row][this.col] = 0;
                // this.Grid[oldRow][oldCol] = 0;
            }
        }
        return false;
    }

    public boolean findNextZero() {
        for (int i = 0; i < this.N; i++) {
            for (int j = 0; j < this.N; j++) {
                if (this.Grid[i][j] == 0) {
                    this.row = i;
                    this.col = j;
                    return true;
                }
            }
        }
        return false;
    }

    public boolean isSafe(int num) {
        return !this.usedInRow(num) 
                && !this.usedInColumn(num) 
                && !this.usedInBox(num);
    }

スタックを実装する場合、次のことは理にかなっていますか? 操作の後、および整数をスタックにfindNextZero()プッシュします。これを続けてから、次のコード行を変更しますrowcol

this.Grid[this.row][this.col] = 0;

のようなものに

this.Grid[s.pop][s.pop] = 0;

これは合理的なアプローチですか？

4

2 に答える 2

2

実際、スタックや再帰は必要ありません。セルにアクセスするための順序付けられた方法が必要なだけです (以下のコードを参照)。このソリューションは、再帰的なバージョンのようにスタックオーバーフローを提供しません。

事前に解決されたセルにラベルを付けるための初期マトリックスを作成します。

public boolean[][] findSolved(int[][] grid){
    boolean[][] isSolved = new boolean[9][9];        

    for(int i=0; i<9; i++)
        for(int j=0; j<9; j++)
            isSolved[i][j] = grid[i][j] != 0;

    return isSolved;
}

次に、バックトラックするかどうかに基づいて、セルを前後に移動します。

public boolean solve(int[][] grid){
    boolean[][] isSolved = findSolved(grid);
    int row, col, k = 0;
    boolean backtracking = false;

    while( k >= 0 && k < 81){
        // Find row and col
        row = k/9;
        col = k%9;

        // Only handle the unsolved cells
        if(!isSolved[row][col]){
            grid[row][col]++;

            // Find next valid value to try, if one exists
            while(!isSafe(grid, row, col) && grid[row][col] < 9)
                grid[row][col]++;

            if(grid[row][col] >= 9){
                // no valid value exists. Reset cell and backtrack
                grid[row][col] = 0;
                backtracking = true;
            } else{
                // a valid value exists, move forward
                backtracking = false;
            }
        }

        // if backtracking move back one, otherwise move forward 1.
        k += backtracking ? -1:1
    }

    // k will either equal 81 if done or -1 if there was no solution.
    return k == 81;
}
于 2013-11-14T07:30:33.187 に答える
1

Sudoku クラスの Stack インスタンス変数に格納することで、再帰呼び出しごとに失い続けた空のセルの 'row' 値と 'col' 値を格納することができました。findNextZero() メソッドは、'row' 値と 'col' 値を 2 つの空のスタックにプッシュしました。次に、プログラムの残りの部分を peek() メソッドを介してこの情報にアクセスするように再構築しました。後戻りする必要がある場合に備えて、最後の 2 つの値をポップし、それらの値に対応するグリッド上の数値を 0 に設定しました。

于 2013-11-14T16:44:53.737 に答える