(より詳しい解説は後日ブログで公開します)

内側の \(2\) 個の正方形のうち，左上側を 1，右下側を 2 とします．

迷路を観察すると，内側に深く潜り，中央の D の道を通り，外側に出ていく，という流れであることがわかります．これを入口と出口から同時に辿ると，1 と 2 のどちらを選んでいったかという列が一致する必要があります．

迷路を整理すると，

• A を使い，入口からは 211，出口からは 2 と選ぶ
• B を使い，入口からは 1，出口からは 211 と選ぶ
• C を使い，入口からは 2，出口からは 1 と選ぶ

のいずれかを繰り返すという形になっていることがわかります．

これは Post の対応問題のインスタンスです．一般的な解法は存在しないので，適当な方法で探索することになります．例えば，入口からと出口からの 1/2 列の差 (余っている suffix) が十分短い解が存在するので，それを状態としてグラフ探索をすると上手くいきます．