数独ボードを生成するためのバックトラッキングアルゴリズムのヘルプが必要

Question

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

コード

私はmatrixと呼ばれる値を保持するための設定多次元配列を持っています。 matrixは、行である9つの配列で構成され、それぞれが9つの列を保持します。 generatePossibleNumbersArray()がmatrixのように正確に多次元配列を作成するためだけのヘルパー関数です

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; 
      } 
     } 
    } 
} 

：だから私はすべての正方形を解決するための

matrix[3][6]; 

機能を使用することになり、行4列7の値を取得しますただし、各セルの整数1〜9の配列を保持するように初期化されています。 populateMatrix()機能の間、これらの可能な数字は各セルごとに縮小されます。

問題

jが-1されて終わるので、それは行列を毎回完了する前に失敗しました。これは、より多くのセルが解決されるにつれて、アルゴリズムがセルの値を見つけ出してバックトラックするのがより困難になるからです。しかし、それは最終的にj == -1まで戻ってバックトラッキングを終わります。

私は本当にこのアルゴリズムが働くだろうと思って、私はこのまわりで私の頭を取得しようとしているすべての一日を過ごしてきましたが、私は誰もがこれに当てる可能性のある光は非常に高く評価されるだろうので困惑しています。

「私が知っていると思うと、私は数独を解決するためのjavascript関数を書いていきます。それはどれくらい難しいでしょうか？ "私は間違っていた。

---

@ Steve314によってコメントに基づいて、[ソリューション]

（彼は今削除しています！）私はif(!found) { ...にmatrix[i][j] = undefinedを追加し、アルゴリズムが機能するようになりましたし、高速軽量化されます。

興味があれば、complete codeです。

Answer 1

通常、バックトラッキングアルゴリズムは、分岐が失敗した場合に状態を復元し、次の可能な移動を行います。したがって、フィールドのランダムな塗りつぶしが失敗したブランチを作成した場合、最初に元のものを書き戻すだけです。