6

数独を生成するアルゴリズムを作成しましたが、それはひどく非効率的でした。各パズルの生成には数分かかりました。だから今、私はそれを最適な方法で書き直そうとしています。しかし、私は助けが必要ないくつかの問題を経験しています。

2つのアプローチがあります：

  1. 空白のグリッドから始めて番号を追加し、それが解決可能かどうかを確認します。
  2. 81個​​の数字すべてで完全に有効なグリッドを作成し、残りの数字の数に満足し、それでも解決できるまで削除します。

最初は最初のアプローチを使用しましたが、より効果的だと思うので、次に2番目を使用します（解決可能であることが保証されている有効なパズルから始めます）。私は2番目のアプローチがより良いというのは正しいですか？

完全に実装されたグリッドを生成しようとすると、問題が発生します。私のアルゴリズムは次のとおりです。

  • 各セルの候補を設定します。最初は1から9までの数字です。
  • 値のないランダムなセルを選択します。
  • そのセルからランダムな候補を選択し、セル値として割り当てます。他の候補は破棄されます。
  • ここで、割り当てられたセルに対応する各行、セル、および正方形について、これらの候補からセルの値を削除します。したがって、各番号は行/列/正方形で一意です。
  • 繰り返す

この手法は、重複する番号のないランダムグリッドを保証します。ただし、ほとんどの場合、配置のルールに違反しないと、競合が発生します。たとえば、すべての候補が削除された空のセルなど、最初からやり直す必要があります。配置のルールを破ることなく、グリッド全体を数字で埋める、よりエレガントで効率的な方法はありますか？

4

4 に答える 4

8

既存のアルゴリズムやコードを見たことがありますか?

アルゴリズムの説明については、 http://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdfと、 http://norvig.com/sudoku.htmlにある Peter Norvig の記事をご覧ください。

Python にはいくつかの実装があります。これまでのところ、公開された C# ソリューションは見たことがありません。

幸運を！

于 2012-02-15T15:00:51.350 に答える
0

いくつかの既存のアルゴリズムを見ている場合は、そのための ac# プロジェクトがあります。それは実際にはピーター・ノーヴィグと同じ解決策から来ています。詳細はこちら

これが役立つことを願っています！

于 2012-02-15T15:10:22.030 に答える
0

私のアプローチは、最初の方法と 2 番目の方法を組み合わせることです。

まず、数独ソルバーが必要です。空の数独にソルバーを適用します。それは、手がかりのない数独の解決策を見つけることです。左上から右下へ順番に数字を入れていきます。それ以外の場合は、時間の問題があります。どうしてか分かりません。とにかく、数独パズルを完成させるのに時間がかからず、非常に高速に動作します。バックトラッキングを適用するときは、各位置の可能な番号のリストをシャッフルします。そうしないと、毎回同じパズルが表示されます。

次に、すべての位置の新しいリストをランダム化します。これは、ランダムな順序で並べられた 81 の位置のリストです。この順序のリストに従って、上記のパズルから数字を削除してみてください。数字を削除するたびに、複数の解があるかどうかを確認する必要があります。複数のソリューションがある場合。番号を戻して、ランダム リストの次の位置を試す必要があります。このプロセスは、リストの最後まで続くか、パズルから 64 個の数字を削除するまで続きます。数独が 64 なのは、手がかりが 17 未満の数独は存在しないことを誰かが証明したためです。このプロセスは、15 秒から 2 分までさまざまです。通常、数独パズルを取得するのに 30 秒かかります。

第 3 に、各数独パズルで 30 秒から 2 分待ちたくない場合は、上記の数独にいくつかの変更を加えることができます。これには、行と列の切り替え、回転が含まれます。番号を再マッピングすることもできます。たとえば、1->2、2->3...9->1 です。回転して再マッピングした後、これが元の数独であることに誰も気付かないでしょう。

于 2021-04-02T01:28:57.373 に答える