您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C 語言回溯法求解數獨：完整實現與優化思路

編輯：關於C

數獨是經典的約束滿足問題，回溯法是最直觀的求解策略。本文提供完整的 C 語言實現，並討論優化方向。

問題建模

9×9 網格，分為 9 個 3×3 宮
每行、每列、每宮包含 1-9 各一次
0 表示空格

核心檢查函數

// 檢查 3×3 宮
int checkSquare(int r, int c, int num) {
    int sr = (r / 3) * 3, sc = (c / 3) * 3;
    for (int i = sr; i < sr + 3; i++)
        for (int j = sc; j < sc + 3; j++)
            if (grid[i][j] == num && !(i == r && j == c)) return 0;
    return 1;
}

// 檢查行
int checkRow(int r, int c, int num) {
    for (int j = 0; j < 9; j++)
        if (grid[r][j] == num && j != c) return 0;
    return 1;
}

// 檢查列
int checkCol(int r, int c, int num) {
    for (int i = 0; i < 9; i++)
        if (grid[i][c] == num && i != r) return 0;
    return 1;
}

int check(int r, int c, int num) {
    return checkSquare(r, c, num) && checkRow(r, c, num) && checkCol(r, c, num);
}

回溯主遞歸

void solve() {
    // 找第一個空格
    int r = -1, c = -1;
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            if (grid[i][j] == 0) { r = i; c = j; break; }

    if (r == -1) {           // 無空格 = 解完成
        printGrid();
        return;
    }

    for (int num = 1; num <= 9; num++) {
        if (check(r, c, num)) {
            grid[r][c] = num;
            solve();         // 遞歸
            grid[r][c] = 0;  // 回溯
        }
    }
}

完整代碼

#include 

int grid[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}
};

int checkSquare(int r, int c, int num) { /* ... */ }
int checkRow(int r, int c, int num)    { /* ... */ }
int checkCol(int r, int c, int num)    { /* ... */ }
int check(int r, int c, int num)       { /* ... */ }

void printGrid() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) printf("%d ", grid[i][j]);
        puts("");
    }
    puts("");
}

void solve() {
    int r = -1, c = -1;
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            if (grid[i][j] == 0) { r = i; c = j; goto FOUND; }
FOUND:
    if (r == -1) { printGrid(); return; }

    for (int num = 1; num <= 9; num++) {
        if (check(r, c, num)) {
            grid[r][c] = num;
            solve();
            grid[r][c] = 0;
        }
    }
}

int main() {
    solve();
    return 0;
}

關鍵優化方向

優化	原理	效果
位掩碼	用 9 位整數表示行/列/宮已用數字，O(1) 檢查	極大加速
最少候選優先	選擇候選數最少的格子優先填寫（MRV 启發式）	大幅剪枝
預計算候選集	維護每個空格的合法數字集合，動態更新	避免重複檢查
Dancing Links (DLX)	精確覆蓋問題建模，Algorithm X + 雙向鏈表	專業級速度

位掩碼優化示例

int rowMask[9] = {0}, colMask[9] = {0}, boxMask[9] = {0};

void initMasks() {
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            if (grid[i][j])
                setMask(i, j, grid[i][j]);
}

void setMask(int r, int c, int num) {
    int bit = 1 << num;
    rowMask[r] |= bit;
    colMask[c] |= bit;
    boxMask[(r/3)*3 + c/3] |= bit;
}

int canPlace(int r, int c, int num) {
    int bit = 1 << num;
    int b = (r/3)*3 + c/3;
    return !(rowMask[r] & bit) && !(colMask[c] & bit) && !(boxMask[b] & bit);
}