37.解数独-创新互联
编写一个程序,通过填充空格来解决数独问题。
让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:域名注册、虚拟主机、营销软件、网站建设、莲池网站维护、网站推广。数独的解法需 遵循如下规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)
数独部分空格内已填入了数字,空白格用 ‘.’ 表示。
提示:输入: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.解数独-创新互联
标题URL:http://myzitong.com/article/ddgccj.html