菜鸡每日一题系列打卡37天
每天一道算法题目
小伙伴们一起留言打卡
坚持就是胜利，我们一起努力！
题目描述(引自LeetCode)
编写一个程序，通过已填充的空格来解决数独问题。一个数独的解法需遵循如下规则：
-
数字1-9在每一行只能出现一次。
-
数字1-9在每一列只能出现一次。
-
数字1-9在每一个以粗实线分隔的3×3宫内只能出现一次。
空白格用'.'表示。
一个数独
答案被标成红色
说明：
-
给定的数独序列只包含数字1-9和字符'.'。
-
你可以假设给定的数独只有唯一解。
-
给定数独永远是9×9形式的。
题目分析
本题是一道二维数组的题目，与上一道题目不同的是，这道题目是求解数独。有经验的小伙伴会第一时间想到回溯法。数独求解问题，同经典的八皇后问题、迷宫问题一样，都是回溯法的典型应用场景。所谓回溯法，说白了其实就是一种试探，通过试探的方式达到剪枝求解的目的。回溯法的流程就是按照某一顺序进行试探，在可行的时候继续向下试探，在不可行的时候返回试探前的状态。这其实交代了回溯法所必须的一些要素，起始位置，结束位置，状态存储，可行性判断及处理等。接下来，就在求解数独的过程中感受一下回溯法的魅力吧。
代码实现
class Solution {// 存储当前行、列、宫的状态private boolean[][] rows = new boolean[9][10];private boolean[][] columns = new boolean[9][10];private boolean[][] boxes = new boolean[9][10];public void solveSudoku(char[][] board) {// 根据输入的board数组初始化行、列、宫的状态for (int row = 0; row < 9; row++)for (int column = 0; column < 9; column++)if (board[row][column] != '.') {int num = board[row][column] - '0';rows[row][num] = true;columns[column][num] = true;boxes[(row / 3) * 3 + column / 3][num] = true;}// 从board数组的左上角开始回溯backTrace(board, 0, 0);}private boolean backTrace(char[][] board, int row, int column) {// 回溯至右下角则返回结果if (row == 9) return true;// 若当前位置有数字，则移动到下一个位置if (board[row][column] != '.') return backTrace(board, column == 8 ? row + 1 : row, column == 8 ? 0 : column + 1);else {// 当前宫的索引int index = (row / 3) * 3 + column / 3;for (int i = 1; i < 10; i++) {// 当前情况下符合条件if (!rows[row][i] && !columns[column][i] && !boxes[index][i]) {rows[row][i] = true;columns[column][i] = true;boxes[index][i] = true;board[row][column] = (char)(i + '0');// 后续情况符合条件if (backTrace(board, column == 8 ? row + 1 : row, column == 8 ? 0 : column + 1)) return true;// 否则状态回溯至本次操作之前rows[row][i] = false;columns[column][i] = false;boxes[index][i] = false;board[row][column] = '.';}}}// 回溯结束，未找到结果return false;}
}
代码分析
对代码进行分析，由于题目给出的是9×9的数独，因此，每行需要填写的数字不超过9个。在仅仅考虑行约束的情况下可以计算得最多有(9!)^9种情况，因此可以粗略估计出其时间复杂度，而就空间而言，在数独大小固定的情况下，所使用的额外空间也是固定的。
执行结果
学习 | 工作 | 分享
????长按关注“有理想的菜鸡”
只有你想不到，没有你学不到