サイト内検索

2016/02/06(土)マインスイーパーアルゴリズム(応用編)

この記事は概要からの続きです。
基本編ページ

計算の仕方:
1と2のそれぞれのセルでANDを取り、以下のルールで評価を行う。
・一致数
 →入力が?の場合は結果を問わず0とする
・不一致があった場合は評価値を-1にする
 →入力が?の場合は処理をスキップする

(全てのケースは別ページにまとめます)
今回は他のパターンは不一致で評価値0になるケースですが、以下のようにすると実践的になります。

例図
□|□|□|□|□|
□|□|1|2|□|
これも同じように考えてみましょう。
  • 1だけ
?|●|●|●|?|
?|●|1|2|?|
  • 2だけ
?|?|■|■|■|
?|?|1|2|■|
【凡例】
●:1だけの候補
■:2だけの候補
★:1と2の候補
?:いずれの候補でもない
?|●|★|★|■|
?|●|1|2|■|
同様のルールで評価の高い組み合わせは以下です。
以下はすべて1点です。
?|□|★|□|■|
?|□|1|2|□|
?|□|★|□|□|
?|□|1|2|■|
?|□|□|★|■|
?|□|1|2|□|
?|□|□|★|□|
?|□|1|2|■|
以下はすべて0点です。
?|●|□|□|■|
?|□|1|2|■|
?|□|□|□|■|
?|●|1|2|■|

?+?+?+?+?+?|□+□+□+□+●+□|★+□+□+□+□+□|□+★+□+□+□+□|■+□+■+□+□+□|
?+?+?+?+?+?|□+□+□+□+□+●|1+1+1+1+1+1|2+2+2+2+2+2|□+■+□+□+□+□|
(細かい内容は別ページにまとめます)

さて、最後に今まで出てきたすべてのパターンでORを取り、0になった場所は安全です。
この時の?は1とします。
(今回は例が良くないので安全地帯はありません)


別例で説明しましょう。
□|1|□|□|2|
□|□|□|3|□|
凡例
■:2→3
★:2→3
確:確定
●|1|★|確|2|
●|●|★|3|確|

分離します。

5点
□|1|★|確|2|
□|□|□|3|確|
□|1|□|確|2|
□|□|★|3|確|

 |1|★|確|2|
 |1|★|3|確|
この形まではできます。

配置は運ゲーですが、その際の最適な理論値は求められます。
これにアルゴリズムの話で最適解を求めるところまで突き詰めると
「最短クリック数でマインスイーパーを完了させる時、最短で何クリックで実現できるか」を測るのも面白そうです。
(空白である場所を探してクリックする等)

しかしこれを実装するとなると非常に難しい事に気づくと思います。
試しに6×6ぐらいでやってみるといいかも?
OK キャンセル 確認 その他