1

ダンスリンクやその他の検索アルゴリズムを試しましたが、指定された1秒の制限時間内に機能しません。約100万のソリューションを持つ数独ゲームの場合、すべてのソリューションをカウントするのに約10秒かかります。

4

2 に答える 2

2

1Mの結果は少し怖いように聞こえますが、基本的に高速に解決するには、除去/制約の伝播のプロセスと、可能な限り最小の値を持つフィールドの徹底的な検索を使用する必要があります。

Peter Norvigからの優れた記事：すべての数独パズルを解く。

于 2012-07-08T12:13:00.200 に答える
0

数独 (すべてのソリューション) の標準的な解決アルゴリズムは、バックトラッキングを使用します。数独の従来のバリアントには 1 つのソリューションしかない (または少なくとも存在する必要がある) ため、人間のような手法を使用することもできますが、この場合は不可能です。したがって、バックトラックがおそらく唯一の方法になります。

しかし、いくつかのトリックを使用したい場合があります

  • ツリーの剪定 (バックトラッキング アルゴリズムの基本的な剪定戦略をより洗練された条件で拡張)
  • 大規模な並列処理 (いくつかのサブ問題が同じである可能性があり、したがって一度しか解決できないか、または他のスレッドのいくつかのブランチを切り取る可能性があるため、ソリューションの超線形加速の恩恵を受ける可能性があると思います)
  • 対称性と設定のいくつかの特別なプロパティを使用します。暗黙の知識がある場合、これはおそらく最良の戦略です
  • いくつかのブラックボックス アプローチを試すことができます。たとえば、大規模な検索空間での検索で高度に最適化された制約(ロジック) プログラミングなどです...
于 2012-07-08T21:01:03.990 に答える