Most explosive
もっとも爆発的
引用元：https://www.ioccc.org/2020/endoh1/prog.c
審査員・作者による説明：https://www.ioccc.org/2020/endoh1/index.html
動作
半自動マインスイーパ。
$ gcc -o prog prog.c -lncurses
$ ./prog
端末で起動し、マウスクリックすると普通のマインスイーパのようにマスを開いて機雷の有無を調べる。
数字が出たら、その周りの8セルのうちその数だけ機雷があるということを意味する。
Rを押したら現在のゲームを捨てて新しいゲームを開始する。
Qで終了。
特徴は、簡単な推論でわかるところは自動的にやってくれてしまうところ。 上記の画面は、1クリックしただけで勝手に広がりきったところ。
初期配置を指定することもできる。
$ ./prog ioccc.txt
デモ動画。
解説
マインスイーパをプレイするときは、ふつう、次の2種類のアクションとなる。
- 機雷がなさそうなマスを第六感で選んでヒントを得る
- ヒントをもとに機雷がないマスを特定していく
しかし、(2)の方は間違いやすく、時間の無駄。こういう作業は機械にやらせるべき。 ということで、局所的な推論で機雷の有無が決定するマスを自動的に特定していく機能を備えたマインスイーパ。
ふつうのマインスイーパでも0のマスを開いた場合は自動的に周りのマスを開いてくれるものが多い。 その推論をもうちょっと賢くしたとも言える。
次の4つのルールに基づいて自動的に推論する。
- 周囲のマスにすでに数字と同じ数だけフラグが立っていたら、他のマスをすべて開く。
- 周囲のマスにすでに数字と同じ数しか閉じマスがなかったら、それらにすべてフラグを立てる。
- 隣接する2つの数字に注目したとき、大きい方の数字の周囲にどのように機雷があるとしても、小さい方の数字の分をカバーしきってしまう場合、小さい方の数字の周囲マスのうち大きい方の数字と共有していないマスをすべて開く。
- 隣接する2つの数字に注目したとき、小さい方の数字の周囲にどのように機雷があるとしても、大きい方の数字の分の残りが他のマスと同じ数になってしまう場合、大きい方の数字の周囲マスのうち小さい方の数字と共有していないマスにすべてフラグを立てる。
言葉ではわかりにくいと思うが、hint.textに例付きで書かれているので参照されたい。 コード上ではこれらのルールを単一の規則にまとめて表現している。