「稍微曲折的迷宮」之後

頗訝異於網路的高效率。

昨天貼出「稍微曲折的迷宮」後，不到半天就有人回應，說這裡有張曲折的迷宮圖，而這裡是它的路徑解答。

喔， 那可是張很大 (3002x3002) 的迷宮圖呢。很可惜，我沒有找到產生這張迷宮的演算法（與程式）。不過，有時直接看到答案，雖然會有「啊哈，原來如此」的痛快，但緊接著可能就會有些莫名 的失落。找不著答案，我們可以試著修改自己的演算法，想想如何才能產生蜿蜒曲折的迷宮。而探索，不也是一種樂趣嗎？

昨晚花了些時間，修改程式來做些實驗。終於，我們可以產生像右圖般的迷宮了。它看起來比昨天的迷宮，就蜿蜒曲折了許多（雖然我們也還是沒有定義出什麼叫做「蜿蜒曲折」）。

這個迷宮是如何被產生的呢？

回顧之前提過的一個想法：或許可藉由增加迷宮的直徑（diameter，就是最長的兩端點距離）來產生曲折的迷宮。但是，要用什麼方式來怎樣增加迷宮的直徑，才能夠依然保持演算法的簡潔呢？

一個「也算直觀」的想法，是在產生迷宮的樹狀圖（8 月 25 日 post 的集合 T）時，儘量增加 T 的高度（height，由根節點到任意節點的最長距離）。也就是說，每當我們從集合 C 裡，要選出「可被打破的牆」時，儘量選「能夠繼續增長迷宮樹狀圖高度」的牆來打破。

最簡單的一種方式，是當我們要將節點四周「可被打破的牆」放入集合 C 時（參考 8 月 25 日 post 的步驟 2），實際上只選一面牆放入集合 C （其他的幾面牆，則放入另一個串列 C2）。如此一來，我們可以讓 T 以類似深度優先 (depth-first) 搜尋的方式向外延伸，而能夠相對容易地增加 T 的高度。

那麼，如果 T 已經「碰到絕處」，無法用深度優先搜尋繼續往下增長時，該怎麼辦呢？此時，我們可以由 C2 取出最後面的牆來打破。如此持續進行，直到 C 與 C2 都是空集合為止。（喔，只是稍微修改 8 月 25 日 post 的「基本演算法」，產生出來的結果，竟然就會有如此大的差異...）

我想，或許迷宮真的是一個不錯的主題吧（連 MPH 從前也曾嘗試用「笨方法」產生曲折迷宮呢）。而回顧這些曾感興趣的問題，總讓我對從前懵懂的歲月，有著淡淡的感傷、歡喜與寂寞。