0036. 有效的数独 [Medium] [Valid Sudoku].md

36 Valid Sudoku

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

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the 9 3x3 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 3x3 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 9x9.

---

题目：判断给定的二维数组是否为有效的数独。该数独不一定有解，只需判断是否满足数独的规则：每行不能有重复的数字，每列不能有重复的数字，每个九宫格不能有重复的数字。

思路: 创建三个unordered_map<int, unordered_set<char>>，将数据重新规整化存入其中，判断是否有重复的元素。其中行，列的序号可由i和j控制，九宫格的序号可通过(i/3)*3+j/3计算得到。可参考具体分析。

工程代码下载

#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<algorithm>
using namespace std;

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int r = board.size();
        int c = board[0].size();

        //将数据重新存放在不同的map中，三个map的key分别表示行序号，列序号，九宫格序号。
        unordered_map<int, unordered_set<char> > rows;
        unordered_map<int, unordered_set<char> > cols;
        unordered_map<int, unordered_set<char> > grids;

        for(int i=0; i< r; i++){
            for(int j=0; j< c; j++){
                if(board[i][j] == '.')
                    continue;

                auto iter = rows[i].find(board[i][j]);
                if(iter != rows[i].end())
                    return false;
                else
                    rows[i].insert(board[i][j]);

                iter = cols[j].find(board[i][j]);
                if(iter != cols[j].end())
                    return false;
                else
                    cols[j].insert(board[i][j]);

                iter = grids[(i/3)*3+j/3].find(board[i][j]);
                if(iter != grids[(i/3)*3+j/3].end())
                    return false;
                else
                    grids[(i/3)*3+j/3].insert(board[i][j]);
            }
        }
        return true;
    }
};

int main(int argc, char const *argv[])
{
    Solution sln;
    vector<vector<char>> testcase{  
        {'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'}
    };
    cout << sln.isValidSudoku(testcase) << endl;
    return 0;
}