1

まず最初に - はい、これは宿題です - しかし、これは主に実用的な問題ではなく理論的な問題です。私が正しく考えているかどうか、またはそうでない場合はヒントを求めているだけです。

私は単純な数独ソルバーをコンパイルするように依頼されました ( Prolog上ではありますが、現時点ではそれほど重要ではありません)。唯一の制限は、Best-First Algorithmを使用したヒューリスティック関数を利用する必要があることです。私が思いついた唯一のヒューリスティック関数を以下に説明します。

1. Select an empty cell. 
  1a. If there are no empty cells and there is a solution return solution.
      Else return No.
2. Find all possible values it can hold. %% It can't take values currently assigned to cells on the same line/column/box.
3. Set to all those values a heuristic number starting from 1.
4. Pick the value whose heuristic number is the lowest && you haven't checked yet.
   4a. If there are no more values return no.
5. If a solution is not found: GoTo 1.
   Else Return Solution.

// I am sorry for errors in this "pseudo code." If you want any clarification let me know.

それで、私はこれを正しくやっていますか、それとも他の方法があり、私のものは間違っていますか? 前もって感謝します。

4

3 に答える 3

1

Prolog で数独ソルバーを自分で書いたとき、使用したアルゴリズムは次のとおりです。

  1. すでに解決済みのセル (つまり、最初に指定された値) を除外します。
  2. セルごとに、すべての隣接セル (20 セル) を含むリストを作成します。
  3. 各セルに対して、取り得るすべての可能な値を含むリストを作成します（上記が完了すると、簡単に実行できます）
  4. 解決するすべてのセルを含むリストで、使用可能な値の最小数を持つセルを一番上に置きます
  5. 一番上のセルの残りの可能性が 0 の場合は 7 に進み、それ以外の場合は 6 に進みます。リストが空の場合は解決策があります。
  6. リストの一番上のセル: セルの可能な値から乱数を選択します。隣接するすべての可能な値からこの値を削除します。5に行きます。
  7. バックトラック (つまり、Prolog で失敗)

このアルゴリズムは、常に「最も解決された」セルを最初にソートし、十分に早い段階で障害を検出します。ランダムなセルを解くアルゴリズムと比較して、解く時間が大幅に短縮されます。

于 2012-04-13T11:04:32.707 に答える
1

私が使用するヒューリスティックは次のとおりです。

  1. 挿入できる数字が 1 つしかない空のスペースを繰り返し見つけます。当てはまる数字1-9を入れてください。
  2. すべての空きスペースに 2 つ以上の可能性がある場合は、ゲームの状態をスタックにプッシュし、ランダムな正方形を選んでランダムな値を入力します。
  3. 手順 1 に進みます。

すべてのマスを埋めることができれば、有効な解決策を見つけたことになります。

有効なオプションがなくなった場合は、最後のゲーム ステートをスタックからポップします (つまり、最後にランダムな選択を行った時点に戻ります)。別の選択をして、もう一度やり直してください。

興味深い補足として、貪欲な発見的アプローチを使用してこれを行うように言われましたが、数独は実際にはブール充足可能性問題 (SAT 問題) に還元され、汎用の SAT ソルバーを使用して解決できます。これは非常に洗練されており、実際にはヒューリスティックなアプローチよりも高速です。

于 2012-04-13T01:25:47.710 に答える