点击上方蓝字设为星标
今天分享一个LeetCode题，题号是37，题目标题是解数独，题目标签是散列表和回溯算法。
题目描述
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。
一个数独
一个数独。
答案被标成红色
答案被标成红色。
Note:
给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的
解题
此题题目标签是散列表和回溯算法，但我觉得散列表换成直接寻址表更巴适。因为一个数独只有1~9的数字。
回到题目描述，一个数独的解法需要遵循以下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
使用直接寻址表，可以设计成
数字：Booleal类型[27个空间默认为False]
假设行的下标为i，列的下标为j，宫格的索引为k，某数字的i、j+9和k+18下标只能出现true一次，下次判断时出现同样的true就不满足一个有解的数独了。
下标i和下标j可以从行和列中直接获取，那宫格的索引k又如何获取呢？看下面图：
三下标的索引
k随着i变化和k随着j变化都有规律的，不多说，直接给公式：k = (int)(i / 3) * 3 + (int)(j / 3)。
要注意的是board二维数组保存的是字符，需换成相应的整数。代码如下：
boolean[][] address = new boolean[9][27]; // 默认false
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int index = board[i][j] - '1'; // board数组保存的是字符，需换成相应的整数
// 宫格的索引
int k = i / 3 * 3 + j / 3;
// 记录某数字存放的位置
address[index][i] = true;
address[index][j + 9] = true;
address[index][k + 18] = true;
}
}
}
得出来的address的值如下：
下标 : 值[一维数组]
0 : F T F F T F F T F F F F T T F F F T F T F F F T F T F
1 : F F F F F T T F F F F F F T F T F F F F F F T F F F T
2 : T F F T T F F F F F T F F F T F F T T F F F T T F F F
3 : F F F F T F F T F T F F T F F F F F F F F T F F F T F
4 : T T F F F F F T F T F F F F T F F T T T F F F F F F T
5 : F T T T F T T F F T T F F T F F T T T F T F T T T F F
6 : T F F F F T F F T T F F F T F F T F F T F T F F F F T
7 : F F T T T F T F T T F T T T F F T F T F F T T F F T T
8 : F T T F F F F T T F T F F T T F F T T T F F F F F T T
我在前几篇写过LeetCode第36号题，是直接使用散列表（哈希表）做这道题，文章的动画视频 如下：
动画：散列表，也可以用直接寻址表表示
动画：LeetCode17号题使用回溯算法
// 找寻空位置
while (board[i][j] != '.') {
if (++j >= 9) {
i++;
j = 0;
}
if (i >= 9) return true; // 到这里说明数独已填入的数字是有解的
// 不能返回为空，返回为空会破坏掉已填入的数字
}
动画：有解数独使用回溯算法
Code
public void solveSudoku(char[][] board) {
// 创建直接寻址表 记录某数字存放的位置 空间换时间
boolean[][] address = new boolean[9][27];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int index = board[i][j] - '1'; // board数组保存的是字符，需换成相应的整数
// 宫格的索引
int k = i / 3 * 3 + j / 3;
// 记录某数字存放的位置
address[index][i] = true;
address[index][j + 9] = true;
address[index][k + 18] = true;
}
}
}
// 回溯算法，和dfs类似，dfs一般做遍历，没有回溯
track(board, address, 0, 0);
}
private boolean track(char[][] board, boolean[][] address, int i, int j) {
// 找寻空位置
while (board[i][j] != '.') {
if (++j >= 9) {
i++;
j = 0;
}
if (i >= 9) return true; // 到这里说明数独已填入的数字是有解的
}
for (int index = 0; index < 9; index++) {
// 宫格索引
int k = i / 3 * 3 + j / 3;
if (!address[index][i] && !address[index][j + 9] && !address[index][k + 18]) {
// index 与 行 列 宫格索引不冲突
// 填入 index，要注意换成对应字符
board[i][j] = (char) (index + '1');
address[index][i] = true;
address[index][j + 9] = true;
address[index][k + 18] = true;
// 递归
if (track(board, address, i, j))
return true;
// 回溯
board[i][j] = '.';
address[index][i] = false;
address[index][j + 9] = false;
address[index][k + 18] = false;
}
}
}
return false; // 当前位置与所有index数字冲突，直接返回false，回到上一个空格
}
执行结果
执行用时 : 2 ms , 在所有 Java 提交中击败了 96.94% 的用户
内存消耗 : 34.6 MB , 在所有 Java 提交中击败了 94.14% 的用户
END
点“在看”你懂得
原文始发于微信公众号（五分钟学算法）：LeetCode 图解 | 37.解数独
