ジグソーパズルを線形時間で解く

むりやり理想化を重ねて形式化したら，ピース数に対して線形時間でできることになりました。

1. すべてのピースに ID を振る
2. 各ピース p の各辺について，辺の形状を符号化し，符号からピース p へのマッピングを作成する。(この前処理により，辺の形状をキーとしてその辺をもつピースを定数時間で取得することができる)
3. 任意にピース p0 をひとつ選んで場に置き，p0 に隣接する各ピース p について (p, p0) をキューに入れる
4. キューが空になるまで以下の操作を続ける
   1. キューから ID の対をひとつ取り出す。それを (p, q) とする。
   2. p がまだ場に置かれていないならば，置く。このとき p は q に隣接するように置ける。
   3. q を場に置いたとき，隣接するピースが場に存在しない q の辺について，それに隣接するピース q' が存在するならば(つまり q が端のピースでないならば)取得し (q, q') をキューに入れる。

物理的に存在するジグソーパズルでこれをやろうとすると，空間計算量も線形なのが厄介そうですね。

辺のデータの符号化もピースを一意に特定できるような精度ではできないと思われるので (少なくとも人手では)，クラスタリングということになるでしょう。実際のパズルでは辺の形だけじゃなくて柄の情報も使えるのが普通なので，そのへんも合わせつつ。