8

だから、私は数独パズルの生成についてかなり読んだ。私の知る限り、希望する難易度の数独パズルを作成する標準的な方法は、パズルを生成し、後でそれを採点し、許容できる評価の1つになるまで繰り返すことです。これは、より複雑な解決パターン(XYウィング、メカジキなど)のいくつかを使用してバックトレースを介して生成することで改善できますが、ここでやりたいことではありません。

私がやりたいのは、実際のリソースを見つけることができなかったのですが、「難易度」(0〜1.0の値、0が最も簡単、1.0が最も難しい)からパズルを生成することです。

たとえば、適度に難しいパズルを作成したいので、値.675が選択されます。その値を使用して、適度に難しいパズルを生成できるようにしたいと思います。

誰かこのようなことを知っていますか?または、おそらく同様の方法論を持つものですか?

4

4 に答える 4

4

必要な難易度の数独をオンザフライで生成するための別の回答を追加します。

これは、他のアプローチとは異なり、アルゴリズムが 1 回だけ実行され、目的の難易度に一致する数独構成を返すことを意味します (範囲内の高い確率または確率 = 1 で) 。

数独の難易度を生成 (および評価) するためのさまざまなソリューションは、簡単に評価できる人間ベースのテクニックとアプローチに関係しています。

次に、(数独構成を生成した後)人間のようなソルバーで数独を再解決し、ソルバーが使用するテクニック(ペアXウィングメカジキなど)に応じて、難易度も割り当てられます。

このアプローチの問題 (および私が持っていたユースケースの要件)

  1. 与えられた難易度で数独を生成するために、以前の方法では数独を 2 回解く必要があります (1 回は基本アルゴリズムで、もう 1 回は人間のようなソルバーで)。

  2. 人間のようなソルバーによって解かれた後にのみ難易度を評価できる多くの数独を (事前に) 生成する必要があります。そのため、オンザフライで目的の数独を一度生成することはできません。

  3. 人間のようなソルバーは複雑になる可能性があり、ほとんどの場合 (すべてではないにしても) 9x9 の数独グリッドに密接に結合されています。そのため、他の数独 (4x4、16x16、6x6 など) への簡単な一般化はできません。

  4. 人間のようなテクニックの難易度は非常に主観的なものです。たとえば、なぜx-wingは隠しシングルよりも難しいと見なされるのでしょうか? (個人的には、公開されている難解な数独パズルを手動で解いたことがあり、そのようなテクニックを使用したことはありません)

次の利点を持つ別のアプローチが使用されました。

  1. 任意の数独 (9x9、4x4、6x6、16x16 など) に一般化します。
  2. 必要な難易度の数独構成は、一度だけオンザフライで生成されます
  3. 難易度は客観的なものです。

使い方?

まず第一に、パズルが難しければ難しいほど、それを解くのに時間がかかるという単純な事実です。

しかし、解決されるまでの時間は、手がかり (与えられた) の数と空のセルごとに調査される平均的な選択肢の両方と密接に相関しています。

私の以前の回答を拡張すると、任意の数独パズルでは、手がかりの最小数はパズルの客観的な特性であることが言及されました (たとえば、9x9 グリッドの場合、有効な数独を持つための手がかりの最小数は 17 です) 。

そこから始めて、難易度ごとの手がかりの最小数を計算できます (線形相関)。

さらに、数独生成プロセスの各ステップで、空のセルごとの平均選択肢 (調査対象) が所定の範囲内にあることを確認できます (目的の難易度の関数として)。

アルゴリズムがバックトラックを使用するかどうかに応じて (アルゴリズムがバックトラックを使用しない使用例について説明します)、目的の難易度は、確率 = 1 または範囲内の高い確率 (それぞれ) で達成できます。

このアルゴリズムで生成された数独と、以前のアプローチ (人間のようなソルバー) に基づいた難易度評価のテストでは、望ましい難易度と推定された難易度の相関関係に加えて、任意の数独構成に一般化する優れた能力が示されています。

(このオンライン数独ソルバー(およびこれも)を使用して、テスト数独の難易度を相関させました)

このコードはgithub sudoku.js (サンプル デモ アプリケーションと共に) で無料で入手できます。これは同じ作者による JavaScript のプロのクロスワード ビルダーである CrossWord.js の縮小版です。

于 2015-02-24T15:31:44.763 に答える
2

数独の難易度は、特定のグリッドの一意のソリューションを指定するために必要な (最小) 量の情報に興味深い方法で関連付けられています。

情報理論のように聞こえますが、ここにも応用があります。

数独パズルには独自のソリューションが必要です。さらに、数独パズルには特定の対称性、つまり行ごと、列ごと、および部分正方形があります。

これらの対称性は、ソリューションが一意になるように必要な手がかりの最小数 (および多かれ少なかれそれらの位置) を指定します (つまり、数独コンパイラまたはバックトラック検索のようなアルゴリズムを使用します)。

これは、最も難しい/難しい数独パズル レベルです (つまり、最低限必要な手がかりの数)。次に、必要な最小量よりも多くの手がかりを許可することにより、難易度が低いものから簡単なものまでの他のすべての難易度レベルが生成されます。

上記で説明したように、数独の難易度は標準ではないことに注意してください。必要な数の難易度を設定できます。標準的なのは、手がかりの最小数 (および位置) (最も難しいレベルであり、数独の対称性に関連する) であり、余分な/冗長な手がかりを表示できるようにするだけで、必要な数の難易度レベルを生成できます。同じように。

于 2014-08-04T01:02:05.513 に答える
1

さて、あなたはそれを解決する方法を知る前に、それがどれほど複雑であるかを知ることはできません。そして、数独解法(したがって難易度も)はNP-C複雑度クラスに属します。つまり、提案されたランダムな推測とチェックよりも(漸近的に)高速なアルゴリズムを見つけることは(ほとんどの場合)論理的に不可能です。

ただし、1つが見つかった場合は、P対NPの問題を解決しているので、フィールズ賞の食器棚をクリアする必要があります... :)

于 2012-05-23T15:08:58.370 に答える
1

あなたが尋ねるほどエレガントではありませんが、キャッシュを使用してこの動作をシミュレートできます。

  1. パズルに必要な「バケツ」の数を決定します。たとえば、20 を選択したとします。したがって、バケットにはさまざまな難易度範囲のパズルが含まれます: 0-.05、.05-.1、.1-.15、..、.9-.95、.95- 1
  2. パズルを生成する
  3. パズルを採点する
  4. 適切なバケツに入れる (またはバケツがいっぱいになったら捨てる)
  5. バケツが「いっぱい」になるまで繰り返します。バケットのサイズと保存場所は、アプリケーションのニーズによって異なります。

次に、ユーザーが特定の難易度のパズルを要求したときに、選択したバケットからキャッシュされたパズルを提供します。また、既知の難しさを持つパズルの数字を交換したり向きを変えたりして、同じレベルの難しさを持つ同様のパズルを生成することを検討することもできます。次に、バケツに新しいパズルを補充する必要がある場合は、必要に応じて上記を繰り返します。

于 2012-05-23T14:48:45.323 に答える