## 一.題目描述 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