[LeetCode] 37. Sudoku Solver 求解數(shù)獨(dú)

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 '.'.

A sudoku puzzle...

...and its solution numbers marked in red.

Note:

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

這道求解數(shù)獨(dú)的題是在之前那道 Valid Sudoku 的基礎(chǔ)上的延伸，之前那道題讓我們驗(yàn)證給定的數(shù)組是否為數(shù)獨(dú)數(shù)組，這道讓求解數(shù)獨(dú)數(shù)組，跟此題類似的有 Permutations，Combinations， N-Queens 等等，其中尤其是跟 N-Queens 的解題思路及其相似，對(duì)于每個(gè)需要填數(shù)字的格子帶入1到9，每代入一個(gè)數(shù)字都判定其是否合法，如果合法就繼續(xù)下一次遞歸，結(jié)束時(shí)把數(shù)字設(shè)回 '.'，判斷新加入的數(shù)字是否合法時(shí)，只需要判定當(dāng)前數(shù)字是否合法，不需要判定這個(gè)數(shù)組是否為數(shù)獨(dú)數(shù)組，因?yàn)橹凹舆M(jìn)的數(shù)字都是合法的，這樣可以使程序更加高效一些，整體思路是這樣的，但是實(shí)現(xiàn)起來(lái)可以有不同的形式。一種實(shí)現(xiàn)形式是遞歸帶上橫縱坐標(biāo)，由于是一行一行的填數(shù)字，且是從0行開(kāi)始的，所以當(dāng)i到達(dá)9的時(shí)候，說(shuō)明所有的數(shù)字都成功的填入了，直接返回 ture。當(dāng)j大于等于9時(shí)，當(dāng)前行填完了，需要換到下一行繼續(xù)填，則繼續(xù)調(diào)用遞歸函數(shù)，橫坐標(biāo)帶入 i+1。否則看若當(dāng)前數(shù)字不為點(diǎn)，說(shuō)明當(dāng)前位置不需要填數(shù)字，則對(duì)右邊的位置調(diào)用遞歸。若當(dāng)前位置需要填數(shù)字，則應(yīng)該嘗試填入1到9內(nèi)的所有數(shù)字，讓c從1遍歷到9，每當(dāng)試著填入一個(gè)數(shù)字，都需要檢驗(yàn)是否有沖突，使用另一個(gè)子函數(shù) isValid 來(lái)檢驗(yàn)是否合法，假如不合法，則跳過(guò)當(dāng)前數(shù)字。若合法，則將當(dāng)前位置賦值為這個(gè)數(shù)字，并對(duì)右邊位置調(diào)用遞歸，若遞歸函數(shù)返回 true，則說(shuō)明可以成功填充，直接返回 true。不行的話，需要重置狀態(tài)，將當(dāng)前位置恢復(fù)為點(diǎn)。若所有數(shù)字都嘗試了，還是不行，則最終返回 false。檢測(cè)當(dāng)前數(shù)組是否合法的原理跟之前那道 Valid Sudoku 非常的相似，但更簡(jiǎn)單一些，因?yàn)檫@里只需要檢測(cè)新加入的這個(gè)數(shù)字是否會(huì)跟其他位置引起沖突，分別檢測(cè)新加入數(shù)字的行列和所在的小區(qū)間內(nèi)是否有重復(fù)的數(shù)字即可，參見(jiàn)代碼如下：

解法一：

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        helper(board, 0, 0);
    }
    bool helper(vector<vector<char>>& board, int i, int j) {
        if (i == 9) return true;
        if (j >= 9) return helper(board, i + 1, 0);
        if (board[i][j] != '.') return helper(board, i, j + 1);
        for (char c = '1'; c <= '9'; ++c) {
            if (!isValid(board, i , j, c)) continue;
            board[i][j] = c;
            if (helper(board, i, j + 1)) return true;
            board[i][j] = '.';
        }
        return false;
    }
    bool isValid(vector<vector<char>>& board, int i, int j, char val) {
        for (int x = 0; x < 9; ++x) {
            if (board[x][j] == val) return false;
        }
        for (int y = 0; y < 9; ++y) {
            if (board[i][y] == val) return false;
        }
        int row = i - i % 3, col = j - j % 3;
        for (int x = 0; x < 3; ++x) {
            for (int y = 0; y < 3; ++y) {
                if (board[x + row][y + col] == val) return false;
            }
        }
        return true;
    }
};

還有另一種遞歸的寫法，這里就不帶橫縱坐標(biāo)參數(shù)進(jìn)去，由于遞歸需要有 boolean 型的返回值，所以不能使用原函數(shù)。因?yàn)闆](méi)有橫縱坐標(biāo)，所以每次遍歷都需要從開(kāi)頭0的位置開(kāi)始，這樣無(wú)形中就有了大量的重復(fù)檢測(cè)，導(dǎo)致這種解法雖然寫法簡(jiǎn)潔一些，但擊敗率是沒(méi)有上面的解法高的。這里的檢測(cè)數(shù)組沖突的子函數(shù)寫法也比上面簡(jiǎn)潔不少，只用了一個(gè) for 循環(huán)，用來(lái)同時(shí)檢測(cè)行列和小區(qū)間是否有沖突，注意正確的坐標(biāo)轉(zhuǎn)換即可，參見(jiàn)代碼如下：

解法二：

class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        helper(board);
    }
    bool helper(vector<vector<char>>& board) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') continue;
                for (char c = '1'; c <= '9'; ++c) {
                    if (!isValid(board, i, j, c)) continue;
                    board[i][j] = c;
                    if (helper(board)) return true;
                    board[i][j] = '.';
                }
                return false;
            }
        }
        return true;
    }
    bool isValid(vector<vector<char>>& board, int i, int j, char val) {
        for (int k = 0; k < 9; ++k) {
            if (board[k][j] != '.' && board[k][j] == val) return false;
            if (board[i][k] != '.' && board[i][k] == val) return false;
            int row = i / 3 * 3 + k / 3, col = j / 3 * 3 + k % 3;
            if (board[row][col] != '.' && board[row][col] == val) return false;
        }
        return true;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(37.求解數(shù)獨(dú))的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)求解數(shù)獨(dú)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論