マインスイーパを解くその2 - プログラマーの脳みそ

　前回はマインスイーパを解くプログラムを作成する場合、単純なアルゴリズムだけでは解けない、そして工夫して論理的に解くアルゴリズムを作ったところで運任せの要素が強いことを示した。

　今回は地雷の配置を推測する、やや難度の高い部分について踏み込んでみよう。

　以下の図のような壁に隣接した1のマスのようなケースでは赤丸のうちどちらかに地雷があることがわかる。

　この場合、壁に隣接した1のひとつ上の1は、この赤丸の部分でカウント1と合致するわけだから、下から3番目、2のマスの隣が安全であることが分かる。

　二者択一で存在する地雷の、両方のマスを周囲に持っている場合、地雷1個分とカウントすることができる。このようなアルゴリズムで実装を考えてみよう。

　2以上の数字の周囲に二者択一を作成する場合、循環的に組み合わせをすることができ、ちょっと困ったことになる。

　2を起源に赤丸の部分に3組の二者択一を作成した場合、上の3のマスはこの3組の二者択一を周囲に含有するが、右上の2マスを開くことは出来ない。

　3つのマスをA,B,Cとした場合、

の3つの二者択一に分解出来る。このC or Aが曲者で、二者択一を含有していれば地雷1個とカウントする、と単純にプログラムするとこのようなケースで失敗する。

　では、組み合わせの循環が困るなら単純に排除すればよいかというとそうでもない。

　上記のようなケースでは、3の周辺に二者択一のグループが4つ作られる必要がある。周囲の2は、最外周部にひとつ地雷マークがつけば、安全にいくつかのマスを開くことが出来る。

　もう少し詳しく開設しよう。3のマスの四つ角に時計回りにABCDと名付けよう。

これにより、二者択一の組みを4つ作ることになる。

　このA or Bの二者択一により、上部の2は周囲に最低でも1つ地雷を保持していることが確定する。ここで、D or Aという第4の二者択一の存在がないと左側の2で二者択一によって地雷が1つ確定することを表現出来ない。

　しかし、中央の3には周囲に4つの二者択一が存在することになる。つまるところ、カウントが2以上のマスの周囲を複数の二者択一に分解するという単純なアルゴリズムではどうも処理が破綻するということだ。三者択二、四者択三といったケースは、やはりそのようなケースとして処理する必要が出てくる。

　二者択一のケースでは両方のマスを含有する周囲のマスに地雷のカウント1を与えられるということだった。通常同時に共有出来るマスは2or3だ。辺を共有すると三者択一は存在しうる。

　上記のようなケース。稀ではあるのだが、三者択一の共有で開ける例だ。青丸で囲った2つの1に注目。右の1は赤丸の部分に三者択一で地雷があることを表している。左の1はこの三者択一の範囲を共有するので、左上の緑丸の箇所を開くことが出来る。

　さらに稀ではあるが、四者択一が効果を発揮するケースがある。

　青で囲った2と1が問題の箇所だが、このような配置では4マスを共有する状況となるので、2が示す四者択一により、1の右下の緑丸を安全に開くことが可能となる。

　これらの事情から、n者択mとなる箇所を管理し、それを考慮できるかを探すようにプログラムしなくてはならない。

　この際、問題ケース1,2に挙げたように、2以上の数字の周囲を二者択一に分解し処理しようとする場合は同一起源のものをうまく管理しなければ誤って地雷のあるマスを開いてしまうことになる。

　対策としては、二者択一を表現するオブジェクトに由来となるマスを識別できる何かをもたせ、同一起源の場合になんらかの対処を行うという手法だ。

　二者択一となる箇所を両方含有する場合に地雷1個分とカウントする、という方法論を推し進めた場合、このようなケースでなかなか容易には進められない。イマイチ筋の悪いアルゴリズムとなってしまう。

　上で挙げた四者択一のようなレアなケースを想定すると、網羅性にも疑問が出てくる。果たして全てのケースを網羅出来るのだろうか、と。

　また、これらの処理を、常時行っても効果が薄いので、単純なアルゴリズムで進め、手詰まりとなったところで実施するというのがよいだろう。