14 Minesweeper Variants の solver 作成
14 Minesweeper Variants とは
確定したマス以外を選択すると必ず失敗するのが特徴です。
普通のマインスイーパーに比べていくつかの追加ルールがあります。
基本的な方針
マインスイーパーのあるマスが確定する <-> そのマスを「地雷」(もしくは「安全なマス」) と仮定した場合に、現状の制約を満たす盤面の作成をすることができない。
となります。現状確定していない全てのマスについて、「地雷」(もしくは「安全なマス」) と仮定し、現状の制約を満たす盤面を 1 つでも求めるかできるかを試せばよいことになります。
現状の制約を満たす盤面を 1 つでも求めるかできるか
盤面の解がなんでもよいので制約を満たすような盤面がつくれるかどうかに着目します。このような問題は制約プログラミング と呼ばれ様々な solver が存在します。今回私は CP-SAT ソルバー | OR-Tools | Google for Developers を使用しました。
N クイーン問題 | OR-Tools | Google for Developers 例示にあるこちらの N-Queen 問題なんかが理解できれば大半のルールは書くだけになると思います。
一部のややこしいルールの解法
C
序盤のルールですが、 solver 作りではこれが一番非自明です。
にほぼほぼ解説されています。
O
安全なマスに関しては C と同様のロジックで解けます。地雷マスに関しては、C における 0 の制約が 1 つのみではなく、外と隣接しているもののみ許すとなると解けます。
D
地雷マスならば隣接 4 マスにちょうど 1 つ地雷があると同値です。
S
C とほぼ同様の制約に加えて、パスである必要があります。 パスは C の制約が満たせているのであれば、「すべての頂点の次数が 2 以下かつ次数 1 の頂点は 2 つ以下」という制約を加えると解けます
W, P, E
W と P と E は、それぞれのマスにおいて、条件としてあたえられるパターンを全て列挙してどれかが満たせばよいとすればよいです。 W と P に関しては 許可されたグループとの割り当て | OR-Tools | Google for Developers を利用すると比較的簡潔に書けます。
