问题描述:
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'
.
You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.
原问题链接:https://leetcode.com/problems/sudoku-solver/
问题分析
这个问题粗看起来很难,和前面那个判断是否为合法的数独矩阵不一样,这里要模拟求这个结果。但是凭直觉也能找到一些思路。对于数独矩阵来说,它里面那些为'.'的空格正是我们需要考虑的地方。所以一种最简单直接的办法就是往这些地方一个个的尝试填数字1到9,然后判断我们的赋值是否和其他的值冲突,如果不冲突则再看下一个,直到矩阵的最后。
在这个大的方向上我们再深入一点看。假设我们在前面的某个点(i, j)的时候赋的值是合法的,但是在它后面的空位置尝试所有的情况都失败了。这个时候我们应该继续尝试这个点后面的赋值,看有没有其他的可能。这么一通描述下来,相信大家找到一个熟悉的概念了。深度优先遍历。这个在很多树、图的遍历,在一些迷宫问题得到大量应用的地方,在这里可以考虑使用一下。
既然是采用深度优先遍历的思路,我们这里再细化一下。针对这个问题,肯定就是走递归的思路。假设定义方法dfs()。我们这里可以定义两个坐标点i, j作为递归的参数。最开始i = 0, j = 0。最终返回的情况是i >= 9, j >= 9。详细的递归关系如下。对于某个点(i, j),我们按照一行一行从左到右的方式递归。所以当i >= 9的时候我们就直接返回了。表示已经到了矩阵的最后面。如果我们碰到的这个点board[i][j]不是'.',这表示这个点是原来就有的值,我们不需要考虑,直接跳过去。所以应该返回dfs(i, j + 1)。另外,当 j >= 9的时候,说明这一行已经走完了,要调整到下一行,所以应该设置为i++; j = 0。这部分的描述用代码表示则如下:
private boolean dfs(char[][] board, int i, int j) { if(j >= 9) { j = 0; i++; } if(i >= 9) return true; if(board[i][j] != '.') return dfs(board, i, j + 1); }
上面的这些是针对那些已经存在的点或者各种边界条件的考虑。现在的重点是对于这些不存在的点呢?因为我们要一个个的去试的。我们需要从字符'0'到'9'一个个的去赋值,然后判断它是否合法,如果合法则递归到下一个位置。当然,这里还有一个细节就是如果尝试完了所有的情况都不合法了,还需要回溯。所以这里还需要在后面将位置的值设置成'.'回去。这也是深度优先遍历里最容易忽略的地方。
有了上面这部分之后整个问题的解决方法就完整了。当然,从细节来说还有一个地方就是判断一个点赋值之后是否合法。假设我们定义方法isValid(i, j)来判断。我们需要检查所在的i行,所在的j列以及i, j所处在的那个3 x 3的矩阵里是否有和当前值重复的元素。前面两个比较好对付,就是找针对这个位置所对应的小矩阵并且去遍历它有点费脑筋。
首先给定位置i, j,我们该怎么来求对应的小矩阵呢?从前面一篇判断一个数独矩阵是否合法的问题里,我们找这个对应的小矩阵核心就是要找到它对应的这个小矩阵的起始点位置。比如(0, 0), (0, 3), (0, 6), (3, 0), (3, 3), (3, 6)等这些个点。对于任意点i, j来说,它对应的小矩阵的起始点位置则是 (i / 3 * 3, j / 3 * 3)。因为对于任意点i来说,它无非就是对应着最前面3行或者中间3行或者最后面3行这3种情况。当它除以3之后得到的值可能为0, 1, 2。相当于对应这每个3行的一个索引。然后在乘以3则得到对应具体矩阵里的位置。有了这个之后再结合前面示例里怎么用一个变量来遍历这个矩阵的方法就可以得到完整的实现了。
这样,最终的代码实现如下:
public class Solution { public void solveSudoku(char[][] board) { dfs(board, 0, 0); } private boolean dfs(char[][] board, int i, int j) { if(j >= 9) { j = 0; i++; } if(i >= 9) return true; if(board[i][j] != '.') return dfs(board, i, j + 1); for(char c = '1'; c <= '9'; c++) { board[i][j] = c; if(isValid(board, i, j) && dfs(board, i, j + 1)) { return true; } board[i][j] = '.'; } return false; } public boolean isValid(char[][] board, int x, int y) { for(int i = 0; i < 9; i++) { if(i != x && board[i][y] == board[x][y]) return false; } for(int i = 0; i < 9; i++) { if(i != y && board[x][i] == board[x][y]) return false; } int i = x / 3 * 3; int j = y / 3 * 3; for(int k = 0; k < 9; k++) { int xIndex = i + k / 3; int yIndex = j + k % 3; if(x == xIndex && y == yIndex) continue; if(board[xIndex][yIndex] == board[x][y]) return false; } return true; } }
总结
对于深度优先遍历的问题,它其实是一个递归的问题。它的思路比较简单,在实现细节上要注意回溯的时候将一些值恢复。另外里面一些代码对问题的解决方式描述比较精炼,这是需要一些思考提炼才能得到的。值得多推敲和反思。
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
leetcode:leetcode刷题
LeetCode:LeetCode的代码
Leetcode:LeetCode解题代码
加油站问题leetcode LeetCode LeetCode-JS分类列表: :smiling_face_with_smiling_eyes: :flushed_face: :winking_face: :face_with_tongue: :face_with_open_mouth: :beaming_face_with_smiling_...
LeetCode:LeetCode的注释
leetcode:LeetCode问题
leetcode:LeetCode题解