マインスイーパを解く
マインスイーパというとWindows付属のゲームとして有名だ。このゲームはプログラミングの腕試しとして多くの人が独自に実装を試みた、メジャーなテーマでもある。僕も幼い頃に実装を試みたプログラマのひとりだ。僕が実装を試みた中学生(92-94年)の頃と記憶している。マインスイーパは1989年の登場らしい。Windows3.1に標準搭載されたとのことだ。日本語版Windows3.1の発売が93年であることを考慮すれば、これを見て真似して作ったのだろう。
マインスイーパの実装は比較的難易度が低く、プログラミングの腕試しには調度良いのだろう。比較的苦労するのは周囲にひとつも地雷のないマスを開いた時に連鎖的にマスを開く処理の実装だろうか。C言語などであれば再帰処理を身につけていれば簡単だが、当時はPC-9801のN88-BASICであったから、いくらか苦労したのを覚えている。ネットで見かけた実装のなかには不完全にしか開けていないものも見かけた。
1.地雷マークをつける
まず、下図のような角の部分の1のような箇所を探して地雷マークをつける。
これは、よりプログラミング的に言えば、「周囲の閉じたマス」と「周囲の地雷マーク」をカウントし、
「マスの数字」 − 「周囲の地雷マーク」 ＝ 「周囲の閉じたマス数」
となっている箇所では、周囲の閉じたマスを地雷マークにする、という処理となる。
2.安全なマスを開く
マスの数字が1のとき、周囲に地雷マークが存在するなら、他の閉じたマスは全て開くことができる。
上図の場合、赤丸の1は左下の地雷マークだけしか周囲に地雷がないことを意味するから、他の閉じたマスを安全に開くことができる。
単純には解けないケース
上記1.と2.を繰り返すだけという簡単な実装では容易に手詰まりになる。
例えば次のケース。
右上の壁に接した1により、上部赤丸の2マスのうちいずれかに地雷があることがわかる。すると、左上角の1はこの2マスのどちらかにある地雷を指して1と言っているわけだから、左の3マス(緑の丸の箇所)は安全であることがわかる。これにより、左下の赤丸の位置に地雷があることが確定する。
また、次のケースを見てみよう。
この例では壁に接している二つの1が赤丸部分に地雷があることを意味し、その二つの地雷によって角が2となっていることがわかる。となれば、緑の丸の部分は安全に開くことができる。
こうした推論をどうプログラムするかがひとつの壁となるだろう。
残り地雷数
終盤となると、残り地雷数によって配置が判明するケースがある。これが役立つシチュエーションはかなり少ないのだが、論理的に解けるなら論理的に解けるようにしておきたい。
