私はJavascriptで書かれた数独ゲームを楽しみのために作っています。
すべてが正常に機能し、ボードは毎回単一のソリューションで完全に生成されます。
私の唯一の問題は、プロジェクトを一般に公開することを妨げているの
は、ボードの難易度を評価する方法がわからないことです。私はどこを見ても
、フォーラムなどに投稿しました。私は自分でアルゴリズムを書きたくありません。それはこのプロジェクトの
目的ではありません。また、私は数学者ではないので、アルゴリズムは複雑すぎます。
私が近づいたのは、 JSを介してグレーディングを行うこのウェブサイト
だけでしたが、問題は、コードがそのようなお粗末な文書化されていない、非常にアドホックな方法で書かれている
ため、借りることができないことです...
要点を説明します-
数独の格付け/評価のソースコードを提供している場所を教えてもらえますか？
ありがとう
アップデート22.6.11：
これは私の数独ゲーム
です
。基本的な人間の論理解法に依存する独自の評価システムを実装しているので、チェックしてください。
私はこの問題を自分で考えました。私ができる最善のことは、パズルを実際に解いてゲームツリーを分析することによって、パズルを解くのがどれほど難しいかを判断することです。
最初に：人間のプレイヤーが使用する可能性が低いアルゴリズムではなく、「人間のルール」を使用してソルバーを実装します。（それ自体が興味深い問題です。）人間が使用する難しさに応じて、ソルバーの各論理ルールをスコアリングします。スコアを相互に自由に調整できるように、数百以上の値を使用してください。
パズルを解く。各位置で：
パズルの全体的な難易度は、ゲームツリーを通るパスの位置のスコアの合計です。
編集：代替ポジションスコア：より難しいルールを使用して控除を完全に除外する代わりに、各ルール（または複合アプリケーション）の全体的な難易度を計算し、最小値を選択します。（ここでの論理は、ルールAのスコアが50、ルールBのスコアが400で、ルールAを1つのセルに適用できるが、ルールBを10に適用できる場合、プレーヤーは簡単な1つのプレイよりも難しい10のプレイの1つを見つけます。ただし、これにはすべての可能性を計算する必要があります。）
編集：Briguy37によって提案された代替案：ポジションスコアにすべての控除を含めます。、、などが個々の控除1 / (1/d1 + 1/d2 + ...)である場合d1、各位置をスコアリングします。d2（これは基本的に、個々の「控除抵抗」などが与えられた位置で「控除を行うことに対する抵抗」d1をd2計算します。ただし、これにはすべての可能性を計算する必要があります。）
うまくいけば、このスコアリング戦略は、難易度の主観的な評価が増加するにつれて増加するパズルのメトリックを生成します。そうでない場合は、ルールのスコア（または上記のオプションからのヒューリスティックの選択）を調整することで、目的の相関関係が得られる可能性があります。スコアと主観的な経験の間に一貫した相関関係を達成すると、「簡単」、「難しい」などの数値のしきい値がどうあるべきかを判断できるようになります。そして、あなたは完了です！
ドナルド・クヌースはこの問題を研究し、数独を解くためのDancing Linksアルゴリズムを考案し、それらの難易度を評価しました。
グーグルの周りには、ダンシングリンクエンジンのいくつかの実装があります。
おそらく、パズルの一般的な「制約」を評価できますか？新しいパズル（ヒントのみ）には、含めることができない値を削除するだけで決定できる特定の数のセルがある可能性があることを考慮してください。これらのセルは、通常のセルよりも少ない数の可能な値に「制約」されており、存在するより高度に制約されたセルは、推測せずにパズルを進めることができます。（ここでは、「推測」の要件がパズルを難しくしていると考えています。）
ただし、ある時点で、プレーヤーは推測を開始する必要があります。また、特定のセルに対して選択する値が少ないほど、正しい値を見つけやすくなる（そして他のセルの制約が増える）ため、セルの制約が重要になります。 ）。
もちろん、私は実際に数独をプレイしていません（ゲームとソルバーを書くのが好きです）ので、これが有効なメトリックであるかどうかはわかりません。ただ大声で考えてください=）
行、列、正方形のユニークな可能性だけを探す単純なソルバーがあります。この方法で解けるいくつかのセルを解くと、残りの候補を選び、それを試し、単純なソルバーが解または可能性のないセルにつながるかどうかを確認します。最初のケースではパズルが解かれ、2番目のケースでは、1つの可能性が実行不可能であり、したがって排除されることが示されています。3番目のケースでは、最終的な解決策にも実行不可能性にもつながりませんが、控除に達することはできません。
この手順を繰り返すことの主な結果は、正しいセルエントリを選択することで解決策が得られるまで可能性を排除することです。これまでのところ、この手順は最も難しいパズルでさえも確実に解決しました。それは複数の解決策で難なくパズルを解きます。トライアル候補がランダムに選ばれた場合、それはすべての可能な解決策を生成します。
次に、単純なソルバーが解決策を見つける前に排除しなければならない違法な候補の数に基づいて、パズルの難易度を生成します。
これは推測のようなものですが、単純なロジックで候補を排除できれば、最終的な解決策に近づきます。
マイク
私は過去にこれをしました。
重要なのは、人間の論理の観点から、どのルールを使用するかを理解する必要があるということです。提供する例では、右上がりのリストとして、さまざまな人間の論理パターンについて詳しく説明しています。
実際には、コンピューターのルールではなく、これらのルールを使用してパズルを解く必要があります（単純なパターン置換を使用すると、ミリ秒単位で解くことができます）。ボードを変更するたびに、「最も簡単な」パターン（たとえば、セルまたは行の単一の開いたボックス）からやり直して、使用する次の論理的な「ルール」が見つかるまでチェーンを下に移動できます。
数独を採点するとき、各方法論にはいくつかのポイント値が割り当てられます。これは、入力する必要のあるすべてのフィールドに合計されます。「単一の空のセル」は0になる可能性がありますが、「XYチェーン」は100になる可能性があります。必要なすべてのメソッド（および頻度）を表にして、最終的な重み付けを行います。それらの重み付けの期待値をリストする場所はたくさんありますが、それらはすべてかなり経験的なものです。あなたは人間の論理をモデル化しようとしているので、自由に独自の重みを考え出すか、システムを強化してください（実際にXYチェーンのみを使用する場合、パズルはより高度なメカニズムを必要とする場合よりもおそらく簡単です）。
また、ユニークな数独を持っていても、人間の論理では解決できないことに気付くかもしれません。
また、これは、標準のパターン化された方法で解決するよりもはるかにCPUに負荷がかかることにも注意してください。数年前、私がコードを書いたとき、私が作成した生成されたパズルのいくつかを解決するのに数秒（正確には忘れましたが、おそらく最大15秒）かかりました。
難易度がユーザーがパズルを解くのにかかる時間に正比例すると仮定すると、これは、時間の経過とともに理想的なアルゴリズムの結果に近づく人工知能ソリューションです。
上記の方法を使用すると、ソリューションは0（すでに解決済み/解決する時間がない）から1（ユーザーはおそらく平均時間でこのパズルを解決する）から2（ユーザーはおそらくこのパズルを解決するのに2倍の時間がかかる）まで評価されます。彼らの平均時間）から無限大（ユーザーはこのパズルの解決策を見つけるのに永遠にかかります）。