LeetCode 37: Sudoku Solver

Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character

'.'

.

You may assume that there will be only one unique solution.

A sudoku puzzle, and its solution numbers marked in red.

解題思路

采用回溯法（Backtracking）求解，代碼如下：

class Solution {
private:
    // 檢測第 x 行，第 y 列是否有效
    bool isValidSudoku(vector<vector<char>>& board, int row, int col) {
        // 行
        for(int j = ; j < ; j++)  
            if(j != col && board[row][j] == board[row][col])  
                return false;  
        // 列
        for(int i = ; i < ; i++)  
            if(i != row && board[i][col] == board[row][col])  
                return false;  
        // 九宮格
        int gridRow = row/*, gridCol = col/*;  
        for(int i = ; i < ; i++)  
            for(int j = ; j < ; j++)      
                if(gridRow + i != row && gridCol + j != col && 
                    board[gridRow + i][gridCol + j] == board[row][col])  
                    return false;  

        return true;
    }

    bool internalSolver(vector<vector<char>>& board) {
        for (int i = ; i < ; ++i) {
            for (int j = ; j < ; ++j) {
                if (board[i][j] == '.') {
                    // 若board[i][j] == '.'，則嘗試填入數字1-9
                    for (int k = ; k < ; ++k) {
                        board[i][j] = '1' + k;

                        // 目前填入的數字有效，遞歸解決餘下部分
                        if (isValidSudoku(board, i, j)) {
                            if (internalSolver(board)) {
                                // 餘下部分成功解決，則board已填充完全
                                return true;
                            }
                        }
                    }

                    //該空格無論設定什麼數字都無法達到合法狀态，回溯
                    board[i][j] = '.';
                    return false;
                }
            }
        }
        return true;
    }

public:
    void solveSudoku(vector<vector<char>>& board) {
        internalSolver(board);
    }
};
           

這裡提供了一個JavaScript實作的 Sudoku puzzle solver 和一些相關連結。