スリザーリンクの自動解答
JOI夏季セミナーでなぜかスリザーリンクを解くプログラムを作ってしまったので、スリザーリンクをプログラムで解く手法について説明したいと思います。
下準備
人間はスリザーリンクの問題をループの線ベースで考えて解いているが、これはプログラムに実装しようと思うと難しい。また、閉所への線の進入を禁止するのはかなり複雑な機構を必要とする。
ところで、スリザーリンクには高等テクニックに「線の内側か外側か考える」がある。ここで、すべてのマスが、線の内側か外側かわかっているなら、当然ループは復元できる。内側か外側かを管理して解くのは、線ベースで解くよりも簡単な方法がある。
よって、問題をループの内側、外側という概念を用いて解くことにする。
データ構造
いつでもループの内側、外側が即座に決まるわけではない。
盤面のど真ん中で２つの３が隣り合っている場合、当然線の引き方は少し決定するが、３がループの内外どちらに入るのかはまだ決定できない。しかし、例えば「２つの３はループで分断されるから、どちらかは内側で、どちらかは外側だ」というのはわかる。
ここで、もし「ある２つのマスは同じ側だ」という情報しか存在しないのなら、Union Findを用いると簡単に管理できる。しかし、「ある２つのマスは違う側だ」という情報も保持できるデータ構造がある。
これは、Union Findを利用したものである。
集合x1, x2, …, xnを管理するとき、同時にxiに対して常に反対側に位置するyiを仮想する。
そして、aとbが同じ側であるという情報があったらxaとxb、yaとybをマージする。
aとbが違う側であるという情報があったらxaとyb、yaとxbをマージする。
当然ながらxiとyiが同じunionに属しているなら、矛盾である。
これを用いると、ある2つのマスに対して、同じ側にある、違う側にある、もしくはわからない、というのが簡単に判定できる。
このデータ構造があれば、各数字マスに対する処理は、「線の引き方をすべて試し、矛盾しないものを選び、その共通部分をとる」だけでよい。
ループ判定
ここまでで簡単な問題は解けるが、まだループが閉じてしまう場合を考えていない。
今、ある「問題図上で縦横につながっていて、互いにすべて同じ側にある」領域を考える。この領域は小さい（閉じてしまうとループが２つ以上に分断してしまう）ので、他の隣り合っている領域とmergeして広がりたいとする。
隣り合っている領域は、領域のすべてのマスに対して隣マスを見ればわかる。ここで、mergeできる領域は、その領域との関係が未決定である領域のみである。もしそのような領域が１つしか存在しないなら、その領域とmergeしてよい。
このループ判定を用いると、かなりの問題が解けるようになる。しかし難しい問題にはまだ歯が立たない。ここで、仮定を導入すると、（１段の仮定でも）ほとんどの問題が解けるようになる。
