專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近騰訊發文稱要在全球招7000+位實習生，行業涵蓋技術研究的多個前沿領域，包括自然語言處理、計算機視覺、高性能計算以及基礎架構等方向。這些領域都是當前科技發展的熱點，也是騰訊戰略布局的重要方向。

同時，騰訊還提供了大量需求量大的崗位，如后臺開發、PC 客戶端開發、移動客戶端開發、游戲客戶端開發、產品策劃、產品運營、游戲策劃培訓生、游戲發行 / 運營培訓生等。有需要的同學趕緊去投遞吧，簡歷投遞入口>>>join.qq.com

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第37題：解數獨。

問題描述

來源：LeetCode第37題

難度：困難

編寫一個程序，通過填充空格來解決數獨問題。數獨的解法需遵循如下規則：

1，數字 1-9 在每一行只能出現一次。

2，數字 1-9 在每一列只能出現一次。

3，數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。

數獨部分空格內已填入了數字，空白格用 '.' 表示。

示例 1：

輸入：board = [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"]] 輸出：[ ["5","3","4","6","7","8","9","1","2"], ["6","7","2","1","9","5","3","4","8"], ["1","9","8","3","4","2","5","6","7"], ["8","5","9","7","6","1","4","2","3"], ["4","2","6","8","5","3","7","9","1"], ["7","1","3","9","2","4","8","5","6"], ["9","6","1","5","3","7","2","8","4"], ["2","8","7","4","1","9","6","3","5"], ["3","4","5","2","8","6","1","7","9"]] 解釋：輸入的數獨如上圖所示，唯一有效的解決方案如下所示：

提示：

1，board.length == 9

2，board[i].length == 9

3，board[i][j] 是一位數字或者 '.'

4，題目數據 保證 輸入數獨僅有一個解

問題分析

解數獨問題是一道經典的 回溯算法 問題，它和八皇后問題很類似，都可以使用回溯算法解決，不過數獨問題要比八皇后問題稍微復雜一點，因為八皇后問題只需要每行放一個皇后就可以了，而數獨問題需要每行全部放上數字。

回溯算法其實就是試探，如果不了解回溯算法的也可以看下我很久之前寫的一篇文章。

對于解數獨這道題，我們可以在每一個空的位置放入一個數字，如果所有空的位置都能正確放入數字，說明這就是數獨的一個解，如果任何一個位置放入數字發生了沖突，我們就撤銷，然后嘗試放其他數字，如果當前位置放任何一個數字都會發生沖突，說明前面放的某個數字有問題，繼續撤銷……。

如下圖所示，我們在第3個位置只能放1,2,4這三個數字，否則放任何數字都會發生沖突。其實就相當于一顆n叉樹，如果當前位置能放數字，我們就沿著這個分支往下走，如果不能放，我們就撤銷。如果所有位置都能放入數字且不發生沖突，說明放的全部數字是其中的一個解。

JAVA：

// 回溯算法
public boolean solveSudoku(char[][] board) {
    return backTrace(board, 0, 0);
}

// row表示第幾行，col表示第幾列。
private boolean backTrace(char[][] board, int row, int col) {
    // row是從0開始的，當row等于board.length的時候表示數獨的
    // 最后一行全部讀遍歷完了，說明數獨中的值是有效的，直接返回true
    if (row == board.length)
        return true;
    // 如果當前行的最后一列也遍歷完了，就從下一行的第一列開始。
    if (col == board.length)
        return backTrace(board, row + 1, 0);
    // 如果當前位置已經有數字了，就不能再填了，直接跳過
    if (board[row][col] != '.')
        return backTrace(board, row, col + 1);
    // 如果上面條件都不滿足，我們就從1到9選擇一個合適的數字填入到數獨中
    for (char i = '1'; i <= '9'; i++) {
        // 判斷當前位置[row，col]是否可以放數字i，如果不能放再判斷下
        // 一個能不能放，直到找到能放的為止，如果從1-9都不能放，就會下面
        // 直接return false
        if (!isValid(board, row, col, i))
            continue;
        // 如果能放數字i，就把數字i放進去
        board[row][col] = i;
        // 如果成功就直接返回，不需要再嘗試了
        if (backTrace(board, row, col))
            return true;
        // 否則就撤銷重新選擇
        board[row][col] = '.';
    }
    // 如果當前位置[row，col]不能放任何數字，直接返回false
    return false;
}

// 驗證當前位置[row，col]是否可以存放數字c
private boolean isValid(char[][] board, int row, int col, char c) {
    for (int i = 0; i < 9; i++) {
        // 當前列有沒有和字符c重復的
        if (board[i][col] == c)
            return false;
        // 當前行有沒有和字符c重復的
        if (board[row][i] == c)
            return false;
        // 當前的單元格內是否有和字符c重復的
        if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
            return false;
    }
    return true;
}

C++：

public:
    void solveSudoku(vector

 >& board) {      backTrace(board, 0, 0); } //row表示第幾行，col表示第幾列。 bool backTrace(vector

 >& board, int row, int col) {     //注意row是從0開始的，當row等于board.length的時候表示數獨的     //最后一行全部讀遍歷完了，說明數獨中的值是有效的，直接返回true     if (row == board.size())         return true;     //如果當前行的最后一列也遍歷完了，就從下一行的第一列開始。這里的遍歷     //順序是從第1行的第1列一直到最后一列，然后第二行的第一列一直到最后     //一列，然后第三行的……     if (col == board.size())         return backTrace(board, row + 1, 0);     //如果當前位置已經有數字了，就不能再填了，直接跳過     if (board[row][col] != '.')         return backTrace(board, row, col + 1);     //如果上面條件都不滿足，我們就從1到9選擇一個合適的數字填入到數獨中     for (char i = '1'; i <= '9'; i++) {         //判斷當前位置[row，col]是否可以放數字i，如果不能放再判斷下         //一個能不能放，直到找到能放的為止，如果從1-9都不能放，就會下面         //直接return false         if (!isValid(board, row, col, i))             continue;         //如果能放數字i，就把數字i放進去         board[row][col] = i;         //如果成功就直接返回，不需要再嘗試了         if (backTrace(board, row, col))             return true;         //否則就撤銷重新選擇         board[row][col] = '.';     }     //如果當前位置[row，col]不能放任何數字，直接返回false     return false; } // 驗證當前位置[row，col]是否可以存放字符c bool isValid(vector

 >& board, int row, int col, char c) {     for (int i = 0; i < 9; i++) {         //當前列有沒有和字符c重復的         if (board[i][col] == c)             return false;         //當前行有沒有和字符c重復的         if (board[row][i] == c)             return false;         //當前的單元格內是否有和字符c重復的         if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)             return false;     }     return true; }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。