迷路のアルゴリズムの延長として、一筆書きについて考えてみる。

ただし、普通の人が一筆書きと聞いて思い浮かべるような以下のような問題は、私がやりたい一筆書きとはちょっと違う。



この一筆書きは、同じ点を何度も通ることができる。

迷路で同じ点を何度も通るというのは、ループが生じることを意味するから、好ましくない。

一筆書きにはもうひとつのタイプが存在する。

その代表的なものがハミルトン閉路問題。絵が出る迷路の作成にも応用されることがある。

問題：全ての点を1度だけ通る経路を見つけてください。

この問題が、このページの冒頭に挙げた一筆書き問題と異なるのは、各点を一度しか通れないこと。その代わり、すべての辺を通る必要はない。

答え

ただ、ハミルトン閉路は、「閉路」なので、始点と終点が一致する必要がある。

私が考えている一筆書きの問題は、始点と終点を一致させる必要はない。

たとえば、以下のような点を結ぶ一筆書きの経路は、だれでも簡単にわかる。


でも、もし、数字を添えて、数字が書かれたマスを順番に通る必要があるという条件をつけると、問題を難しくすることができる。


上の問題は、十分簡単だが・・・。

一筆書き経路の問題についてはまた別の機会にあらためて考察しようと思う。