题目：
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
示例 1：
输入：
board = [
["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"],
]输出：
[
["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"],
]解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 ‘.’
题目数据 保证 输入数独仅有一个解
解题：
每个行，列，宫里面1-9只出现一次
代码：
func copyMap(elements map[byte]int) map[byte]int {
tmp := make(map[byte]int, len(elements))
for k, v := range elements {
tmp[k] = v
}
return tmp
}
func getAMapValue(elements map[byte]int) byte {
for k := range elements {
return k
}
return '.'
}
func solveMethod(board [][]byte) [][]byte {
elements := map[byte]int{'1': 1, '2': 1, '3': 1, '4': 1, '5': 1, '6': 1, '7': 1, '8': 1, '9': 1}
var result [9][9]map[byte]int
// 行
for key, line := range board {
tmp := copyMap(elements)
for _, v := range line {
if v != '.' {
if _, ok := tmp[v]; ok {
delete(tmp, v)
}
}
}
for k := range line {
result[key][k] = copyMap(tmp)
}
}
// 列
for i := 0; i < 9; i++ {
tmp := copyMap(elements)
for _, line := range board {
if line[i] != '.' {
if _, ok := tmp[line[i]]; ok {
delete(tmp, line[i])
}
}
}
for key := range board {
for k := range result[key][i] {
if _, ok := tmp[k]; !ok {
delete(result[key][i], k)
}
}
if board[key][i] == '.' && len(result[key][i]) == 1 {
board[key][i] = getAMapValue(result[key][i])
}
}
}
// 宫
for i := 0; i < 3; i++ {
for j := 0; j < 3; j++ {
tmp := copyMap(elements)
for m := i * 3; m < i*3+3; m++ {
for n := j * 3; n < j*3+3; n++ {
if board[m][n] != '.' {
if _, ok := tmp[board[m][n]]; ok {
delete(tmp, board[m][n])
}
}
}
}
for m := i * 3; m < i*3+3; m++ {
for n := j * 3; n < j*3+3; n++ {
for k := range result[m][n] {
if _, ok := tmp[k]; !ok {
delete(result[m][n], k)
}
}
if board[m][n] == '.' && len(result[m][n]) == 1 {
board[m][n] = getAMapValue(result[m][n])
}
}
}
}
}
for _, value := range board {
for _, v := range value {
if v == '.' {
board = solveMethod(board)
}
}
}
return board
}
func solveSudoku(board [][]byte) {
solveMethod(board)
}吭哧吭哧写了两天，结果还超时了。。
官方解答：
1.回溯
func solveSudoku(board [][]byte) {
var line, column [9][9]bool
var block [3][3][9]bool
var spaces [][2]int
for 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] = true
block[i/3][j/3][digit] = true
}
}
}
var dfs func(int) bool
dfs = func(pos int) bool {
if pos == len(spaces) {
return true
}
i, j := spaces[pos][0], spaces[pos][1]
for digit := byte(0); digit < 9; digit++ {
if !line[i][digit] && !column[j][digit] && !block[i/3][j/3][digit] {
line[i][digit] = true
column[j][digit] = true
block[i/3][j/3][digit] = true
board[i][j] = digit + '1'
if dfs(pos + 1) {
return true
}
line[i][digit] = false
column[j][digit] = false
block[i/3][j/3][digit] = false
}
}
return false
}
dfs(0)
}2.位运算
func solveSudoku(board [][]byte) {
var line, column [9]int
var block [3][3]int
var spaces [][2]int
flip := func(i, j int, digit byte) {
line[i] ^= 1 << digit
column[j] ^= 1 << digit
block[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) bool
dfs = 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 个 1
for ; mask > 0; mask &= mask - 1 { // 最右侧的 1 置为 0
digit := 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)
}3.枚举优化
func solveSudoku(board [][]byte) {
var line, column [9]int
var block [3][3]int
var spaces [][2]int
flip := func(i, j int, digit byte) {
line[i] ^= 1 << digit
column[j] ^= 1 << digit
block[i/3][j/3] ^= 1 << digit
}
for i, row := range board {
for j, b := range row {
if b != '.' {
digit := b - '1'
flip(i, j, digit)
}
}
}
for {
modified := false
for i, row := range board {
for j, b := range row {
if b != '.' {
continue
}
mask := 0x1ff &^ uint(line[i]|column[j]|block[i/3][j/3])
if mask&(mask-1) == 0 { // mask 的二进制表示仅有一个 1
digit := byte(bits.TrailingZeros(mask))
flip(i, j, digit)
board[i][j] = digit + '1'
modified = true
}
}
}
if !modified {
break
}
}
for i, row := range board {
for j, b := range row {
if b == '.' {
spaces = append(spaces, [2]int{i, j})
}
}
}
var dfs func(int) bool
dfs = 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 个 1
for ; mask > 0; mask &= mask - 1 { // 最右侧的 1 置为 0
digit := 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)
}学习了