LeetCode每日一题,37. Sudoku Solver
先看题目描述
大意就是实现一个程序,可以解数独题,解必须满足三个要求:1. 数字 1-9 在每一行只可以出现一次; 2. 数字 1-9 在每一列只可以出现一次; 3. 数字 1-9 在以实线分割的 3*3 方格里只可以出现一次
算法和思路
回溯
使用回溯模拟人的思考方式来解决问题
- 使用三个布尔数组 rowUsed, colUsed, boxUsed 来记录行列和方格中数字的使用情况,true 表示使用过,false 表示没使用过,例如 rowUsed[0][5] = true,表示第 0 行中,数字 5 已经使用过了;boxUsed[1][0][8] = true,表示第 1 行的第 0 个方格中,数字 8 已经使用过了
- 在填充数组前先遍历一遍,将三个布尔数组初始化,表明哪些数字已经使用过了
- 尝试去填充数组,只要行,列, 还有 3*3 的方格内 出现已经被使用过的数字,我们就不填充,否则尝试填充
- 如果填充失败,那么我们需要回溯。将原来尝试填充的地方改回来
- 递归直到数组被填充完成
算法源码
1 | class Solution { |