37. 解数独
编写一个程序，通过填充空格来解决数独问题。
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：
域名注册、
虚拟主机、营销软件、网站建设、
莲池网站维护、网站推广。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
示例 1：
输入：board = [[“5”,“3”,“.”,“.”,“7”,“.”,“.”,“.”,“.”],[“6”,“.”,“.”,“1”,“9”,“5”,“.”,“.”,“.”],[“.”,“9”,“8”,“.”,“.”,“.”,“.”,“6”,“.”],[“8”,“.”,“.”,“.”,“6”,“.”,“.”,“.”,“3”],[“4”,“.”,“.”,“8”,“.”,“3”,“.”,“.”,“1”],[“7”,“.”,“.”,“.”,“2”,“.”,“.”,“.”,“6”],[“.”,“6”,“.”,“.”,“.”,“.”,“2”,“8”,“.”],[“.”,“.”,“.”,“4”,“1”,“9”,“.”,“.”,“5”],[“.”,“.”,“.”,“.”,“8”,“.”,“.”,“7”,“9”]]
输出：[[“5”,“3”,“4”,“6”,“7”,“8”,“9”,“1”,“2”],[“6”,“7”,“2”,“1”,“9”,“5”,“3”,“4”,“8”],[“1”,“9”,“8”,“3”,“4”,“2”,“5”,“6”,“7”],[“8”,“5”,“9”,“7”,“6”,“1”,“4”,“2”,“3”],[“4”,“2”,“6”,“8”,“5”,“3”,“7”,“9”,“1”],[“7”,“1”,“3”,“9”,“2”,“4”,“8”,“5”,“6”],[“9”,“6”,“1”,“5”,“3”,“7”,“2”,“8”,“4”],[“2”,“8”,“7”,“4”,“1”,“9”,“6”,“3”,“5”],[“3”,“4”,“5”,“2”,“8”,“6”,“1”,“7”,“9”]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 ‘.’
题目数据 保证 输入数独仅有一个解
思路：(回溯)
- 由于题目有三个条件，所以应该存储每个条件的数字使用情况；
- 遍历数字，只有在三个条件中都未使用的时，将该数暂存到该位置：
- 如果在以上数字条件下，下面的位置都能找到合适的数字，则成立；
- 如果在上述数字条件下，下面的位置遍历1-9，都不能找到合适的数字，则返回false，回溯上一步结果，上一步继续往后遍历，直到9，如果找不到继续回溯；
本题关键：
将 backtracking 函数的返回类型设为 boolean 类型，如果下一次迭代返回结果为 true，则填入数字正确，否则才数字不正确，回溯，继续遍历剩余数字：
bod[r][c] = (char)(num + '0');
rowsUsed[r][num] = colsUsed[c][num] = cubesUsed[cubeNum(r, c)][num] = true;
if(backtracking(nr , nc)) {
return true;
}else {//不成立回溯
bod[r][c] = '.';
rowsUsed[r][num] = colsUsed[c][num] = cubesUsed[cubeNum(r, c)][num] = false;
continue;
}
代码：(Java)
public class sudoku {public static void main(String[] args) {//TODO Auto-generated method stub
char [][] board = { {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
{'.', '.', '.', '.', '8', '.', '.', '7', '9'}
};
solveSudoku(board);
for(int i = 0; i< 9; i++) { for(int j = 0; j< 9; j++) { System.out.print(board[i][j]+ " ");
}
System.out.println();
}
}
private static boolean[][] rowsUsed = new boolean[9][10];
private static boolean[][] colsUsed = new boolean[9][10];
private static boolean[][] cubesUsed = new boolean[9][10];
private static char[][] bod;
public static void solveSudoku(char[][] board) {bod = board;
for(int r = 0; r< 9; r++) { for(int c = 0; c< 9; c++) { if(bod[r][c] != '.') {int num = Character.getNumericValue(bod[r][c]);
rowsUsed[r][num] = true;
colsUsed[c][num] = true;
cubesUsed[cubeNum(r, c)][num] = true;
}
}
}
backtracking(0, 0);
}
private static boolean backtracking(int r, int c) {// TODO Auto-generated method stub
if(r == 9) { return true;
}
int nr, nc;
if(c == 8) { nr = r + 1;
nc = 0;
}else { nr = r;
nc = c + 1;
}
if(bod[r][c] != '.') { return backtracking(nr , nc);
}
for(int num = 1; num<= 9; num++) { if(rowsUsed[r][num] || colsUsed[c][num] || cubesUsed[cubeNum(r, c)][num]) { continue;
}
bod[r][c] = (char)(num + '0');
rowsUsed[r][num] = colsUsed[c][num] = cubesUsed[cubeNum(r, c)][num] = true;
if(backtracking(nr , nc)) {//判断条件为递归结果
return true;
}else {//不成立回溯
bod[r][c] = '.';
rowsUsed[r][num] = colsUsed[c][num] = cubesUsed[cubeNum(r, c)][num] = false;
continue;
}
}
return false;
}
private static int cubeNum(int i, int j) {//返回第几个方块
// TODO Auto-generated method stub
int r = i / 3;
int c = j / 3;
return r * 3 + c;
}
}
运行结果：
注：仅供学习参考！
题目来源：力扣.
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
分享文章：37.解数独-创新互联
标题来源：
http://www.cdkjz.cn/article/ddgccj.html
