• 问题描述

1. 判断一个 9x9 的数独是否有效。需要满足三个条件：

1.　　数字 1-9 在每一行只能出现一次

2.　　数字 1-9 在每一列只能出现一次

3.　　数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 

• 解决思路

1. 前两个要求比较容易好解决，对每行、列的数字都用一个映射来计数，key 为 1-9 的数字，value 为该数字出现的次数。
2. 关键是第二个要求，在 9X9 的 方格里总共有 9 个 3X3 的小方格。可以根据 i， j 坐标计算出是第几个方格，用9个映射来存储数字及其出现的次数。或者用二维信息（i，j）来代表当前元素是在哪个小方格。
   1. Java 代码如下：
      1     public boolean isValidSudoku(char[][] board) { 2         HashMap
               
                 [] rows = new HashMap[9]; 3         HashMap
                
                  [] columns = new HashMap[9]; 4         HashMap
                 
                   [] boxes = new HashMap[9]; 5         for (int i = 0; i < 9; i++) { 6             rows[i] = new HashMap
                  
                   (); 7             columns[i] = new HashMap
                   
                    (); 8             boxes[i] = new HashMap
                    
                     (); 9 }10 // validate a board11 for (int i = 0; i < 9; i++) {12 for (int j = 0; j < 9; j++) {13 char num = board[i][j];14 if (num != '.') {15 int n = (int)num;16 // 区分当前是第几个小格子，9X9的格子阵里面有 9 个3X3的小格子。17 int box_index = (i / 3 ) * 3 + j / 3;18 // 对该行，该列，该小方格进行健值对的添加。19 rows[i].put(n, rows[i].getOrDefault(n, 0) + 1);20 columns[j].put(n, columns[j].getOrDefault(n, 0) + 1);21 boxes[box_index].put(n, boxes[box_index].getOrDefault(n, 0) + 1);22 // 判重23 if (rows[i].get(n) > 1 || columns[j].get(n) > 1 || boxes[box_index].get(n) > 1)24 return false;25 }26 }27 }28 return true;29 }
                    
                   
                  
                 
                
               

      2.　　Python 代码如下：

      1 class Solution: 2     def isValidSudoku(self, board): 3         """ 4         :type board: List[List[str]] 5         :rtype: bool 6         """ 7         // 可以直接用一个集合，就可以存储所有的需要判重的健值对 8         count = set() 9         for i in range(9):10             for j in range(9):11                 if board[i][j] != '.':12                     cur = board[i][j]13                     if ((i,cur) in count) or ((cur,j) in count) or ((i//3, j//3, cur) in count):14                         print("(i,j)=(%s,%s)"%(i, j))15                         return False16                     # row17                     count.add((i, cur))18                     # column19                     count.add((cur, j))20                     # square21                     count.add((i//3,j//3,cur))22         return True