マインスイーパーは、パソコンのおまけのゲームとして知られていますが、数学やコンピューターの研究でも話題になったことがあります。キーワードは「NP完全」です。

マインスイーパーはNP完全

2000年ごろ、数学者のリチャード・ケイが、マインスイーパーにかかわる次の問題が「NP完全」と呼ばれる難しい問題の仲間であることを示したとされています。

数字が書かれた盤があるとき、その数字と矛盾しない地雷の置き方が、1つでもあるかどうか。

ふだん遊ぶときに考える「このマスは安全か」という問題も、この問題と深くつながっています。

NP完全とは

NP完全をやさしく言うと、次のような性質を持つ問題です。

  • 答えが正しいかを確かめるのは簡単: 地雷の置き方を1つ見せてもらえば、全部の数字と合っているかは、すぐに確かめられます。
  • 答えを見つけるのは大変(と考えられている): 盤が大きくなると、置き方の候補が急に増えます。今知られているどの方法でも、どんな盤でも速く答えを見つけられるものは見つかっていません。

さらに、NP完全な問題どうしは、互いに言いかえられることが分かっています。どれか1つでも、どんな場合でも速く解ける方法が見つかれば、ほかのNP完全な問題も全部速く解けることになります。この「速く解ける方法があるかどうか」は「P≠NP予想」と呼ばれる有名な未解決問題で、100万ドルの懸賞金がかけられた問題の1つとして知られています。

置き方の数は、すぐに大きくなる

置き方を調べるのが大変なのは、候補の数がとても大きくなるからです。

  • 9×7の盤に地雷8個を置く置き方は、63マスから8マスを選ぶ組み合わせの数で、約39億通りです。
  • 26×15の盤に地雷75個を置く置き方は、390マスから75マスを選ぶ組み合わせの数で、80けたを超える数になります。

もちろん、実際に遊ぶときは全部を調べる必要はありません。数字に接していないマスはまとめて考えられますし、多くの場面は1つや2つの数字を見るだけで決まります。それでも、数字が複雑にからみ合った場面では、確実に答えを出すのが大変になることがあります。

アプリは、人の推理で解ける盤だけを選ぶ

アプリ「マインスイーパー」は、盤を作るときに、人が使う次の3つの決まりだけで最初から最後まで解けるかを確かめています。

  1. 1つの数字から分かること
  2. 2つの数字を組み合わせて分かること
  3. 盤全体の残りの地雷の数から分かること

どの決まりも、見る範囲が小さく、すばやく調べられます。この3つで解けない盤は、地雷を動かして作り直します。そのため、遊ぶ人も、全部の置き方を調べるような重い考え方をしなくても、必ず最後まで解けます。

このサイトの記事の中で遊べる盤も同じ考え方で作っています。パソコンで★5と同じ大きさの盤を作る時間を計ると、1面あたり平均で数ミリ秒でした。

パズルと数学

ナンプレ(数独)など、ほかの多くのペンシルパズルも、盤を大きくした一般的な形ではNP完全であることが知られています。人が楽しく解けるパズルは、「全部を調べなくても、筋道を立てて解ける」ように作られているものが多いのです。アプリ「マインスイーパー」の推測なしの盤も、その1つです。

確率の計算については、マインスイーパーの確率で紹介しています。