题目内容

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法遵循如下规则：

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

本题满足以下设定：

• 给定的数独序列只包含数字 1-9 和字符 '.' 。
• 你可以假设给定的数独只有唯一解。
• 给定数独永远是 9x9 形式的。

样例

源数据

结果

//递归func solveSudoku(board [][]byte) {var line, column [9][9]boolvar block [3][3][9]boolvar spaces [][2]intfor i, row := range board {//按行遍历for j, b := range row {if b == '.' {//保存对应行，列的空格spaces = append(spaces, [2]int{i, j})} else {digit := b - '1'//列line[i][digit] = true//行column[j][digit] = trueblock[i/3][j/3][digit] = true}}}//对空格进行填值var dfs func(int) booldfs = func(pos int) bool {if pos == len(spaces) {return true}i, j := spaces[pos][0], spaces[pos][1]//遍历数字0~9进行填值for digit := byte(0); digit < 9; digit++ {//判断填该数字是否犯规if !line[i][digit] && !column[j][digit] && !block[i/3][j/3][digit] {//表示该数字可以填line[i][digit] = truecolumn[j][digit] = trueblock[i/3][j/3][digit] = trueboard[i][j] = digit + '1'//这里会一直向下递归，递归到最后一个空格再开始返回if dfs(pos + 1) {return true}line[i][digit] = falsecolumn[j][digit] = falseblock[i/3][j/3][digit] = false}}return false}//填第几个空格，空格有对应下标放在数组里//要对每个空格进行填值dfs(0)
}//位运算优化
func solveSudoku(board [][]byte) {var line, column [9]intvar block [3][3]intvar spaces [][2]intflip := func(i, j int, digit byte) {line[i] ^= 1 << digitcolumn[j] ^= 1 << digitblock[i/3][j/3] ^= 1 << digit}for i, row := range board {for j, b := range row {if b == '.' {spaces = append(spaces, [2]int{i, j})} else {digit := b - '1'flip(i, j, digit)}}}var dfs func(int) booldfs = func(pos int) bool {if pos == len(spaces) {return true}i, j := spaces[pos][0], spaces[pos][1]mask := 0x1ff &^ uint(line[i]|column[j]|block[i/3][j/3]) // 0x1ff 即二进制的 9 个 1for ; mask > 0; mask &= mask - 1 { // 最右侧的 1 置为 0digit := byte(bits.TrailingZeros(mask))flip(i, j, digit)board[i][j] = digit + '1'if dfs(pos + 1) {return true}flip(i, j, digit)}return false}dfs(0)
}