本文共 2982 字，大约阅读时间需要 9 分钟。

===问：

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

1. 数字1-9在每一行只能出现一次。
2. 数字1-9在每一列只能出现一次。
3. 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
   
   上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用'.'表示。

示例 1:

输入:[  ["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"]]输出: true

示例 2:

输入:[  ["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"]]输出: false解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 给定数独序列只包含数字 1-9 和字符 ‘.’ 。
• 给定数独永远是 9x9 形式的。

===答：

方法一：执行0ms-100.00%，内存4.2mb-6.25%

func isValidSudoku1(board []byte) bool {
   	for i := 0; i < 9; i++ {
   		c := make(map[byte]int, 9)		for j := 0; j < 9; j++ {
   			t := board[i][j]			if t != '.' {
   				if _, ok := c[t]; ok {
   					return false				} else {
   					c[t] = 1				}			}		}		b := make(map[byte]int, 9)		for j := 8; j >= 0; j-- {
   			t := board[j][i]			if t != '.' {
   				if _, ok := b[t]; ok {
   					return false				} else {
   					b[t] = 1				}			}		}		if i < 3 {
   			for x := 0; x < 3; x++ {
   				d := make(map[byte]int, 9)				for m := i * 3; m < i*3+3; m++ {
   					for n := x * 3; n < x*3+3; n++ {
   						t := board[m][n]						if t != '.' {
   							if _, ok := d[t]; ok {
   								return false							} else {
   								d[t] = 1							}						}						//fmt.Println(m, n)					}				}				//fmt.Println(d)			}		}	}	return true}

方法二：执行8ms-16.15%|0ms-100.00%，内存4.3mb-6.25%

func isValidSudoku2(board [][]byte) bool {
   	for i := 0; i < 9; i++ {
   		arr1 := make(map[byte]int, 9)		arr2 := make(map[byte]int, 9)		arr3 := make(map[byte]int, 9)		for j := 0; j < 9; j++ {
   			temp1 := board[i][j]			if temp1 != '.' {
   				if _, ok := arr1[temp1]; ok {
   					return false				} else {
   					arr1[temp1] = 1				}			}			temp2 := board[j][i]			if temp2 != '.' {
   				if _, ok := arr2[temp2]; ok {
   					return false				} else {
   					arr2[temp2] = 1				}			}			//思路一样，但是要利用一次j的0~8的循环完成3*3的比较，较少开支，结果有波动			x := 3*(i/3) + j/3			y := 3*(i%3) + j%3			temp3 := board[x][y]			if temp3 != '.' {
   				if _, ok := arr3[temp3]; ok {
   					return false				} else {
   					arr3[temp3] = 1				}			}		}	}	return true}

===解：

1. 就是纵坐标循环、横坐标循环，每次循环包含三个部分：横向遍历检测，纵向遍历检测，33遍历检测，其中33的遍历要利用横坐标的循环（9次）来实现纵坐标3次，横坐标3次。
2. 二种方法的结果比较波动，有的时候执行效率100%，有的时候执行效率16.15%，但内存消耗比较一致，方法一比方法二稍微少点。

转载地址：http://ftkpi.baihongyu.com/