解数独 about daily-leetcode HOT 2 OPEN

func solveSudoku(board [][]byte) {
    //统计每行/列/块已经使用的数字,按位存储
    var rows, cols, zones = make([]int, 9), make([]int, 9), make([]int, 9)
    for i := range board {
        for j := range board[i] {
            if board[i][j] != '.' {
                var bit = 1 << (board[i][j] - '0')
                rows[i] |= bit
                cols[j] |= bit
                zones[i/3*3+j/3] |= bit
            }
        }
    }
    dfs(board, 0, rows, cols, zones)
}

//将二维数组按行打平为一维数组, 按一维索引位置递归填充数字, 这里之所以打平为一维数组,避免递归时重复检查之前的元素
//n: 按行打平为一维数组时的索引位置
//rows: 遍历第n个位置时,各行已使用的数字集合
//cols: 遍历第n个位置时,各列已使用的数字集合
//zones: 遍历第n个位置时,各列已使用的数字集合
func dfs(board [][]byte, n int, rows []int, cols []int, zones []int) bool {
    //第n个位置填充完成，递归结束
    if n == len(board)*len(board) {
        return true
    }
    //定位行与列
    var i, j = n / len(board), n % len(board)
    //当前位置已填数字,直接判断下一个位置
    if board[i][j] != '.' {
        return dfs(board, n+1, rows, cols, zones)
    }
    //当前位置未填充数字,则尝试填充数字1~9
    for k := 1; k <= 9; k++ {
        var bit = 1 << k
        //判断所在行/列/块是否使用该数字
        if unused := rows[i]&bit == 0 && cols[j]&bit == 0 && zones[i/3*3+j/3]&bit == 0; unused {
            //对应行/列/块标记该数字被占用
            rows[i] |= bit
            cols[j] |= bit
            zones[i/3*3+j/3] |= bit
            //继续填充下一个位置
            if dfs(board, n+1, rows, cols, zones) {
                //这里递归返回true，表示后续位置都已经正确填充，此时可以填充当前位置
                board[i][j] = uint8(k + '0')
                return true
            } else {
                //这里递归返回false，表示后续位置填充失败，因此当前数字无效，我们需要尝试下一个数字
                //在尝试下一个数字前，我们要移除对应行/列/块所标记的当前数字
                rows[i] &= ^bit
                cols[j] &= ^bit
                zones[i/3*3+j/3] &= ^bit
            }
        }
    }
    //此处表示该位置1~9均不可填充, 数独无解
    return false
}