Valid Sudoku

标签： C++ 算法 LeetCode

每日算法——leetcode系列

问题 Valid Sudoku

Difficulty: Easy

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

<small> A partially filled sudoku which is valid.</small>
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        
    }
};

翻译

数独有效性验证

难度系数：容易

根据Sudoku Puzzles - The Rules规则来判定数独的有效性。
数独板可以被部分填充，空格部分用'.'来填充。

注意
不一定要这个数独是有解，只要当前已经填充的数字是合法的就可以。

思路

玩游戏先弄懂规则最重要。数独好像国处很受欢迎，但我还没见过人玩。

由于只要当前已经填充的数字是合法的就可以，因此只需要判断9*9网格的每一行、每一列、9个小九宫格是否合法。如果在每一行、每一列、每个9个小九宫格内有重复数字则不合法。

三个循环，各判断行、列、小九宫格是否合法，为了节省时间，可以用bitmap来代表这个数字是否出现，bitmap可以用数组，只有0到9的数字为index，false和true为值，出现过值为true， 关于vector里面装bool类型，在<<Effective STL>> 这本书里有说明，最好不要在vector装bool类型。
由于有规律，三个在不同循环判断的可以写在一个里面。

代码

class Solution {
public:
    bool isValidSudoku(vector<vector<char> > &board) {
        const int cnt = 9;
        bool rowMap[cnt][cnt] = {false};
        bool colMap[cnt][cnt] = {false};
        bool smallBoardMask[cnt][cnt] = {false};
        
        for(int i = 0; i < board.size(); ++i){
            for (int j = 0; j < board[i].size(); ++j){
                if (board[i][j] == '.'){
                    continue;
                }
                int idx =  board[i][j] - '0' - 1;
                
                // 行
                if (rowMap[i][idx] == true){
                    return false;
                }
                rowMap[i][idx] = true;
                
                // 列
                if (colMap[j][idx] == true) {
                    return false;
                }
                colMap[j][idx] = true;
                
                // 小区域
                int area = (i/3) * 3 + (j/3);
                if (smallBoardMask[area][idx] == true) {
                    return false;
                }
                smallBoardMask[area][idx] = true;
            }
        }
        
        return true;
    }
};