解数独 #1
Comments
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
} |
|
第一次解数独问题，基本思路就是递归， 首先找出所有空格子以及初始可能填充的数字，依次尝试。因为填充可能失败，因此递归退出时需要恢复当前状态，这就是回溯。 大家的思路差不多，但是在具体实现细节上各有差别， 这里提供一个非常简洁的思路。 首先， 我看很多人递归时是基于二维数组的递归，在每一层递归时，都要从头检查空格，实际上没有必要。假设当前检查第i行第j列的空格，尝试填充数字后，递归检查下一个空格，应该直接从第i行j+1列或者i+1行0列继续检查。这里之所以递归从头检查不会进入死循环，是因为递归时第i行j列位置的空格已经被填充，所以即使从头寻找下一个空格，也是在其后的空格，但是实际遍历二维的操作是冗余的。 那么有没有更好的办法呢？ 答案是有的， 就是我们可以将二维数组打平成一维数组进行递归。 对于9*9的二维数组，按照行优先的访问顺序，81个格子对应的索引为0~80, 假设当前索引为n，则对应的行为n/9，列为n%9，这样递归时只需n+1就可以了。 其次，在判断当前位置数字是否有效时，一般有两种思路，一种思路是看数独空格填充数字之后，是否满足要求，这时需要检查行、列以及子块，好处是不需要额外申请空间，坏处时，没有办法优化检查效率。另一种思路时，记录各行、列、子块已经使用的数字，判断当前数字是否已经被占用，好处是可以利用各种方法优化检查效率，坏处是需要额外申请空间。其实，这里还有另一个好处，不需要原二维数组记录临时结果。 再次，上面我们提到检查填充数字是否有效时的优化手段，由于每个空格只能填充1~9九个数字，显然利用位运算可以将二维数组降维成一维数组。我们可以使用三个一维数组分别记录各行、列以及子块已经使用的数字，同时利用位运算的高效进行数字判断。 这里，我们首先将已经填充的数字按照行、列以及子块的顺序进行记录。然后在尝试填充某个空格时，我们会先判断该数字是否被空格所在行、列、子块中被占用，如果没有被占用，则所在行、列以及子块登记该数字，继续填充下一个空格。如果后续填充失败，则需要在行、列以及子块中移除该数字，尝试下一个数字。 |
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例：
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解
https://leetcode-cn.com/problems/sudoku-solver/
The text was updated successfully, but these errors were encountered: