推論だけで解けるマインスイーパ：運に頼る局面を作らない生成法

マインスイーパに負ける理由は二つあり、性質がまったく違う。

• 見落とし。これは自分の問題で、もう一度やればいい。
• 推測するしかない。確定推論を使い切った先が、賽の目しか残っていない。

二つ目が、このゲームをやめさせる。だから「ノーゲス」は難易度設定ではない。このゲームを技術のゲームとして扱えるかの前提だ。

定義は厳密でなければならない

ここを曖昧にすると実装がずれる。

ある盤面がノーゲスであるとは、最初のクリックからクリアまでの経路が存在し、その各手が確定推論のみで進められることをいう。

「経路が存在する」であって「どの分岐も推測を要さない」ではない。後者は強すぎて、本来良い盤面を大量に捨ててしまう。

さらに見落としやすい制約がある。ソルバはプレイヤーが見える情報しか使ってはならない。 答えを覗いて「このマスは地雷」と判定するなら、通った盤面は神視点では解けてプレイヤーには解けない。条件は満たすが価値はゼロだ。

最も素直な方法：生成して、解いて、駄目ならやり直す

loop:
  ランダムに地雷を配置
  安全な起点を開く
  if ソルバが最後まで推論できる: その盤面を返す
  else: やり直す

棄却サンプリングである。正しく、単純で、小さい盤面なら十分機能する —— 地雷密度が低ければ一発で通る確率は高い。

見苦しいのは裾だ。盤面が大きく密度が上がると命中率が急速に落ち、時には数十回から数百回やり直す。地雷配置が O(n) なら最悪は O(n × 試行回数) で、試行回数に上限はない。

より安い方法：作り直すのではなく直す

盤面全体を作り直す代わりに、推測を強いるマスそのものを直す。

1. 盤面を生成し、ソルバを走らせる
2. 詰まったら、どの推論でも確定できない未知のマスを集める
3. その一つを選び、地雷を移すか開く（周囲の情報も同時に変わる）
4. もう一度解く。数回直しても駄目なら、そこで初めて全体を作り直す

マス一つを変えるほうが、盤面全体の再生成よりずっと安い。実際にはほとんどの詰まりは地雷一、二個の移動で解ける。

ソルバをどこまでやるか

ここが唯一、判断が要る部分だ。確定推論には三段階ある。

段階	手法	範囲
一	直接の数え上げ：周囲の残り地雷数が未知の隣接数と等しい → 全部地雷、ゼロ → 全部安全	大半
二	部分集合と差集合：A の未知集合が B の部分集合 → 差は全部地雷か全部安全	かなりの量
三	局所列挙：境界の未知マスをある規模まで列挙し、全解で同じ値になるマスを探す	残りの大半

第二段階は「1-2-1」「1-2-2-1」といった古典パターンの一般化である。あれは規則ではなく、この段階の特殊例だ。

第三段階が分水嶺。数学的には依然決定的（全解で地雷なら地雷）だが計算量が増え、「列挙規模」が調整つまみになる。緩めれば生成が遅くなり、締めれば推測が必要な盤面だと誤判定される。

私は第二段階 + 小規模列挙に落ち着いている。第一、二段階で大半を覆い、列挙が残りのほとんどを食べ、それ以上に進んでも通過率の伸びは計算量に見合わない。

最初の一手

見落とされやすいが重要な点。最初のクリックは安全でなければならない。

定石は、最初のクリックの後に地雷を配置するか、起点とその八近傍を開けておくこと。これで二つ同時に解決する。

• 一手目で死なない —— 純粋に体験の問題
• 序盤に数字が並ぶ、つまり情報がある。そうでなければ初手は純粋な乱数で、ノーゲスの前提が最初から成立していない

ノーゲスが変えるもの

ゲームを簡単にはしない。難易度は盤面の大きさと地雷数で決まる。

変わるのは乱数が効く場所だ。「運が勝敗を決める」から「局面の形」へ移る。負けることは変わらないが、「ここは自分が見落とした」のか「ここは誰にも見えない」のかが変わる。

私にとってはそこが重要だ。繰り返し遊ぶ価値があるかどうかは、敗因を自分の判断に帰せるかで決まる。