C 語言實現數獨求解器：回溯算法完整解析

專案背景

平時喜歡玩數獨遊戲，一日突發奇想：能否寫個程式自動求解？經研究，採用經典的回溯法，通過不斷試探與回退，即可破解所有合法數獨題目。

核心數據結構

使用二維陣列 int data[9][9] 表示棋盤，0 代表空格待填入數字。預載入一組測試數據：

int data[9][9] = {
    {0,7,0,2,6,0,9,0,0},
    {3,0,0,0,0,8,0,0,7},
    {0,9,0,0,5,7,0,0,0},
    {5,0,0,0,0,0,0,7,0},
    {0,4,7,3,1,2,8,5,0},
    {0,8,0,0,0,0,0,0,1},
    {0,0,0,8,2,0,0,4,0},
    {7,0,0,6,0,0,0,0,2},
    {0,0,4,0,3,9,0,8,0}
};

關鍵算法模組

1. 衝突檢測三部曲

在 (line, col) 位置放置 num 前，必須同時滿足三個條件：

• 3×3 宮檢查：計算所屬宮左上角座標，遍歷 9 格
• 行檢查：掃描同行 9 格
• 列檢查：掃描同列 9 格

int Check(int i, int j, int num) {
    return CheckSquare(i,j,num) && CheckLine(i,j,num) && CheckColumn(i,j,num);
}

2. 完成度判斷

int IsDone() {
    for (i=0; i<9; i++)
        for (j=0; j<9; j++)
            if (!Check(i,j,data[i][j]) || data[i][j]==0) return 0;
    return 1;
}

3. 遞迴回溯核心

void Calc() {
    if (IsDone()) { output(); return; }
    for (i=0; i<9; i++)
        for (j=0; j<9; j++)
            if (data[i][j] == 0) {
                for (x=1; x<=9; x++)
                    if (Check(i,j,x)) {
                        data[i][j] = x;
                        Calc();
                    }
                if (x == 10) { data[i][j] = 0; return; } // 回溯
            }
}

算法邏輯：找到第一個空格 → 嘗試 1~9 → 合法則遞迴 → 全試完無解則歸零回溯。

運行與擴展

main() 中直接調用 Calc() 並輸出結果。若需互動輸入，取消註釋 input() 即可。此解法結構清晰，易於移植至其他語言或擴展為圖形介面版本。