典型的DFS题目，虽然编码有点长，但思路不算复杂，我觉得达不到hard难度。
1 题目描述
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
2 思路
回溯。
3 java代码
class Solution {
/*
典型的回溯题目
*/
boolean[][] rowmap = new boolean[9][9]; // 记录每一行某个数字是否出现过
boolean[][] colmap = new boolean[9][9]; // 记录每一列某个数字是否出现过
boolean[][][] square = new boolean[3][3][9]; // 记录每一个放个中某个数字是否出现过
public void solveSudoku(char[][] board) {
// 初始化
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] == '.') {
continue;
} else {
int num = (int)(board[i][j] - '0');
rowmap[i][num - 1] = true;
colmap[j][num - 1] = true;
square[i / 3][ j / 3][num - 1] = true;
}
}
}
// 递归,深度优先搜索
dfs(board, 0, 0);
}
// i, j表示s搜索起始的位置
public boolean dfs(char[][] board, int i, int j) {
// 寻找下一个空格
while (i < 9) {
boolean flag = false;
while (j < 9 && !flag) {
if (board[i][j] == '.') {
flag = true;;
} else {
++j;
}
}
if (flag) {
break;
}
j = 0;
++i;
}
if (i == 9) { // 如果找不到下一个空格，说明已经得解
return true;
}
// 如果找到了，就尝试往这个空格里放数
for (int num = 1; num <= 9; ++num) {
if (!rowmap[i][num - 1] && !colmap[j][num - 1] && !square[i / 3][j / 3][num - 1]) {
board[i][j] = (char)('0' + num);
rowmap[i][num - 1] = true;
colmap[j][num - 1] = true;
square[i / 3][ j / 3][num - 1] = true;
if (dfs(board, i, j)) {
return true;
} else {
board[i][j] = '.';
rowmap[i][num - 1] = false;
colmap[j][num - 1] = false;
square[i / 3][ j / 3][num - 1] = false;
}
}
}
return false;
}
}