簡単なところを勝手に進めてくれてしまうマインスイーパです。若干考える余地が残っていますが、ほとんど運の勝負です。
http://dame.dyndns.org/misc/semiautomine/mine.jnlp
マインスイーパ 2000 プロジェクトという鬼のようなゲームをやりながら作りました。クリアしたよ!
マインスイーパは非常に機械的な作業の多いゲームで、誰しも一度は自動化を考えると思います (特にマインスイーパ 2000 をやると) 。しかし完全な自動回答は明らかに NP 完全の香りがするので*1、SemiAutoMine は以下の4点だけ自動で推論します。
- 数字マスの周りにフラグマスと不確定マスが数字と同じ数しかない -> 周りの不確定マスに全部フラグを立てる
??? フフフ ?:不確定マス *5フ ==> *5フ フ:フラグマス **フ **フ *:数字マス
- 数字マスの周りにフラグマスが数字と同じ数だけある -> 周りの不確定マスを全部開ける
??? 開開開 *2フ ==> *5フ **フ **フ
- 隣接する数字マスと数字マスから確実に機雷があるところ、ないところを判定する
???? 開??フ *12* ==> *12* **** ****
- 1 つ開けて隣接する数字マスと数字マスから確実に機雷があるところ、ないところを判定する
**??? **?開開 *1?1? ==> *1?1開 **??? **?開開
ただバグがあるので推論してくれないときもあります。原因は dirty flag の管理が適当なせいだとわかっているのですが面倒で直す気がしません。future work です。
少し一般化して、影響範囲が重なる任意の 2 つの数字マスについて推論するようにしたかったのですが、面倒で直す気がしません。future work です。
あと、下のような推論も面倒で実装する気がしません。future work です。
**** **** *01? *01? *12? ==> *12? *??? *??開
あ、SemiAutoMine はクリアしたことがないので、バグがあったらすみません (笑)
*1:マインスイーパの解の存在判定は SAT に還元できるそうな。