27

マインスイーパのようなゲーム (ルールを変更) を設計していますが、プレイヤーが推測できないようにしたいと考えています。私の目標は次のとおりです。生成されたボードにはいくつかの正方形が表示され、プレーヤーは推測なしでパズル全体を解くことができます。

ウィキペディアは次のように言及しました：

マインスイーパの一部の実装では、明らかになった最初のマスに地雷を配置しないか、ボードを配置して解が推測を必要としないようにすることで、ボードをセットアップします。

しかし、私はアルゴリズムを理解することはできません。

その上、別の StackOverflow の質問:マインスイーパ解決アルゴリズム

改善: ジェネレーターと一緒にソルバーを実行し、パズルに固有の解があることを確認します。これにはある程度の賢さが必要であり、ほとんどの亜種では行われていません。

これが本当に機能するかどうかは疑問です。マインスイーパが NP 完全であることはよく知られています。

要約すると、私の質問は次のとおりです。

  • 推測を必要としないマインスイーパ ボードを生成する方法は?
  • できるとすれば、具体的なアルゴリズムは何ですか?
  • この問題を多項式時間で決定論的に解くことができるでしょうか? この問題は NP 完全ですか? それを証明する方法は？
4

4 に答える 4

24

Simon Tatham の Portable Puzzle Collectionでのマインスイーパの実装は推測不要です。(これは MIT ライセンスでもあるので、必要に応じて彼の実装を自由にコピーできます。)

于 2011-11-29T04:23:35.367 に答える
12

マインスイーパが NP 完全であることはよく知られています。

これは本当ですが、おそらくあなたが思っているほど関連性はありません。提案されたアルゴリズムは、「コンピューターが解けるまでランダムなボードを繰り返し生成する」ようなものです。NP 硬度は最悪のケースの特性ですが、ここでは平均ケースの硬度に本当に関心があります。異常に硬いボードが生成された場合、ソルバーをタイムアウトにして、新しいボードで再起動できます。

また、良いボードと悪いボードを区別するオラクルがあったとしても、ユーザーが推測を避けるために難しい問題を解決しなければならないことを本当に望んでいますか? 才能のないコンピューター ソルバーは、より公正なボードを選択するようにバイアスをかける可能性があります。

于 2011-11-29T03:17:48.540 に答える