4

数独ボードを生成するためのアルゴリズムを作成しましたが、失敗しています。これに基づいて作成しましたが、これに遭遇する前に多くのコードを作成したため、異なります。

コード

と呼ばれる値を保持するために設定された多次元配列がありますmatrix。matrix行である9つの配列で構成され、これらのそれぞれが9つの列を保持します。したがって、行4列7の値を取得するには、使用します

matrix[3][6];

すべての正方形を解く関数:

var populateMatrix = function() {
    var possibles = generatePossibleNumbersArray();
    var found = false;
    for(var i=0; i< matrix.length; i++) {
        for(var j=0; j< matrix[i].length; j++) {
            while(possibles[i][j].length > 0) {
                var rnd = Math.floor(Math.random() * possibles[i][j].length);
                var num = possibles[i][j].splice(rnd, 1)[0];
                if(isValid(i, j, num)) {
                    matrix[i][j] = num;
                    found = true;
                    break;
                } else {
                    found = false;
                    continue;
                }
            }
            if(!found) {
                possibles[i][j] = [1,2,3,4,5,6,7,8,9];
                j -= 2;
            }
        }
    }
}

は、セルごとに 1 ～ 9 の整数の配列を保持するように初期化されることを除いて、まったく同じように多次元配列を作成するためのgeneratePossibleNumbersArray()単なるヘルパー関数です。matrix関数の実行中、populateMatrix()これらの可能な数値はセルごとに削減されます。

問題

になるため、毎回マトリックスを完了する前に失敗しjます-1。これは、より多くのセルが解決されると、アルゴリズムがセルの値を見つけるのが難しくなり、バックトラックするためです。しかし、最終的には までさかのぼってしまいj == -1ます。

私は本当にこのアルゴリズムがうまくいくと思っていました。私はこれを回避するために一日中費やしましたが、私は困惑しているので、誰かがこれに当てることができる光は非常に高く評価されます.

「分かった、数独を解くための JavaScript 関数を書こう」と思いました。それはどれくらい難しいですか？私がどれほど間違っていたか。

[解決]

@Steve314 によるコメント (彼は現在削除されています!) に基づいて、アルゴリズムに追加matrix[i][j] = undefinedしたところif(!found) { ...、アルゴリズムが機能し、非常に高速になりました。

興味のある方は、完全なコードをご覧ください。

4

1 に答える 1

3

バックトラッキングアルゴリズムは通常、ブランチに障害が発生した場合に状態を復元し、次の可能な移動を実行します。したがって、フィールドをランダムに入力すると失敗したブランチが作成された場合は、元々そこにあったものを書き戻すだけです。

于 2011-07-24T19:52:11.307 に答える