マインスイーパを解くプログラム

マインスイーパを解くプログラムを,作ってみました.開発言語は,javaです.
Windowsに付属する普通のマインスイーパを解くプログラムです.



     ※ 他に細かい処理もしていますが,大まかには上記のような処理をしています.




解くための方法(解法アルゴリズム)は,以下のようにしています.

  1. 全てのパネル(マス)に,爆弾が在る確率を割り当てる(1.0/マス目数).
  2. 確率が最も低いマスを開く.同じ確率のマスが複数ある場合には,その中からランダムで1つを選択する.
  3. 開いたマスに表示される文字から算出できる,爆弾が在る確率を求める.例えば「2」が表示されていて,その周りに開いていないマスが4つある場合には,その4つの爆弾確率は,2/4=0.5となる.
  4. 3.で求めた確率が,すでにそのマスに与えられている確率よりも大きい場合には,そのマスの爆弾確率として採用する.
  5. 確率が1.0の所には,旗を立てる.そしてその周りの既に開いたマスにおいて,数字の数だけ旗のついたマスに左右同時クリック(周囲に残っているまだ開いていないマスを一斉に開く)をする.
  6. 2.に戻る.

上のような解法は,近くにある既に開いたマス同士の関係を考慮していないため,攻略法としては不完全です.例えば下のような場合,

というのが分かりますが,上記の解法では分かりません. (確率は低くなりますが,0とはなりません)
このような問題を解くには,直感的にはPrologによるプログラミングがやりやすいと思います.
(このプログラムは,今はjavaで書いています) ( Prologに関する資料 (ppt 125kbyte) )


例えば,既に開いたマスに「2」と書かれていて,その周りに5つのまだ開いていないマスが在る場合,爆弾の配置は,5*4/2=10通りあります.そのすべてにおいて,それ以外の開いたマスの数字と矛盾しなければ,1つの可能性として採択します.そして全ての採択された可能性の中で,上記のような確率的な処理を行い,最も可能性の低いマスを開ける,という解法が恐らく完全でしょう.

この可能性の列挙には,Prologが適していると思っています.全く調べていないですが,恐らく,もっと簡単な解法もあると思いますが・・・

戻る