5

私は掃海艇ソルバーを作ろうとしています。ご存知のように、地雷原のどのフィールドが開いても安全かを判断する方法と、採掘されているフィールドを判断してフラグを立てる必要がある方法は 2 つあります。決定する最初の方法は簡単で、次のようなものがあります。

もし (X 周辺の地雷の数 – X 周辺で発見された現在の地雷の数) = X 周辺の未開拓の鉱区の数 X 周辺の未開拓の鉱区がすべて採掘される

if (X 周辺の地雷の数 == 現在 X 周辺で発見されている地雷の数) then X 周辺のすべての未開地は採掘されません

しかし、私の質問は次のとおりです。採掘されたまたは安全なフィールドを見つけることができず、複数のフィールドを調べる必要がある場合はどうなりますか?

http://img541.imageshack.us/img541/4339/10299095.png

例えばこんな状況。以前の方法では何も判断できません。したがって、これらのケースのアルゴリズムの助けが必要です。

これを行うには、A* アルゴリズムを使用する必要があります。そのため、アルゴリズムの次のステップで可能なすべての安全な状態が必要です。考えられるすべての安全な状態を見つけたら、それらを現在の最短パスに追加し、ヒューリスティック関数に応じて、パスのリストをソートし、開く必要がある次のフィールドを選択します。

4

2 に答える 2

8

恐ろしい問題ですが、興奮しすぎる前に、NP Completeness と Minesweeperを読んでください。また、いくつかの良い最悪のケースの例と、人間がそれらを解決する方法を説明している付属のプレゼンテーションも読んでください。それでも、基本的な剪定とヒューリスティックを使用すれば、おそらく時間の壁にぶつかることはないと予想されます。

ゲームを生成する問題はここで尋ねられます:マインスイーパ解決アルゴリズム. 代数的方法に関する非常にクールな投稿があります。また、 sudokuのようなものに対してローカル情報が十分でない場合と同様に、バックトラックを試すこともできます (つまり、推測して、それが無効になるかどうかを確認します) 。このテクニックについての素晴らしい議論を参照してください。

于 2013-04-11T19:45:01.457 に答える