C 語言遞迴回溯法解迷宮：完整實作與視覺化輸出

從隨機生成到路徑搜尋：遞迴回溯法解迷宮完整教學

迷宮尋路是遞迴與回溯的經典應用。本文實作一個 10x10 迷宮：隨機生成牆壁/通路、從 (1,1) 起點搜尋至 (8,8) 終點、優先順序 右→下→上→左、找到路徑即輸出並結束、無解則提示。完整包含迷宮生成、遞迴搜尋、路徑標記、回溯還原、視覺化輸出。

資料結構與常數定義

#define N 10
#define WALL 1
#define PATH 0
#define VISITED 2  // 搜尋路徑標記

int maze[N][N]; // 0=路, 1=牆, 2=正確路徑

1. 隨機生成迷宮

void generateMaze() {
    srand((unsigned)time(NULL));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            // 邊界強制為牆
            if (i == 0 || i == N-1 || j == 0 || j == N-1) {
                maze[i][j] = WALL;
            }
            // 起點、終點強制為路
            else if ((i == 1 && j == 1) || (i == 8 && j == 8)) {
                maze[i][j] = PATH;
            }
            // 內部隨機：1/3 機率為牆，2/3 為路 (保證可解性較高)
            else {
                maze[i][j] = (rand() % 3 == 0) ? WALL : PATH;
            }
        }
    }
}

2. 列印迷宮 (視覺化)

void printMaze() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            switch (maze[i][j]) {
                case WALL:    printf(" █ "); break; // 牆
                case PATH:    printf("   "); break; // 未走過的路
                case VISITED: printf(" ● "); break; // 正確路徑
            }
        }
        printf("\n");
    }
    printf("\n");
}

3. 遞迴回溯搜尋核心

int found = 0; // 全域旗標，找到即停止

void findPath(int x, int y) {
    // 到達終點
    if (x == 8 && y == 8) {
        maze[x][y] = VISITED;
        printMaze();
        found = 1;
        return;
    }

    // 四個方向：右、下、上、左 (優先順序)
    int dx[4] = {0, 1, -1, 0};
    int dy[4] = {1, 0, 0, -1};

    for (int dir = 0; dir < 4; dir++) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];

        // 邊界檢查 + 是路 + 未訪問
        if (nx >= 0 && nx < N && ny >= 0 && ny < N &&
            maze[nx][ny] == PATH) {

            maze[x][y] = VISITED; // 標記當前點為路徑一部分
            findPath(nx, ny);     // 遞迴探索下一步

            if (found) return;    // 找到解，層層返回，保留路徑標記

            maze[x][y] = PATH;    // 回溯：還原為普通路，表示此路不通
        }
    }

    // 起點特殊處理：若四周皆牆且非終點
    if (x == 1 && y == 1 && maze[1][2] == WALL && maze[2][1] == WALL) {
        printf("No way out!\n");
        exit(0);
    }
}

4. 主程式整合

int main() {
    generateMaze();
    printf("Generated Maze:\n");
    printMaze();

    printf("Solving...\n");
    findPath(1, 1);

    if (!found) {
        printf("No solution found.\n");
    }
    return 0;
}

執行結果範例

Generated Maze:
 █  █  █  █  █  █  █  █  █  █
 █        █     █     █     █
 █  █  █  █  █  █  █  █     █
 █     █        █        █  █
 █  █  █  █  █  █  █  █  █  █
 █  █     █     █     █     █
 █  █  █  █  █  █  █  █  █  █
 █     █        █        █  █
 █  █  █  █  █  █  █  █     █
 █  █  █  █  █  █  █  █  █  █

Solving...
 █  █  █  █  █  █  █  █  █  █
 █  ●  ●  ●  █  ●  ●  ●  █  █
 █  █  █  █  █  █  █  █  ●  █
 █  ●  ●  ●  ●  ●  ●  ●  ●  █
 █  █  █  █  █  █  █  █  █  █
 █  █  ●  ●  ●  ●  ●  ●  ●  █
 █  █  █  █  █  █  █  █  █  █
 █  ●  ●  ●  ●  ●  ●  ●  ●  █
 █  █  █  █  █  █  █  █  ●  █
 █  █  █  █  █  █  █  █  █  █

核心概念解析

擴充方向

• 最短路徑：改用 BFS (佇列) 而非 DFS 遞迴。
• 記憶化/動態規劃：記錄到達各格的最短步數，避免重複計算。
• 迷宮生成演算法：Prim、Kruskal、Recursive Division 生成完美迷宮 (無迴路、唯一解)。
• 圖形化介面：SDL2、Raylib、OpenGL 繪製動畫過程。
• 非遞迴實作：自行維護堆疊 Stack 模擬遞迴，避免棧溢位。

常見錯誤

1. 忘記回溯還原 maze[x][y] = PATH，導致錯誤路徑殘留輸出。
2. 邊界檢查漏寫 nx >= 0 && nx < N，造成陣列越界崩潰。
3. 起點/終點被隨機生成為牆，導致無解 (程式已強制設為 PATH)。
4. 方向陣列順序錯誤，導致搜尋順序不符預期。

此範例展示了「狀態空間搜尋 + 遞迴回溯」的標準模板，同樣適用於八皇后、數獨、圖著色、組合生成等 NP 完全問題的精確求解。