スリザーリンクの自動解答(続き)

http://d.hatena.ne.jp/semiexp/20100828/1283027177 とはまったく異なる手法によりスリザーリンクを解く試みをしました。

設計

前の手法と異なり、線を直接管理するようにした。

すると、基本的に「何か変更があった場所の近く」以外は新たに決まることはないから、更新を伝播させる方法が使える。すなわち、ある位置について解く関数を用意しておけば、その関数が新たに決まりうる場所について関数をさらに呼び出すことにより、高効率で解答を決定できる。背理法がない場合、関数呼び出し回数は(後述する線管理のコストを除くと)盤面の大きさの線形になり、きわめて効率が良い。実際、20*36 の問題について、前の手法によるプログラムの 90 倍近い速度を達成した。
さらに、この手法では、「解法が比較的人間に近い」というメリットがある。誰も簡単な問題に前バージョンのような「線の内外」の手法は使わないと思うが、この解法は人間が解く際の解法に近く、さらに「背理法の難易度」も評価することができるようになる。

データ構造

背理法

2 段以上の背理法が必要な問題は人間には解けないから、1 段のみとしてよい。