4

誰かがこの解決策を理解するのを手伝ってくれますか:

 Initialize 2D array with 81 empty grids (nx = 9, ny = 9)
 Fill in some empty grid with the known values
 Make an original copy of the array
 Start from top left grid (nx = 0, ny = 0), check if grid is empty
 if (grid is empty) {
   assign the empty grid with values (i)
   if (no numbers exists in same rows & same columns same as (i) & 3x3 zone (i) is currently in)
     fill in the number
   if (numbers exists in same rows & same columns same as (i) & 3x3 zone (i) is currently in)
     discard (i) and repick other values (i++)
 }
 else {
   while (nx < 9) {
     Proceed to next row grid(nx++, ny)
     if (nx equals 9) {
       reset nx = 1
       proceed to next column grid(nx,ny++)
       if (ny equals 9) {
         print solution
       }
     }
   }
 }
4

3 に答える 3

14

これは、単純なブルート フォース ソルバーです。左上から開始し、行ごとに左から右に作業し、可能な数字をそれぞれの正方形に配置しようとし、再帰呼び出しを使用して続行します。失敗すると、バックトラックして別の代替手段を試みます。

呼び出された関数は、行、列、およびボックスに既に配置されている値をチェックすることにより、特定のセルにsafe値を配置することが現在合法であるかどうかを判断します。n

これは、数独を解く最も簡単な (そして最も遅い) 方法の 1 つです。

于 2010-01-15T23:48:44.530 に答える
4

数独を解決する方法はたくさんあります（一般的に数独に興味があるかどうかはわかりません）。これは基本的に制約充足問題であり、お気に入りの整合性チェック手法（AC3など）を適用して、制約を伝播し、明らかに無益なパスをはるかに早く整理することができます。変数は各正方形であり、各変数が取ることができるドメインは1から9までの整数です。制約は、セルのさまざまなサブセットに対するAllDiffです。

また、整数線形計画問題として定式化し、お気に入りのILPエンジン（lp_solveなど）で解決することもできます。

于 2010-01-17T05:13:26.867 に答える
0

最も紛らわしいのは、アルゴリズムが終了時に数独マトリックスに正しい値を入力することを期待していたのですが、代わりに値を出力して最初に戻るだけで、t 変数の値は常にグリッドに書き戻されます (おそらくアルゴリズム別の解決策を見つけることさえできます）。

アルゴリズムが終了したときにグリッドがいっぱいになるようにするには、ソルブ関数が true/false を返すようにし、内部呼び出しの結果に基づいてトレース バックするかどうかを決定します。

于 2010-01-16T00:10:19.957 に答える