题目描述#

给定一个 9 x 9 的数独棋盘，请判断当前已经填入的数字是否合法。

这里只需要验证已经出现的数字是否满足数独规则：

• 每一行中，数字 1-9 不能重复出现
• 每一列中，数字 1-9 不能重复出现
• 每一个 3 x 3 宫内，数字 1-9 不能重复出现

空白位置用 '.' 表示。需要注意的是，一个当前合法的棋盘不一定最终可解，这题也不要求把数独解出来，只判断当前状态是否合法。

思路#

这题的关键不是“求解数独”，而是“检查是否出现重复”。因此只要在遍历棋盘时，同时记录每一行、每一列、每一个 3 x 3 宫里哪些数字已经出现过即可。

代码里用了三个布尔数组：

• rowHas[i][x] 表示第 i 行是否已经出现数字 x
• colHas[j][x] 表示第 j 列是否已经出现数字 x
• subBoxHas[i/3][j/3][x] 表示第 (i/3, j/3) 个宫是否已经出现数字 x

遍历棋盘时，如果当前位置是 '.'，直接跳过；如果是数字字符，就把它转成 0-8 的下标。然后检查这三个位置是否已经被标记过：

• 如果某一行里已经出现过这个数字，说明当前行重复
• 如果某一列里已经出现过这个数字，说明当前列重复
• 如果某一个宫里已经出现过这个数字，说明当前宫重复

只要有任意一种重复，马上返回 false。如果整张棋盘遍历结束都没有冲突，就返回 true。

这种写法的好处是很直接，逻辑和题目规则一一对应。时间复杂度是 O(81)，因为棋盘大小固定为 9 x 9；额外空间复杂度也是常数级。

代码#

func isValidSudoku(board [][]byte) bool {
	rowHas := [9][9]bool{}       // rowHas[i][x] 表示 i 行是否有数字 x
	colHas := [9][9]bool{}       // colHas[j][x] 表示 j 列是否有数字 x
	subBoxHas := [3][3][9]bool{} // subBoxHas[i'][j'][x] 表示 (i',j') 宫是否有数字 x

	for i, row := range board {
		for j, b := range row {
			if b == '.' {
				continue
			}
			x := b - '1'                                                // 字符 '1'~'9' 转成数字 0~8
			if rowHas[i][x] || colHas[j][x] || subBoxHas[i/3][j/3][x] { // 重复遇到数字 x
				return false
			}
			// 标记行、列、宫包含数字 x
			rowHas[i][x] = true
			colHas[j][x] = true
			subBoxHas[i/3][j/3][x] = true
		}
	}

	return true
}