迷宮是一種編碼系統，無論是單純地丟硬幣，或者是特定的走訪方式，就是在為每個細胞選擇一個編碼，牆面的形態不過就是基於編碼的呈現罷了，必要時，你還可以基於迷宮中各細胞被給予的編碼，進一步地轉換為其他編碼。

先來問一個問題，你知道如何走出迷宮嗎？如果是完美迷宮，最簡單的方式之一是沿壁法，也就是固定一隻手摸著牆壁，手不離牆面地前進，一定可以從入口走到出口，就道理而言很簡單，先前談過的，迷宮的路徑會形成一棵樹，摸著牆走，就是繞著整棵樹畫一圈。

給你一張迷宮的圖，你可以很簡單地畫出如上圖的紅線吧！那麼怎麼寫程式自動找出紅線的路徑呢？直覺地會想檢查每個細胞的牆面，不過仔細想想行不通，因為路徑在同一個細胞中是有進有出的，怎麼辦呢？

仔細觀察細胞中最短的紅線，例如上圖中左上角，由左往右的第一條紅線，就像是把細胞畫成四格，從左上格走到右上格，既然如此，把全部的細胞都切成四格好了：

喔！有趣了，正好都是從其中一格往另一格移動，把迷宮拿掉：

這張圖有意思了，紅線通過全部的格子，然而路徑又不重複， 也就是格子不會重複走過，這是一種哈密頓路徑，每個格子的中心都做為點的話，也就是由指定的起點前往指定的終點，途中經過所有其他節點且只經過一次。

是的！迷宮可以做為求哈密頓路徑的一種方式，眼尖的你可能發現了，方才的兩張圖，路徑並不同，當然，既然迷宮是隨機生成的，這樣的哈密頓路徑也會是隨機的，我曾經把這拿來做過隨機千本鳥居：

用迷宮編碼來編碼

將迷宮中全部的細胞都切成四格，路徑就是在格子間前進，想求得前進方向，直覺地也是會想查看格子旁有牆面，不過呢！有些格子沒有牆面呢！

上圖中問號處是沒有牆面，不過格子有一角接著牆，既然如此，就是判斷格子的四個角是否有接觸牆面就對了！來將接觸點畫出來：

如此一來，在每一格中，看看四個角的點分佈，就可以決定該怎麼走往下一格，如果將格子四個角的點分佈歸類，總共會有 12 種類型，依前進的上、下、左、右進一步分類，就會如下：

因為寫程式時需要有個值來作為判斷，上圖就為四個角加上數字，如果格子中該角有點，就加上該角對應的數字，加總的結果已經標在上圖的每個格子裡，如此一來，稍後寫程式只要根據數字，就知道要前進的方向了。

因為實際上哪些角要標上點，是根據方形迷宮中各細胞的牆面資料而定，上圖就像是把各細胞的編碼，轉換為各格子的編碼。

順便一提的是，〈蜂巢狀迷宮〉也是將方形迷宮做了編碼對應，雖然當時沒有特別強調出來，然而其實就是將方形細胞的無右牆編碼，進一步轉換為根據行數的奇偶，決定六角細胞是右上無牆還是右下無牆編碼。

實作哈密頓路徑

根據以上的說明，必須先有個方式，將迷宮中各細胞的牆面資訊，轉換為點的資訊，如果點使用一個二維陣列 dots 來儲存，有點的位置就標示為 true，就可以實作出以下的函式：

// 上牆轉點
function topDots(cell, dots) {
    const nx = cell.x * 2;
    const ny = cell.y * 2;
    dots[ny][nx] = true;
    dots[ny][nx + 1] = true;
    dots[ny][nx + 2] = true;
}

// 上右牆轉點
function topRightDots(cell, dots) {
    const nx = cell.x * 2;
    const ny = cell.y * 2;
    dots[ny][nx] = true;
    dots[ny][nx + 1] = true;
    dots[ny][nx + 2] = true;
    dots[ny + 1][nx + 2] = true;
    dots[ny + 2][nx + 2] = true;  
}

// 右牆轉點
function rightDots(cell, dots) {
    const nx = cell.x * 2;
    const ny = cell.y * 2;
    dots[ny][nx + 2] = true;
    dots[ny + 1][nx + 2] = true;
    dots[ny + 2][nx + 2] = true;  
}

// 邊界的牆轉點
function borderDots(dots) {
    for(let y = 0; y < dots.length; y++) {
        dots[y][0] = true;
    }

    for(let x = 0; x < dots[0].length; x++) {
        dots[dots.length - 1][x] = true;
    }
}

有了點的資訊，就可以計算每一格的角落值總合：

function dotValue(x, y, dots) {
    return (dots[y][x] ?         1 : 0) +
           (dots[y + 1][x] ?     2 : 0) +
           (dots[y + 1][x + 1] ? 4 : 0) +
           (dots[y][x + 1] ?     8 : 0);
}

有了角落值總合，就可以計算接下來要往哪一格走：

function nextCoord(x, y, dValue) {
    const dirTable = [
        [7,  0], [ 3, 0], [1, 0], // 上
        [13, 1], [12, 1], [4, 1], // 下
        [14, 2], [ 6, 2], [2, 2], // 左
        [11, 3], [ 9, 3], [8, 3]  // 右
    ];
    const offset = [
        [0, -1],  // 上
        [0,  1],  // 下
        [-1, 0],  // 左
        [1,  0]   // 右
    ];

    const i = dirTable.find(vi => vi[0] === dValue)[1];

    return {
        x: x + offset[i][0],
        y: y + offset[i][1]
    };
}

接著就可以拿哈密頓路徑了：

function hamiltonianPath(maze, sx = 0, sy = 0) {
    // 用來標示點的二維陣列
    const dots = new Array(maze.rows * 2 + 1);
    for(let y = 0; y < dots.length; y++) {
        dots[y] = new Array(maze.columns * 2 + 1);
    }

    // 處理每個細胞
    maze.cells.forEach(cell => {
        switch(cell.wallType) {
            case Maze.TOP_RIGHT_WALL:
                topRightDots(cell, dots); break;
            case Maze.TOP_WALL:
                topDots(cell, dots); break;
            case Maze.RIGHT_WALL:
                rightDots(cell, dots); break;
        }
    });
    // 處理邊界
    borderDots(dots);

    // 開始走訪每一格
    let current = {x: sx, y: sy};
    const path = [current];
    while(path.length < maze.rows * maze.columns * 4) {
        const v = dotValue(current.x, current.y, dots);
        const next = nextCoord(current.x, current.y, v);
        path.push(next);
        current = next;
    }

    return path;
}

底下是完整的範例：