題目描述

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.

編寫(xiě)一個(gè)程序，通過(guò)已填充的空格來(lái)解決數(shù)獨(dú)問(wèn)題。

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

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

題解

題的解法類(lèi)似于36.Valid Sudoku；不同之處在于36題驗(yàn)證Sudoku的有效性，其中包括‘.’表示的空白，而且不需要對(duì)其進(jìn)行填充；這道題除了進(jìn)行有效性驗(yàn)證外，還需要對(duì)Sudoku進(jìn)行求解。

借助上一題的解法，先對(duì)當(dāng)前空白處進(jìn)行嘗試性填充，如果填充有效[使用36題的方法]，則繼續(xù)；如果無(wú)效，則重置為空白；不斷遞歸，直到找到解或者處于沒(méi)有解的情況[題目中表明一定存在一個(gè)解，所以最后返回時(shí)一定找到了解]。

步驟：

1. corner case：數(shù)組為空，數(shù)盤(pán)不是9x9；直接返回；
2. 使用回溯法進(jìn)行問(wèn)題求解；從左上角0,0開(kāi)始
   1. 如果當(dāng)前單元格為空，用1-9進(jìn)行逐個(gè)嘗試性填充，
   2. 然后使用isValid方法進(jìn)行有效性驗(yàn)證，確保所在行、列、3x3小方格內(nèi)沒(méi)有重復(fù)數(shù)字出現(xiàn)；如果出現(xiàn)，返回false，進(jìn)行回退，將單元格重置為空；如果沒(méi)有出現(xiàn)，進(jìn)行遞歸，繼續(xù)進(jìn)行回溯法判斷，知道找到最終解，返回。

完整代碼：

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)注公眾號(hào)，一起學(xué)習(xí)