## 一.题目描述 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules：  [http://sudoku.com.au/TheRules.aspx](http://sudoku.com.au/TheRules.aspx) .  The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’. The following figure: A partially filled sudoku which is valid.  ## 二.题目分析 关于Sudoku矩阵的性质，可以简单概括为：对于矩阵中每一行、每一列以及每个`3×3`的九宫格区域是否存在唯一的`0~9`排列组合，如果存在相同的元素，则该Sudoku矩阵不合法。 这道题比较简单，就是遍历Sudoku矩阵的所有元素，检查各元素是否满足Sudoku的性质。对于判断一个元素是否在某一行，某一列或者某个小区域内，我定义了一个用于存放0~9数字出现次数的`map`，使用`'1'，'2'，...，'9'`作为关键字只要某个关键字的储存对象大于1，表示在该行、列或`3×3`的九宫格区域中有重复的某个关键字，通过这种方式进行遍历即可判断矩阵是否合法。 ## 三.示例代码 ~~~ #include <iostream> #include <vector> #include <map> using namespace std; class Solution { public: bool isValidSudoku(vector<vector<char> >& board) { map<char, int> sudokuMap; for (int i = 0; i < 9; i++) { sudokuMap.clear(); for (int j = 0; j < 9; j++) { sudokuMap[board[i][j]]++; if ((board[i][j] != '.') && (sudokuMap[board[i][j]] > 1)) return false; } } for (int i = 0; i < 9; i++) { sudokuMap.clear(); for (int j = 0; j < 9; j++) { sudokuMap[board[j][i]]++; if ((board[j][i] != '.') && (sudokuMap[board[j][i]] > 1)) return false; } } for (int i = 0; i < 9; i += 3) { for (int j = 0; j < 9; j += 3) { sudokuMap.clear(); for (int k = i; k < i + 3; k++) { for (int l = j; l < j + 3; l++) { sudokuMap[board[k][l]]++; if ((board[k][l] != '.') && (sudokuMap[board[k][l]] > 1)) return false; } } } } return true; } }; ~~~ 运行结果如下： 1.一个正确的数独矩阵：  2.一个错误的数独矩阵：  ## 四.小结 这道题不要求实现什么算法，只需设计一下矩阵运算，使用`map`用于存放每行、每列或每个九宫格中`1~9`每个数出现的次数，只要发现有大于一的，即可立即否定这个Sudoku，只有遍历整个Sudoku矩阵且符合要求，才判定为valid sudoku。 相关题目：Sudoku solver