從零手寫華容道小遊戲（一）：矩陣生成與隨機打亂算法

編輯：關於C語言

從零手寫華容道小遊戲（一）：矩陣生成與隨機打亂算法

作為編程新手，通過 CS50 公開課受啟發，決定親手實現一個類似華容道的滑塊拼圖遊戲。本文記錄第一階段：根據階數生成矩陣、隨機打亂、並解決「空位顯示」問題。

一、遊戲規則與數據結構

輸入階數 n，生成 n×n 矩陣
數字 1 到 n²-1 填充，剩餘一格為空位（用 _ 表示）
玩家移動空位相鄰數字，最終將矩陣恢復有序

二、核心步驟實現

1. 初始化有序數組

int square[n * n];
for (int i = 0; i < n * n; i++) {
    square[i] = i + 1; // 1, 2, 3, ..., n²
}

2. Fisher-Yates 洗牌算法（正確隨機打亂）

#include <stdlib.h>
#include <time.h>

srand(time(NULL)); // 以當前時間為種子，每次運行結果不同

for (int i = n * n - 1; i > 0; i--) {
    int j = rand() % (i + 1); // [0, i] 隨機索引
    swap(&square[i], &square[j]);
}

為什麼不用原文的 rand() % (n*n)？ 那種寫法會導致某些排列概率更高，不是均勻分佈。Fisher-Yates 保證每種排列等概率。

3. 交換函數：指針傳遞實現數值交換

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

4. 矩陣形式輸出

for (int i = 0; i < n * n; i += n) {
    for (int j = 0; j < n; j++) {
        printf("%2d ", square[i + j]);
    }
    printf("\n");
}

三、關鍵問題：最大值顯示為空位 `_`

遊戲規定最大數字 n² 代表空位，輸出時需特殊處理。

方法一：輸出時判斷

for (int i = 0; i < n * n; i++) {
    if (square[i] == n * n) {
        printf("%2c ", '_');
    } else {
        printf("%2d ", square[i]);
    }
    if ((i + 1) % n == 0) printf("\n");
}

方法二：抽象為函數（原文思路）

// 判斷索引 c 處是否為數組最大值
int is_max(int *arr, int len, int c) {
    for (int m = 0; m < len; m++) {
        if (arr[c] < arr[m]) return 0;
    }
    return 1;
}

// 主循環中調用
if (is_max(square, n * n, k)) {
    printf("%2c ", '_');
} else {
    printf("%2d ", square[k]);
}

四、完整代碼整合

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int *a, int *b);
int is_max(int *arr, int len, int idx);

int main(int argc, char *argv[]) {
    int n;
    printf("請輸入階數：\n");
    scanf("%d", &n);
    
    int total = n * n;
    int square[total];
    
    // 初始化
    for (int i = 0; i < total; i++) square[i] = i + 1;
    
    // 打亂
    srand(time(NULL));
    for (int i = total - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        swap(&square[i], &square[j]);
    }
    
    // 輸出
    for (int i = 0; i < total; i++) {
        if (is_max(square, total, i)) {
            printf("%2c ", '_');
        } else {
            printf("%2d ", square[i]);
        }
        if ((i + 1) % n == 0) printf("\n");
    }
    return 0;
}

void swap(int *a, int *b) {
    int temp = *a; *a = *b; *b = temp;
}

int is_max(int *arr, int len, int idx) {
    for (int m = 0; m < len; m++) {
        if (arr[idx] < arr[m]) return 0;
    }
    return 1;
}