マインスイーパーから学ぶ背理法
マインスイーパーは、誰もが経験したことがあるゲームだと思います。
地雷のないマスをクリックするゲームなのですが、攻略に重要なのはなぜそこに地雷がある(ない)のかという確信がなければなりません。
その考え方を、攻略法と共にここで学べたらと思います。
マインスイーパとは
ルール
・地雷がないマスをすべて開放できればクリア
・数字の書かれたマスの周りには、書かれた数の分だけ地雷がある
数字が描かれていないマスの周りには地雷がないので、数字が描かれていないマスの周りは自動的に解放される
・地雷をクリックすると負け
例えば、以下の盤面の場合
（ここでは、$0$のマスを数字が描かれていないマスの代わりとします）
| $1$ | $2$ | $2$ | ||
| $2$ | $0$ | $1$ | ||
| $1$ | $1$ | $3$ | ||
このように埋めることができます。
$○$:地雷が埋まっている場所
$×$:地雷が埋まっていない場所
(以下も同様)
| $×$ | $×$ | $×$ | $○$ | |
| $○$ | $1$ | $1$ | $2$ | $×$ |
| $×$ | $2$ | $0$ | $1$ | |
| $○$ | $1$ | $1$ | $3$ | |
| $×$ | $×$ | $×$ | $○$ | $○$ |
$1$の周り八方向には$1$つの地雷がある
$2$の周り八方向には$2$つの地雷がある
$3$の周り八方向には$3$つの地雷がある
というようなルールです。
表の右側の空欄は、地雷があるかどうか未確定の部分です。
このヒントだけで、少なくともこれだけ絞れるわけです。
大切なのは、地雷がなぜそこにあるのか、またはないのか、という根拠が大事なので、よく出てくるパターンと共に紹介します。
背理法の考え方
以下のような盤面を考えます。
| $1$ | $2$ | $1$ |
| $0$ | $0$ | $0$ |
まず、$2$の上に地雷があると仮定し、$○$をつけてみます。
| $○$ | ||
| $1$ | $2$ | $1$ |
| $0$ | $0$ | $0$ |
左右の$1$の周り八方向に、既に$○$が2つついているので、他の所には地雷はありません。
| $×$ | $○$ | $×$ |
| $1$ | $2$ | $1$ |
| $0$ | $0$ | $0$ |
しかし、これでは$2$の周りに$○$が2つつく、というルールに反するので、矛盾です。
この時、$2$の上に$○$がつく、という仮定をしていたので、この仮定が間違っていることになります。
つまり、本当は$2$の上に$×$がつく、が正解です。
| $×$ | ||
| $1$ | $2$ | $1$ |
| $0$ | $0$ | $0$ |
$2$の周りには$○$が二つつかなければならないのですが、残り2マスしかないので両方$○$で埋めます。
| $○$ | $×$ | $○$ |
| $1$ | $2$ | $1$ |
| $0$ | $0$ | $0$ |
これで地雷を探すことができました。
本来はこのように探しますが、よく出てくる盤面と地雷パターンを紹介します。
1,2,1
| $○$ | $×$ | $○$ |
| $1$ | $2$ | $1$ |
| $0$ | $0$ | $0$ |
理由
先ほど紹介した通りです。
また、1,2,1とありますが、以下のような場合も同様です
| $○$ | $×$ | $○$ |
| $2$ | $3$ | $2$ |
| $1$ | $○$ | $1$ |
下に$○$が一つあるので、$2$は$1$として、$3$は$2$として扱うことができます。
1,2,2,1
| $×$ | $○$ | $○$ | $×$ |
| $1$ | $2$ | $2$ | $1$ |
| $0$ | $0$ | $0$ | $0$ |
理由
仮に以下の様な配置だとします。
| $×$ | |||
| $1$ | $2$ | $2$ | $1$ |
| $0$ | $0$ | $0$ | $0$ |
左からニ番目の$2$は、残り2マスしかないので、両方に$○$をつけます。
| $○$ | $×$ | $○$ | |
| $1$ | $2$ | $2$ | $1$ |
| $0$ | $0$ | $0$ | $0$ |
一番右の空欄を$○$にすると、$1$の周りに$○$が2つつくことになり、ルールに矛盾します。
一方で、$×$にすると$2$の周りに$○$が1つしかないので、やはりルールに矛盾します。
どちらにせよ矛盾するので、仮定が間違っていることになり、$2$の上は$○$になります。
右から二番目の$2$に関しても同様です。
2,3,2
| $○$ | $○$ | $○$ |
| $2$ | $3$ | $2$ |
| $0$ | $0$ | $0$ |
理由
$3$の周りには$○$が3つついていなければなりませんが、残り3マスしかないので、全てのマスに$○$をつけます。
2,3,3,...,3,2
| $○$ | $○$ | $○$ | $○$ | $○$ |
| $2$ | $3$ | $3$ | $3$ | $2$ |
| $0$ | $0$ | $0$ | $0$ | $0$ |
理由
$3$の周りには$○$が3つついていなければなりませんが、残り3マスしかないので、全てのマスに$○$をつけます。
$3$はいくつあっても同じです。
1,3,1
| $○$ | ||
| $3$ | $1$ | |
| $1$ | $0$ |
理由
以下の盤面と仮定します。
| $×$ | $×$ | |
| $3$ | $1$ | |
| $1$ | $0$ |
$3$の周りには$○$が3つついていなければならず、残り3マスしかありません。
もし、この3マスを$○$で埋めてしまうと$1$の周りに$○$が2つつくことになるので、ルールと矛盾します。
よって、この仮定は間違いです。
ということは、以下の盤面も間違いです。
| $○$ | $○$ | |
| $3$ | $1$ | |
| $1$ | $0$ |
よって、以下のどちらかとなります。
| $○$ | $×$ | |
| $3$ | $1$ | |
| $1$ | $0$ |
| $×$ | $○$ | |
| $3$ | $1$ | |
| $1$ | $0$ |
左側の空欄も同様に、$1$の周りには$○$と$×$が1つずつつくはずです。
場所は未確定ですが、$3$の周りには$○$が2つあることがわかりました。
ということは、$3$の周りの残りのマスには、残り1つの$○$がつきます。
| $○$ | ||
| $3$ | $1$ | |
| $1$ | $0$ |
1,4
| $○$ | $○$ | $○$ |
| $○$ | $4$ | $2$ |
| $1$ | $1$ | $0$ |
理由
$4$の周りには$○$が4つついていなければならず、残り4マスしかありません。
よって、$4$の周りのマスすべてに$○$がつきます。
まとめ
全てのパターンの配置を把握することは難しいですが、ほとんどのパターンは背理法で考えることができます。
これは学校の数学の公式に言えることかと思います。
特定のパターンは公式でどうにかなるのですが、公式に当てはまらないパターンが出てきたときに対処しようと思うと、公式よりも考え方が重要だったりします。
マインスイーパも数学の公式も同じで、速さを求める場合は公式を覚えてもよいですが、問題をじっくり解決する場合は考え方を重視した方がよいかと思います。
