您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

POJ 2676 Sudoku - 數獨求解器優化回溯

編輯：C++ 入門

題目大意

標準 9×9 數獨，多測資。每行、每列、每 3×3 宮數字 1-9 不重複。
輸入 0 表示空格。輸出任一合法解。

優化回溯關鍵技術

1. 位掩碼 / 布爾陣列快速檢查

bool row[10][10], col[10][10], box[10][10];
// row[i][d] = 第 i 行數字 d 已用
// box 索引：(i-1)/3*3 + (j-1)/3 + 1

2. 最少候選數優先 (MRV 启發式)

每步掃描全盤，找候選數最少的空格優先填寫。
大幅剪枝，避免無效搜索。

3. 遞迴 + 回溯

void dfs(int left) {
    if (left == 0) { print_solution(); return; }
    // 找候選最少的空格
    int bx, by, min_cand = 10;
    for (i=1..9) for (j=1..9) if (!a[i][j]) {
        int cnt = 0;
        for (d=1..9) if (!row[i][d] && !col[j][d] && !box[box_id(i,j)][d]) cnt++;
        if (cnt < min_cand) { min_cand = cnt; bx=i; by=j; }
    }
    // 嘗試候選
    for (d=1..9) if (可填) {
        填入; 更新標記; dfs(left-1); 回溯;
    }
}

完整程式碼

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

int a[10][10];
bool row[10][10], col[10][10], box[10][10];
int box_id[10][10] = { /* 預計算 1..9 */ };
bool solved;

void dfs(int cnt) {
    if (solved) return;
    if (cnt == 0) {
        solved = true;
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) printf("%d", a[i][j]);
            puts("");
        }
        return;
    }
    int bx = -1, by = -1, min_c = 10;
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 9; j++)
            if (!a[i][j]) {
                int c = 0;
                for (int d = 1; d <= 9; d++)
                    if (!row[i][d] && !col[j][d] && !box[box_id[i][j]][d]) c++;
                if (c < min_c) { min_c = c; bx = i; by = j; }
            }
    for (int d = 1; d <= 9; d++) {
        int bid = box_id[bx][by];
        if (!row[bx][d] && !col[by][d] && !box[bid][d]) {
            a[bx][by] = d;
            row[bx][d] = col[by][d] = box[bid][d] = true;
            dfs(cnt - 1);
            a[bx][by] = 0;
            row[bx][d] = col[by][d] = box[bid][d] = false;
        }
    }
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        memset(row, 0, sizeof row);
        memset(col, 0, sizeof col);
        memset(box, 0, sizeof box);
        solved = false;
        int empty = 0;
        for (int i = 1; i <= 9; i++)
            for (int j = 1; j <= 9; j++) {
                char ch; scanf(" %c", &ch);
                a[i][j] = ch - '0';
                if (a[i][j]) {
                    row[i][a[i][j]] = col[j][a[i][j]] = box[box_id[i][j]][a[i][j]] = true;
                } else empty++;
            }
        dfs(empty);
    }
    return 0;
}