POJ 2676 / 2918 Sudoku：回溯暴力求解優化

題目要求

標準 9×9 數獨，輸入多組測試案例，每組 81 個數字（0 表示空格），輸出填滿後的數獨。無特殊格式要求，僅需每行 9 位數字。

核心算法：DFS + 剪枝

1. 預計算每個格子屬於哪個 3×3 宮（ch[81] 映射到 0..8）。
2. check(step, k)：檢查第 step 格（行 step/9，列 step%9）能否填 k。
    - 掃描同行、同列、同宮是否已有 k。
3. dfs(step)：遞歸填寫。
    - 若 step ≥ 81 返回成功。
    - 若當前格已有數，直接遞歸下一格。
    - 否則嘗試 1..9，通過檢查則填入遞歸，回溯時清零。

完整代碼（含輸出格式處理）

#include <cstdio>
#include <iostream>
using namespace std;

int blockId[81];          // 0..8 表示所屬 3x3 宮
int blockStart[9][2] = {{0,0},{0,3},{0,6},{3,0},{3,3},{3,6},{6,0},{6,3},{6,6}};
int grid[9][9];

void initBlock() {
    for (int b = 0; b < 9; ++b) {
        int sr = blockStart[b][0], sc = blockStart[b][1];
        for (int dr = 0; dr < 3; ++dr)
            for (int dc = 0; dc < 3; ++dc)
                blockId[(sr+dr)*9 + (sc+dc)] = b;
    }
}

bool check(int step, int k) {
    int r = step / 9, c = step % 9;
    for (int i = 0; i < 9; ++i)
        if (grid[r][i] == k || grid[i][c] == k) return false;
    int b = blockId[step];
    int sr = blockStart[b][0], sc = blockStart[b][1];
    for (int dr = 0; dr < 3; ++dr)
        for (int dc = 0; dc < 3; ++dc)
            if (grid[sr+dr][sc+dc] == k) return false;
    return true;
}

bool dfs(int step) {
    if (step >= 81) return true;
    int r = step / 9, c = step % 9;
    if (grid[r][c] != 0) return dfs(step + 1);
    for (int k = 1; k <= 9; ++k) {
        if (check(step, k)) {
            grid[r][c] = k;
            if (dfs(step + 1)) return true;
            grid[r][c] = 0;
        }
    }
    return false;
}

int main() {
    initBlock();
    int T; cin >> T;
    while (T--) {
        for (int i = 0; i < 9; ++i)
            for (int j = 0; j < 9; ++j)
                scanf("%1d", &grid[i][j]);
        dfs(0);
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) printf("%d", grid[i][j]);
            puts("");
        }
        puts("");
    }
    return 0;
}

優化要點

• 位掩碼加速 check：用三個 int row[9], col[9], blk[9] 記錄已用數字，O(1) 判斷。
• 按空格數最少的格子優先搜索（MRV 啟發式）可大幅減少回溯。
• 本題數據規模小，基本 DFS 即可 AC。