またも迷路パズルに挑戦する

　朝日新聞のｂｅ版に載っていた迷路パズルを見て、またもその構造をアルゴリズム的な観点から記述してみたくなった。

　パズルは、７種類の絵札を８×７の行列状に並べたもので、この７種類の絵のうち３種類以内の絵をつなぎ合わせて１～７で示されるスタートからａ～ｇで示されるゴールまでの経路をつくるものである。

　７種類の絵を各ゴールの大文字記号Ａ～Ｇを使って表すと、次のようになる。表の左側には、上から順に１～７の数字が並ぶ。また、右側には、上から順にａ～ｇの記号が並ぶ。

Ｇ Ａ Ａ Ｇ Ｂ Ｂ Ｆ Ａ
Ｆ Ｆ Ｃ Ｄ Ａ Ｄ Ｇ Ｂ
Ｅ Ａ Ｆ Ｂ Ｇ Ａ Ｅ Ｃ
Ｄ Ｆ Ｃ Ｆ Ｂ Ｄ Ｆ Ｄ
Ｃ Ｃ Ｅ Ａ Ｅ Ｄ Ｃ Ｅ
Ｂ Ｇ Ｇ Ｄ Ａ Ｇ Ｅ Ｆ
Ａ Ｅ Ｃ Ｂ Ｄ Ｂ Ｃ Ｇ

　スタートおよびゴールとなる絵には水平方向に右側または左側の通路しかないが、その他の絵には、上下の境界線を除いて左右方向および上下方向の通路がある。

　たとえば、スタート点１とゴール点ｃの近くにある絵の可能な通路を・で表すと、次のようになる。

　　　　　　　　　　　　　　　　　・
　１｜Ｇ・｜・Ａ・｜　・・・　｜・Ｅ・｜・Ｃ｜ｃ
　　　　　　　・　　　　　　　　　・

　経路をつくる絵は３種類までしか使えないという制約を考慮すると、スタート点に続く２つの絵とゴール点に導く２つの絵との組合せは３種類までに制限される。この制約をスタートとゴールの組合せのマトリックスで表すと、次のようになる。ここで可能な組合せを＊で示す。

ａ ｂ ｃ ｄ ｅ ｆ ｇ
１ ＊ ＊ 　 　 　 　 ＊
２ ＊ ＊ ＊ ＊ ＊ ＊ ＊
３ ＊ 　 ＊ 　 ＊ ＊ 　
４ ＊ 　 　 ＊ 　 ＊ 　
５ ＊ ＊ ＊ ＊ ＊ ＊ ＊
６ 　 ＊ 　 　 　 　 ＊
７ ＊ 　 ＊ 　 ＊ ＊ 　

　そこで、スタートとゴールの可能な組合せについて一つ一つ経路を試すと、唯一の経路６－ｂを除いて他はすべて行き止まりになることがわかる。