LeetCode 36. Valid Sudoku

Determine if a 9×9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the 9 3×3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid.

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

Example 1:

Input:
[
[“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″]
]
Output: true
Example 2:

Input:
[
[“8″,”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″]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being
modified to 8. Since there are two 8’s in the top left 3×3 sub-box, it is invalid.
Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
The given board contain only digits 1-9 and the character ‘.’.
The given board size is always 9×9.

解析：
数独游戏，具体规则如下：
每一行包含1-9个数字，并且没有重复。
每一列包含1-9个数字，并且没有重复。
9*9的方格可以划分成9个3*3的九宫格，保证每个单元格中没有重复的数字。
思路1：
可以一次检查每一行、每一列和每个九宫格是否有重复数字。每次检查过程中使用一个表示数组来记录1-9是否有重复使用。

bool isValidSudoku(vector<vector<char>>& board) {
    if(board.size()!=9 || board[0].size()!=9) 
        return false;
    
    //检查每一行
    for(int i=0; i<9; i++) {
        vector<bool> used(9,false);//标识数字是否已被使用
        for(int j=0; j<9; j++) {
            if(!isdigit(board[i][j])) 
                continue; 
            int k = board[i][j]-'0';
            if(k==0 || used[k-1]) 
                return false;
            used[k-1] = true;
        }
    }
    
    //检查每一列
    for(int j=0; j<9; j++) {
        vector<bool> used(9,false);
        for(int i=0; i<9; i++) {
            if(!isdigit(board[i][j])) 
                continue;
            int k = board[i][j]-'0';
            if(k==0 || used[k-1]) 
                return false;
            used[k-1] = true;
        }
    }
    
    // 检查每个3*3的单元格
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            int row = 3*i;
            int col = 3*j;
            vector<bool> used(9,false);
            for(int m=row; m<row+3; m++) {
                for(int n=col; n<col+3; n++) {
                    if(!isdigit(board[m][n])) 
                        continue;
                    int k = board[m][n]-'0';
                    if(k==0 || used[k-1]) 
                        return false;
                    used[k-1]=true;
                }
            }
        }
    }
    
    return true;
}

思路2：
在讨论区中看到了另外一种思路，很精巧。对9个九宫格分别按行进行编号，比如第i行，j列的元素，对应的九宫格编号为k = i / 3 * 3 + j / 3
具体代码如下：

bool isValidSudoku(vector<vector<char> > &board)
{
    int used1[9][9] = {0}, used2[9][9] = {0}, used3[9][9] = {0};
    //used1用来标记每一行是否有重复数字，used2标记每一列是否有重复数字，used3标识每一个九宫格是否有重复数字。
    
    for(int i = 0; i < board.size(); ++ i)
        for(int j = 0; j < board[i].size(); ++ j)
            if(board[i][j] != '.')
            {
                int num = board[i][j] - '0' - 1, k = i / 3 * 3 + j / 3;
                if(used1[i][num] || used2[j][num] || used3[k][num])
                    return false;
                used1[i][num] = used2[j][num] = used3[k][num] = 1;
            }
    
    return true;
}

参考：
https://leetcode.com/problems/valid-sudoku/discuss/15464/My-short-solution-by-C++.-O(n2)
http://bangbingsyb.blogspot.com/2014/11/leetcode-valid-sudoku-sudoku-solver.html