數獨約束求解器：C++ 與 Python 實現的深度對比

問題建模：約束滿足問題 (CSP)

數獨求解本質是一個 約束滿足問題 (Constraint Satisfaction Problem, CSP)。每個空格是一個變量，其定義域為 {1-9}，約束條件為：

• 行約束：同一行 9 格數字互不相同
• 列約束：同一列 9 格數字互不相同
• 宮約束：同一 3×3 宮內 9 格數字互不相同

核心算法：GAC (Generalized Arc Consistency) + 回溯搜尋

1. 初始化：計算每個空格的初始定義域（排除同行/列/宮已有數字）
2. 變量選擇：採用 MRV (Minimum Remaining Values) 策略，優先選擇定義域最小的空格
3. 值嘗試：對選定空格，遍歷其定義域中的候選數字
4. 約束傳播：將選定數字從相關空格（同行/列/宮）的定義域中移除
5. 遞歸搜尋：若傳播後無空域，遞歸求解下一空格；否則回溯恢復定義域
6. 終止條件：所有空格填滿 → 找到解

C++ 實現關鍵數據結構

const int N = 81; // 9x9 = 81 個格子
vector<int> CurDom[N];      // 每個格子的當前定義域
int Assigned[N] = {0};       // 0=未填, >0=已填數字
vector<vector<int>> answer; // 解路徑：{row, col, val}
int map[9][9];               // 數獨盤面

關鍵函數實現

// 初始化單個格子的定義域
void init_CurDom(int idx) {
    int r = idx / 9, c = idx % 9;
    bool used[10] = {false};
    // 掃描行、列、宮
    for (int i = 0; i < 9; ++i) {
        if (map[r][i]) used[map[r][i]] = true;
        if (map[i][c]) used[map[i][c]] = true;
    }
    int br = r / 3 * 3, bc = c / 3 * 3;
    for (int i = br; i < br + 3; ++i)
        for (int j = bc; j < bc + 3; ++j)
            if (map[i][j]) used[map[i][j]] = true;
    // 填充定義域
    for (int d = 1; d <= 9; ++d)
        if (!used[d]) CurDom[idx].push_back(d);
}

// MRV 選擇未賦值且定義域最小的格子
int PickAnUnassignedVariable() {
    int bestIdx = -1, minSize = 10;
    for (int i = 0; i < N; ++i)
        if (!Assigned[i] && CurDom[i].size() < minSize) {
            minSize = CurDom[i].size();
            bestIdx = i;
        }
    return bestIdx;
}

// 約束傳播：將數字 d 從相關格子定義域移除，記錄受影響格子
vector<int> ForwardCheck(int idx, int d) {
    vector<int> affected;
    int r = idx / 9, c = idx % 9;
    // 行
    for (int i = 0; i < 9; ++i) {
        int id = r * 9 + i;
        if (!Assigned[id] && remove_d(id, d)) affected.push_back(id);
    }
    // 列
    for (int i = 0; i < 9; ++i) {
        int id = i * 9 + c;
        if (!Assigned[id] && remove_d(id, d)) affected.push_back(id);
    }
    // 宮
    for (int i = r/3*3; i < r/3*3+3; ++i)
        for (int j = c/3*3; j < c/3*3+3; ++j) {
            int id = i * 9 + j;
            if (!Assigned[id] && remove_d(id, d)) affected.push_back(id);
        }
    return affected;
}

// 回溯恢復定義域
void RestoreDomains(const vector<int>& affected, int d) {
    for (int id : affected) CurDom[id].push_back(d);
}

// 主遞歸求解
bool Solve(int level) {
    if (level == 0) return true; // 所有空格填滿
    int idx = PickAnUnassignedVariable();
    if (idx == -1) return false; // 無可用格子但未填滿（理論不應發生）

    int r = idx / 9, c = idx % 9;
    for (int d : CurDom[idx]) {
        Assigned[idx] = d;
        answer.push_back({r, c, d});

        vector<int> affected = ForwardCheck(idx, d);
        bool domainWipeout = false;
        for (int id : affected)
            if (CurDom[id].empty()) { domainWipeout = true; break; }

        if (!domainWipeout && Solve(level - 1)) return true;

        // 回溯
        RestoreDomains(affected, d);
        Assigned[idx] = 0;
        answer.pop_back();
    }
    return false;
}

Python 實現：更簡潔的表達

class SudokuSolver:
    def __init__(self, board):
        self.board = [row[:] for row in board]
        self.domains = [[set(range(1,10)) for _ in range(9)] for _ in range(9)]
        self.assigned = [[0]*9 for _ in range(9)]
        self._init_domains()

    def _init_domains(self):
        for r in range(9):
            for c in range(9):
                if self.board[r][c]:
                    self.assigned[r][c] = self.board[r][c]
                    self._remove_from_peers(r, c, self.board[r][c])

    def _peers(self, r, c):
        """生成所有受約束的同伴格子"""
        for i in range(9):
            if i != c: yield r, i
            if i != r: yield i, c
        br, bc = r//3*3, c//3*3
        for i in range(br, br+3):
            for j in range(bc, bc+3):
                if i != r and j != c: yield i, j

    def _remove_from_peers(self, r, c, d):
        for pr, pc in self._peers(r, c):
            self.domains[pr][pc].discard(d)

    def _mrv_cell(self):
        min_size, best = 10, None
        for r in range(9):
            for c in range(9):
                if not self.assigned[r][c]:
                    sz = len(self.domains[r][c])
                    if sz < min_size:
                        min_size, best = sz, (r, c)
        return best

    def solve(self):
        return self._backtrack(sum(1 for r in range(9) for c in range(9) if not self.assigned[r][c]))

    def _backtrack(self, remaining):
        if remaining == 0: return True
        r, c = self._mrv_cell()
        if not r: return False
        for d in sorted(self.domains[r][c]):
            self.assigned[r][c] = d
            self.board[r][c] = d
            # 保存定義域快照用於回溯
            snapshot = [(pr, pc, self.domains[pr][pc].copy()) 
                       for pr, pc in self._peers(r, c) if d in self.domains[pr][pc]]
            for pr, pc, _ in snapshot:
                self.domains[pr][pc].discard(d)
            if all(self.domains[pr][pc] for pr, pc, _ in snapshot):
                if self._backtrack(remaining - 1): return True
            # 回溯恢復
            for pr, pc, dom in snapshot:
                self.domains[pr][pc] = dom
            self.assigned[r][c] = 0
            self.board[r][c] = 0
        return False

兩種實現的關鍵差異對比

優化方向

1. 啟發式排序：嘗試值時按 LCV (Least Constraining Value) 排序，優先選擇對其他格子影響最小的數字
2. 位掩碼優化：C++ 中用 `uint16_t` 位掩碼表示定義域，位運算極大加速約束傳播
3. 舞蹈鏈 (DLX)：將數獨建模為精確覆蓋問題，用 Algorithm X + Dancing Links 求解，理論最優
4. 並行搜尋：在搜尋樹頂層分支並行探索

位掩碼版 C++ 核心片段

using Mask = uint16_t; // 低 9 位對應數字 1-9
const Mask FULL_MASK = 0x3FE; // 0b1111111110

Mask rowMask[9] = {FULL_MASK}, colMask[9] = {FULL_MASK}, boxMask[9] = {FULL_MASK};

inline Mask getDomain(int r, int c) {
    return rowMask[r] & colMask[c] & boxMask[r/3*3 + c/3];
}

inline void place(int r, int c, int d) {
    Mask bit = 1 << d;
    rowMask[r] ^= bit; colMask[c] ^= bit; boxMask[r/3*3 + c/3] ^= bit;
}

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

總結

數獨求解器展示了約束編程的核心思想：定義域初始化 → MRV 變量排序 → 前向檢查傳播約束 → 回溯搜尋。C++ 版本通過手動內存管理和增量更新極致榨取性能；Python 版本利用高級數據結構快速實現核心邏輯。理解這兩種風格的權衡，有助於在不同工程場景選擇合適的實現策略。