題目描述

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

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

img

A sudoku puzzle...

image

...and its solution numbers marked in red.

Note:

• The given board contain only digits 1-9 and the character '.'.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always 9x9.

編寫一個程序，通過已填充的空格來解決數(shù)獨問題督笆。

一個數(shù)獨的解法需遵循如下規(guī)則：

數(shù)字 1-9 在每一行只能出現(xiàn)一次闲坎。
數(shù)字 1-9 在每一列只能出現(xiàn)一次殉农。
數(shù)字 1-9 在每一個以粗實線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次碘举。
空白格用 '.' 表示熙侍。

題解

題的解法類似于36.Valid Sudoku啸罢；不同之處在于36題驗證Sudoku的有效性忍啤，其中包括‘.’表示的空白加勤，而且不需要對其進行填充；這道題除了進行有效性驗證外同波，還需要對Sudoku進行求解鳄梅。

借助上一題的解法，先對當(dāng)前空白處進行嘗試性填充未檩，如果填充有效[使用36題的方法]戴尸，則繼續(xù)；如果無效冤狡，則重置為空白孙蒙；不斷遞歸项棠，直到找到解或者處于沒有解的情況[題目中表明一定存在一個解，所以最后返回時一定找到了解]挎峦。

步驟：

1. corner case：數(shù)組為空香追，數(shù)盤不是9x9；直接返回坦胶；
2. 使用回溯法進行問題求解透典；從左上角0,0開始
   1. 如果當(dāng)前單元格為空，用1-9進行逐個嘗試性填充顿苇，
   2. 然后使用isValid方法進行有效性驗證峭咒，確保所在行、列纪岁、3x3小方格內(nèi)沒有重復(fù)數(shù)字出現(xiàn)凑队；如果出現(xiàn)，返回false幔翰，進行回退漩氨，將單元格重置為空；如果沒有出現(xiàn)导匣，進行遞歸，繼續(xù)進行回溯法判斷茸时，知道找到最終解贡定，返回。

完整代碼：

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        if (board.empty() || board.size() != 9 || board[0].size() != 9)
            return;
        
        dfs(board, 0, 0);
        
    }
    bool isValid(vector<vector<char>>& board, int i, int j){
        for (int t=0; t< 9; t++){
            if (t != j && board[i][t] == board[i][j]) return false;
            if (t != i && board[t][j] == board[i][j]) return false;
        }
        int row = i / 3 * 3, col = j / 3 * 3;
        for (int m=row; m< row+3; m++){
            for (int n=col; n< col+3; n++){
                if (m!=i && n!=j && board[m][n] == board[i][j])
                    return false;
            }
        }
        return true;
    }
    bool dfs(vector<vector<char>>& board, int i, int j){
        if (i >= 9) return true;
        if (j >= 9) return dfs(board, i+1, 0);
        
        if (board[i][j] == '.'){
            for (char t='1'; t<= '9'; t++){
                board[i][j] = t;
                if (isValid(board, i, j)){
                    if (dfs(board, i, j+1)) return true;
                }
                board[i][j] = '.';
            }
        }
        else
            return dfs(board, i, j+1);
        
        return false;
    }
};

歡迎關(guān)注公眾號可都，一起學(xué)習(xí)