《スリザーリンク自動解答アルゴリズム》

盤面の表現

ルールの解釈

スリザーリンクは、表向きは次のようなルールになっている。

a.次のルールに従って、辺に線を引く
b.マスに書いてある数字だけ、そのマスに接する辺に線が引かれる
c.線は途切れたり分岐したりしない
d.線は交差しない
e.線は全体で1つの輪になる

辺に線を引いて輪を作るというのは、マスを外側と内側に分けることになる。つまり、スリザーリンクは、マスを2色に塗り分ける問題と等価になる。マスを水色と黄緑の2色に塗り分ける問題と見た場合、スリザーリンクのルールは次のように表現される。このルールを塗り分けルールと呼ぶ。

A.次のルールに従って、マスを水色と黄緑に塗り分ける ( a. c. より)
B.(数字条件) マスに書いてある数字は、そのマスに隣接するマスの中で、数字の書いてあるマスと反対側(違う色)になるマスの数 ( b. より)
C.(境界条件) 盤面の外には水色のマスがあるとする ( a. より)
D.水色の領域、黄緑の領域はそれぞれ、連続している(ただし、水色は盤面の外を通って連続であればよい) (ルール D1. D2. と等価)
D1.(大域条件) 水色の領域、黄緑の領域はそれぞれ、8方向に連続している(同上) ( e. より)
D2.(頂点条件) 1つの頂点に対し、対角する2つのマスが黄緑で、残りの2つのマスが水色になることはない ( d. より)
E.(存在条件) 黄緑のマスが1つ以上存在する ( a. より)
点と点をつないで輪っかを作るマスを水色と黄緑に塗り分ける
輪っかが2つに分かれる黄緑の領域が連続でない
輪っかが2つに分かれる水色の領域が連続でない

ルールD1. E. 以外 ( A. B. C. D2. ) を使って解く方法を、局所的解法と呼ぶ。ルールD1. E. が必要な解法を大域的解法と呼ぶ。

用語の定義

ここで使う用語は次のように定義する。

盤面
問題として数字や点の書かれている範囲
頂点
盤面に書かれた点
頂点をタテヨコに結ぶ(途中に別の頂点が入らない)短い線
マス
4つの点に囲まれた小さな正方形、盤面の外にもマスがあるとすることもある
隣接する
2つのマスが辺を共有していること
8方向に隣接する
2つのマスが頂点を共有していること
領域
マスの集合
経路
2つのマス(マスA、マスB)に対して、マスA→マスP→マスQ→…→マスBという列で、マスAとマスP、マスPとマスQ、…が隣接しているもの
8方向経路
経路の条件の「隣接」を「8方向に隣接」に変えたもの
連続する
領域内のどの2つのマスも、領域内のマスだけを通る経路が存在すること
8方向に連続する
領域内のどの2つのマスも、領域内のマスだけを通る8方向経路が存在すること
同じ側
水色・黄緑の同じ色で塗られるマス
反対側
水色に塗られるマスに対して、黄緑に塗られるマス、またはその逆

途中状態の表現

塗り分けルールのうち、境界条件以外は水色と黄緑に対して対称である。そのため、塗る色が水色か黄緑かは外側からしか決定しない。内側から解くために、水色か黄緑かは分からないがこのマスとこのマスは同じ側(または反対側)、という状態を考える。このような状態では、同じ側のマスを、仮に同じ色、例えば青紫で塗る。また、青紫のマスと反対側のマスは灰色がかった青紫で塗る。青紫が水色と同じ側と判明したら、その時点で青紫を水色、灰色がかった青紫を黄緑で塗りなおす。また、青紫や水色・黄緑と関係なく、同じ側と判明したマスは、別の色、例えば橙色で塗り、その反対側は灰色がかった橙色で塗る。青紫と灰色がかった橙色が同じ側と判明したら、灰色がかった橙色を青紫で塗りなおし、橙色を灰色がかった青紫で塗りなおす。

以後、「灰色がかった」は、記号「¬」で表し、¬青紫や¬橙色という表記を用いる。

盤面の状態を図示する際、隣接するマスが反対側の場合は、分かりやすいように辺に線を引いて表現する。ただし、これは図示する際の方法であって、アルゴリズムとしては、辺に線が引かれているかどうかを考える必要はない。

また、他のマスと同じ側・反対側が全く判明していないマスについては、それぞれ別の色で塗ると煩雑になるので、このようなマスは白で表現する。



市岡 耕平