14 Minesweeper Variants 2のパターン数

2024年12月12日Advent Calendar 2024、Advent Calender

この記事は、東京大学ゲーム研究会アドベントカレンダー2024、12日目の記事です。

はじめに

なんだかんだ今年も2回目のClomyです。このアドベントカレンダー企画も明日で折り返しらしく、時の流れが早いなと、しみじみしております……

さて今回の記事は、『14 Minesweeper Variants 2』の地雷の配置のパターン数を計算するものです。とはいえ、いろいろなルールで計算していると、収集がつかなくなり、結果だけ載せることになりそうだったので、明らかに少なそうな[2C][2G]、[2B]のそれぞれ5×5のパターン数を計算しました。

ほんの少しだけ、C105で頒布予定の会誌第124号での執筆内容に関わりがあったりしますので、よろしかったらそちらもどうぞ。

[2C][2G]のパターン数

こちらの方は、もう200問（5×5、5×5!の100問ずつ）解いちゃったよー、というような（おそらく多くの）方には需要がほとんど無いであろう小ネタになるでしょう。そのような方は、飛ばしてもらうのがいいと思います。会誌でも特に触れてないですし。

[2C][2G]5×5は、[2C]ルール、[2G]ルール、盤面の小ささがいい感じに制限し合ってしまい、おそらく最も地雷の配置のパターンが少ないであろう問題です。

まず、[2G]ルールの地雷のグループは、[2C]ルールにより、（テトリスの）IミノかOミノの形に限られます。さらに、これらの2個が斜めにつながる必要があります。これを5×5の盤面に収めるのは非常に大変で、パターン数はなんと12しかありません！具体的には以下です。

見た目通り、同じアルファベットi,o,u（適当にi(jklmn)o(pqrst)uから選んだ。）のものは互いに90°、180°、270°回転のいずれかで移り合います。実際の問題でも、元の問題の解法を回転させたものと全く同じ手順で解くことができます。

ちなみに他の操作として、上下反転、左右反転、対角線に関する反転2種が考えられますが、今の盤面に限れば（0°を含む）回転と同じ結果となります（どちらかの対角線に関する反転操作で不変なことが関係しています）。もちろん実際の問題では、安全マスが事前に与えられており、一緒になるとは限りませんが。

ちなみにこの12通りを一つにまとめたのが次の図です。

わかりにくい？自分もそう思います。完全に蛇足な気がしますが、せっかく作ったので載せておきます。

じーっと眺めていると、地雷の位置の上下・左右対称の位置は安全マスなんだな～とか、中心（C3）が地雷ならC1、A3、C5、E3は安全マス（逆もまた然り）なんだな～とか、見えてきますが、解く上で使った記憶がないんですよね。

アルティメットモードでやってたからってのもありますが、結局実際解くときは、[i-0]、[o-0]、[u-0]を意識し、頭の中でぐるぐる動かして、矛盾しないやつの共通部分を考えて解いていました。

そもそも、大抵は複数マス分の情報が与えられのですが、それはこの図から見るのはちょっと厳しいですね……

[2B]のパターン数

続いて、[2B]ルールの地雷の配置のパターン数を数えていきます。行列の積を1か所だけ使いますが、基本方針は高校数学レベルのはずです。

[2B]の各列の地雷数は橋の本数と等しいです。よって各列は以下の${}_5{}^{}\mathrm{C}_2^{}=10$パターンを持ちます。

このうち2つが互いに隣り合えるかどうかをまとめたものが以下の表になります。

	[a-+]	[b-+]	[c-+]	[d-+]	[e]	[f]	[d-−]	[c-−]	[b-−]	[a-−]
[a-+]	○	○	○
[b-+]	○	○	○	○	○
[c-+]	○	○	○	○	○			○
[d-+]		○	○	○	○	○	○
[e]		○	○	○	○	○	○	○	○
[f]				○	○	○	○
[d-−]				○	○	○	○	○	○
[c-−]			○		○		○	○	○	○
[b-−]					○		○	○	○	○
[a-−]								○	○	○

この○を1に、空白を0に変えた行列
$$\left(\begin{array}{cccccccccc}1& 1& 1& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 0& 0& 0& 0& 0\\ 1& 1& 1& 1& 1& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1& 0& 0& 0\\ 0& 1& 1& 1& 1& 1& 1& 1& 1& 0\\ 0& 0& 0& 1& 1& 1& 1& 0& 0& 0\\ 0& 0& 0& 1& 1& 1& 1& 1& 1& 0\\ 0& 0& 1& 0& 1& 0& 1& 1& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1& 1& 1\\ 0& 0& 0& 0& 0& 0& 0& 1& 1& 1\end{array}\right)$$
を考えます（グラフ理論では隣接行列と呼ばれます）。([x],[y])成分は、A列がパターン[x]、B列がパターン[y]が可能か不可能かを表しますが、それを、可能なら1パターン、不可能なら0パターンと言い換えただけです。

さてこの隣接行列の2乗
$$\left(\begin{array}{cccccccccc}3& 3& 3& 2& 2& 0& 0& 1& 0& 0\\ 3& 5& 5& 4& 4& 2& 2& 2& 1& 0\\ 3& 5& 6& 4& 5& 2& 3& 3& 2& 1\\ 2& 4& 4& 6& 6& 4& 4& 3& 2& 0\\ 2& 4& 5& 6& 8& 4& 6& 5& 4& 2\\ 0& 2& 2& 4& 4& 4& 4& 2& 2& 0\\ 0& 2& 3& 4& 6& 4& 6& 4& 4& 2\\ 1& 2& 3& 3& 5& 2& 4& 6& 5& 3\\ 0& 1& 2& 2& 4& 2& 4& 5& 5& 3\\ 0& 0& 1& 0& 2& 0& 2& 3& 3& 3\end{array}\right)$$
を考えます。すると([x],[y])成分は、A列がパターン[x]、C列がパターン[y]のときにB列の可能なパターン数となります（これを使えば行列の積を知らなくても計算できます。人間がやる仕事ではないですが）。このように、ちょうどn回分グラフの点を移るパターン数すべての情報を、隣接行列のn乗が持っているわけです。

[2B]5×5のパターン数は隣接行列の4乗の全ての成分和でもありますが、2乗を求めたのでこれを使いましょう。パターン[x]の行の数字の和はC列から、A列（またはE列）までの連続する3列の可能な地雷のパターン数を表します。各行の和は、$\left(14,28,34,35,24,46,35,34,28,14\right)$なので、全パターン数は
$$2({14}^2+{28}^2+{34}^2+{35}^2)+{46}^2+{24}^2=9414$$となります。ところで、上下・左右反転で移り合う盤面は、既に述べたように上下・左右反転した解法が使えてしまいます。そこで、そのような盤面を区別しないとした場合のパターン数を計算してみます。

まず、左右反転に関して対称なパターン数は
$$2(14+28+34+35)+46+24=292$$です。一方上下反転に関して対称なのは[e]、[f]パターンだけで、これらは互いに隣接できるので、パターン数は
$$2^5=32$$です。少し面倒なのが、上下反転と左右反転を両方行うと元に戻る盤面です。これはC列は[e][f]ですが、B(A)列が[*-+]ならD(E)列は[*-−]となります。もしくは両方[e]や[f]です。その、パターン数は
$$46+24=70$$です。さらに、上下・左右反転両方に関して対称なものは、
$$2^3=8$$です。よって、上下・左右反転で互いに移り合わないパターン数は
$$\frac{9414-\left(292-8\right)-\left(70-8\right)-\left(32-8\right)-8}{4}+\frac{\left(292-8\right)+\left(70-8\right)+\left(32-8\right)}{2}+8=2452$$
となります。

おわりに

[2B]5×5は、そもそも隣接行列にパターン[e]くらい1が並ぶと思ってたので、パターン数は${10}^5$の半分の5万通りくらいかなと予想してたんですが、結構少ないんですね。

これくらいなら、行列計算と少しの手計算で何とかなりましたが、これ以上はちゃんとしたプログラムを書いて計算させないと厳しそうです。

パターン数の並んだ表とか、じーっと眺めていろいろ考えるのは楽しそうなので、いつか一通り計算したいところです。もしくはだれか計算してくれないかなー。