棒倒し法という迷路作成アルゴリズムがある。

結構有名。

棒倒し法のアルゴリズムの詳細は省略する。

不思議に思っていたのは、２段目以降の棒は、上に倒すことができないという点。

でも冷静に考えてみたらすぐに分かった。

そんなわけで、メモっておく。

上に倒してはいけないというのは壁の線が閉路になるのを防ぐための方法。

逆に、閉路をつくろうと試みてみるとわかりやすい。

２段目以降の４点について考察する。


まず、左上の棒を右に倒す。次に右上の棒を下に倒す。



この状態で、この四点を棒倒しによって閉じた形状にするには、必ず、左下の棒を上に倒さないといけない。

逆説的に捉えるならば、下の段の棒を上に倒しても良いことにしてしまうと、閉路ができる可能性が生まれるのだ。

したがって、２段め以降の棒は上に倒せない。

では一番上の段はどうか。

これも、仮定の話を考えるとすぐに分かる。




外枠の線から下に棒は倒すことはできない。

したがって、図の右下と左下の２つの棒を倒して、閉路をつくろうとしても、もともと不可能。

だから、上に倒しても何の問題もないのである。

とにかく、1段目だけ4方向に倒すことができ、２段め以降は倒すことができない。これによって、棒倒し法はバランスの悪い迷路になってしまう。