graphillionによるしろまるくろまるの解列挙
しろまるくろまるとは
リンク先を参照
また、しろまるくろまるは、
白丸と黒丸の境界に線を引くことで、「盤面の外からスタートして、すべての交差点を通り、盤面の外に抜ける一本の線」
を引くパズルとみなすことができます。
リンク先のモーメントが詳しいです
しろまるくろまるの盤面を列挙するには、
盤面サイズより1少ない格子グラフを考え、
格子グラフの外側2点を端点とする全マス通過パス
および
格子グラフ内の全マス通過ループ
の個数を列挙すればよいことがわかります。
関連
パス変換の際の注意
全マス通過ループは格子グラフのサイズが偶数の時のみ存在します（パリティにより証明可能）
全マス通過パスについても、出入のパリティが存在するため、選び方によっては解が存在しないことがあります。
https://gyazo.com/c4e9acf11d75fd7133cfe6e5bc877fb2
また、角を端点に選んだ場合、盤面の端に出る方法が2通りあります。
今回は同一視しますが、端点が角の時に2倍することで、区別した解の個数を求めることもできます。
https://gyazo.com/9a8acb3076732ef27b767f9572b54315
また、白丸と黒丸の塗り分け(2通り)も今回は無視します。
しろまるくろまるの解列挙について
組み合わせお姉さんで知られるグラフ上のパスの数え上げ問題について、
ZDDと呼ばれるデータ構造とフロンティア法が知られています。
これらを利用することで、しろまるくろまるの解の列挙もできそうな気がします。
今回はGraphillionを使用します。
Graphillionとは
部分グラフの列挙ツール
内部データ構造にZDDを持ち、内部アルゴリズムにはフロンティア法を利用している。
環境導入
pipを利用する
code:sh
% pip3 install graphillion
% pip3 install networkx
% pip3 install matplotlib
グラフ処理にnetworkx
描画用にmatplotlibを導入する
code: py
from graphillion import GraphSet
import graphillion.tutorial as tl
from itertools import combinations
size = 7
universe = tl.grid(size-1,size-1)
GraphSet.set_universe(universe)
まずは盤面を定義します。
tl.grid(row, col)
でrow x colサイズのセルの周囲のグリッドグラフ(つまり、頂点数 row+1 x col+1)を生成します。
今回は一辺がsizeのグラフを生成したいので、引数にsize-1を指定します。
全マス通過ループを求める
code: python
solutions = GraphSet.cycles(is_hamilton=True)
これだけで、全マス通過ループを列挙することができます。
（全マス通過しない場合はis_hamiltonをfalseにすることで列挙できます）
全マス通過パスを求める
code: python
solutions = GraphSet.paths(begin,end,is_hamilton=True)
こちらもあっさり列挙することができます。
begin, endには左上を1とした、頂点番号を設定します。
すべてのパスを求める
code: python
edge = []
for i in range(1,size):
edge.append(i)
edge.append(size*i+1)
edge.append(size*i)
edge.append(size*size+1-i)
edge.sort()
all_path = GraphSet()
for pair in combinations(edge,2):
solutions = GraphSet.paths(pair0,pair1,is_hamilton=True) print(pair0, pair1, len(solutions), flush=True) all_path = all_path.update(solutions)
solutions = GraphSet.cycles(is_hamilton=True)
print('cycles', len(solutions), flush=True)
all_path = all_path.update(solutions)
外側の頂点の集合を作成し、2点取り出した組み合わせについてパスを生成しています。
all_path.updateでマージした解集合を作成しています。
len(solutions) で解の個数を列挙することができます。
code: python
tl.draw(all_path.choice())
解の一つをmatplotlibにより列挙することも簡単にできます。
https://gyazo.com/2ac959223d93d9577f9d34308c22bdf9
無作為抽出もできるため、解空間の研究等にも使えそうです。
所要時間
10x10の盤面 (9x9の格子グラフ)で30秒程度
9x9の盤面 (8x8の格子グラフ)で2分程度
奇数サイズの方が取りうる端点の数が多く、盤面が複雑なのかもしれない。
追記
11x11では推定18時間程度、
回転・反転の対称性を利用し、一方の端点を1-5に限定することで探索量を減らすことができる
結果
table:
しろまるくろまる盤面サイズ パスの個数 解の数
4x4 6 48
5x5 154 440
6x6 1,476 4,552
7x7 64,508 213,260
8x8 2,806,528 10,095,300
9x9 496,791,812 1,491,131,588
10x10 101,264,393,212 330,618,741,128
11x11 77,429,984,803,716 179,514,396,139,752
解の数については角の解を2倍(両端が角の時は4倍)し、白黒入れ替えで全体を2倍している
結論と課題
とりあえずパスを列挙するだけならとっても簡単
内外の処理でフィルタを書くことができれば、白丸、黒丸の配置から解の個数を求めることができるが、良い扱い方が見当たらなかった。
小さいサイズであれば全解をメモリ上に列挙し、ヒートマップを作ることもできるかもしれない。
解の個数の推定から最小表出、標準的な表出数の考察ができるかもしれない。
参考文献
関連