LeetCode 筆記：解數獨

題目描述

編寫程式解數獨謎題，空格以 '.' 表示。輸入保證有且僅有一個解。

題目分析

經典回溯算法。對每個空格嘗試填入 1~9，檢查該數在所在行、列、3x3 宮內是否合法。合法則遞歸處理下一空格；不合法則回溯重置為 '.' 試下一數。只需檢查當前填入數影響的行、列、宮，無需驗證整個棋盤。遞歸終止條件：所有格子填滿（到達右下角）。

核心代碼 (C++)

class Solution {
public:
    bool isValidSudoku(vector>& board, int x, int y) {
        // 檢查行
        for (int row = 0; row < 9; ++row)
            if (row != x && board[row][y] == board[x][y]) return false;
        // 檢查列
        for (int col = 0; col < 9; ++col)
            if (col != y && board[x][col] == board[x][y]) return false;
        // 檢查 3x3 宮
        for (int row = (x/3)*3; row < (x/3+1)*3; ++row)
            for (int col = (y/3)*3; col < (y/3+1)*3; ++col)
                if (row != x && col != y && board[row][col] == board[x][y]) return false;
        return true;
    }

    bool internalSolveSudoku(vector>& board) {
        for (int row = 0; row < 9; ++row) {
            for (int col = 0; col < 9; ++col) {
                if (board[row][col] == '.') {
                    for (int i = 1; i <= 9; ++i) {
                        board[row][col] = '0' + i;
                        if (isValidSudoku(board, row, col) && internalSolveSudoku(board))
                            return true;
                        board[row][col] = '.'; // 回溯
                    }
                    return false; // 1~9 都不行
                }
            }
        }
        return true; // 全滿
    }

    void solveSudoku(vector>& board) {
        internalSolveSudoku(board);
    }
};

小結

利用輸入保證有唯一解的條件，大幅剪枝：每步只驗證局部合法性。回溯法雖指數級最壞情況，但數獨規模固定 (9x9)，實際極快。理解回溯的「試探-驗證-遞歸-回退」模板是關鍵。