ロードオブザリンク (Cマガ電脳クラブ)

久々にCマガ電脳クラブに応募した。
C++が使えないというのはすでに私にとっては痛い。痛すぎる。
今月(10月号…もう先月号になるのか?)の問題はロードオブザリンクなる
要するにナンバーリンクだった。
問題文にも書いてあったが、今回は枝刈り勝負だろう。

問題のサイズはとりあえず8*8である。

・・・Ａ・・・・
・Ｂ・・・・Ｃ・
・・・・・・・・
・Ｃ・・・・・Ｅ
・・・Ｄ・・・・
Ｅ・・・・・Ｂ・
・・Ａ・・・・・
・・・・・・・Ｄ

この程度なら何も考えなくても何とか実用的な時間で解ける
…のであるが、それではやっぱり面白くないし、
そんなプログラムを送るなんてそもそも応募する意味も無いだろう。

で、枝刈りなのである。
実はナンバーリンクのソルバーは一年以上前に作ったことがあって
(そのときはC++使った)
それで10*10あたりまでならば一瞬で解ける程度のものは出来上がっていたのだが、
今回、問題の条件が
・通らない交点が有っても良い
・リンク線が最短でなくても良い
という本来のものよりもゆるい条件で、かつ解の個数を求めよ
というものなので、そこに実装してあったプログラムの
枝刈り条件の半分以上が使い物にならない状態ということに。

まず参考のために探索ノード数を計ってみる。
何も枝刈りしないとき → 大体360万ノード
前に作ったやつ → 100ノードぐらい

何も枝刈りしなくてもまぁ、こんなもんか、といった程度だろうか。
これで大体1分弱…?だっただろうか。
前に作ったやつはさすがに一瞬だった。
前に作ったやつは、通らない交点は無い、としたり、
リンク線が最短のものに限ったり、いろいろ探索抜けがあるはずなのだが、
"今回の問題"はエレガントな(?)問題だったので、答えに相違は無かった。
(意地悪だなぁ)

とりあえず、エレガントじゃない解答も列挙できる範囲で枝刈りを組み込んでみた。
まず、
・端がどこにも延長できないような線が存在したらだめ
・同じ記号から伸びる2本の線が、一度も線が通っていない交点のみを使って
接続できないとだめ
このあたりの単純な条件で行ってみた。
(書き忘れたが、探索は記号から線をにょろにょろと延ばす方式である。
あまり良い方法ではないかもしれない…が、まぁいいか…ということで)
両方とも簡単な条件だが、大体これで探索ノードは4万程度になった。
実行時間はこれで1.5秒ぐらいである。

もっと時間を短縮したい。…のだが、実のところこの辺で
いっぱいいっぱいで、送ったものはこのレベルのものに成ってしまった。
ちょっと悲しい。しかし、枝刈りのアイデア自体は他に色々と考えたのである。

・線が延長できるかどうか、を表面的にだけではなく再帰的に調べてみる。

今のところ線が上下左右の方向に延長できるかどうかは、
そっちが空白のマスであるかとか、同じ記号のもう一つの端があるのだとか
そういうののみで決定しているが、
そっちに伸ばしてしまうと他の線がつなげなくなる…
などもうちょっと先を読んで決定してみるなどしてみた。
確かに探索ノード数は減った。
(1手先読みで数千ノードに、4手ほど読むと数十ノードになった)
…が、チェックに時間がかかりすぎて余計に遅くなってしまった。
確か昔に作った何か別のソルバーでは非常に有効な手法だった
記憶があるのだが、どうもナンバーリンクでは良くなかったらしい。

・2つの記号の端点の関係から不可能な盤面を探してみる

例えば、

A...B
.....
.....
.....
B...A

などの状況が出てくるとこの時点でアウトなのだが、
これを検出できないかなぁと思った。
なんだかグラフ理論的に多項式のアルゴリズムが存在しそうな雰囲気は
あるのだが、どうにもこうにも浮かばなかった。
これを一般的に、n個の記号の関係から接続が可能かどうか…
という問題はこの問題自体になってしまうのだが、
1つの記号なら自明に可能。2つなら或いは…と。

・2つの記号の端点に対して、双方が絶対に通らなければならない点がある

A.C.A
..|..
..C..
B...B

こういう盤面でAとBは同時につなげない。

A.C.A
..|..
..C..
BxxxB

xで示された箇所はABともに通らなければならず、
こういう地点が存在するとアウトなのである。
これについてはO(n^2)(nはマスの数)のアルゴリズムが
結構すぐに思いつくが、(通らなければならない点かどうかは
その箇所を通らないパスが存在するか否かで分かる)
が、探索しているノードを見てみてもこういうケースはそんなに多くなかったし、
軽くない処理になりそうなので、やっぱり実装しないことに。

・空きマスの数

同じマスは二回以上通れない。
ので、各記号の端点をつなぐ最短距離の合計が空きマスの数を超えている場合、
その時点で不可能だといえる。
空きマスには行き止まり(隣接3方向以上がすでに線が通っているマスとか)の地点を
カウントしなくて良い。
これを実装することにより、探索ノードはおおよそ半分になった。
(正直期待はずれというか…)
計算にも時間がかかるので、結局実行時間は倍ぐらいになってしまった。

………

というわけで、いろいろやってみたりはしたものの、
どれも良い結果にならなかった。
今回は正直完敗…というか、ナンバーリンクは難しかった。
しかしまぁ、色々考えることが出来て楽しかった。