问题描述
如下所示,玩家需要根据9*9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个色九宫内的数字均含1-9,不重复 数独的答案都是唯一的,所以,多个解也称为无解 本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的目。但对会使用计算机编程的你来说,恐怕易如反掌了 本题的要求就是输入数独题目,程序输出的一解,我们保证所有已知数据的格式都是合法的,并且题目有一的解 格式要求,输入9行,每行9个数字,0代表未知,其它数字为已知。
输入：
0,0,5,3,0,0,0,0,0
8,0,0,0,0,0,0,2,0
0,7,0,0,1,0,5,0,0
4,0,0,0,0,5,3,0,0
0,1,0,0,7,0,0,0,6
0,0,3,2,0,0,0,8,0
0,6,0,5,0,0,0,0,9
0,0,4,0,0,0,0,3,0
0,0,0,0,0,9,7,0,0
代码：
public class _dfs数独 { public static void main(String[] args) { /* Scanner sc = new Scanner(System.in); char[][] table = new char[9][]; for (int i = 0; i < 9; i++) { table[i] = sc.nextLine().toCharArray(); } */ char[][] table = {{'0','0','5','3','0','0','0','0','0'}, {'8','0','0','0','0','0','0','2','0'}, {'0','7','0','0','1','0','5','0','0'}, {'4','0','0','0','0','5','3','0','0'}, {'0','1','0','0','7','0','0','0','6'}, {'0','0','3','2','0','0','0','8','0'}, {'0','6','0','5','0','0','0','0','9'}, {'0','0','4','0','0','0','0','3','0'}, {'0','0','0','0','0','9','7','0','0'}}; dfs(table,0,0); } private static void dfs(char[][] table, int x, int y) { if (x == 9) { print(table); System.exit(0); } if (table[x][y] == '0') { // 虚位以待 for (int k = 1; k < 10; k++) { if (check(table, x, y, k)) { table[x][y] = (char)('0' + k); dfs(table, x + (y+1) / 9, (y+1) % 9); // 处理下一个状态 } } table[x][y] = '0'; // 回溯 } else { dfs(table, x + (y+1) / 9, (y+1) % 9); // 处理下一个状态 } } private static void print(char[][] table) { for (int i = 0; i < 9; i++) { System.out.println(table[i]); } } private static boolean check(char[][] table, int i, int j, int k) { // 检查同行同列 for(int l = 0; l < 9; l++) { if (table[i][l] == (char)('0' + k)) return false; if (table[i][l] == (char)('0' + k)) return false; } // 检查小九宫格 for (int l = (i / 3)*3; l < (i / 3 + 1)*3; l++) { for (int m = (j / 3)*3; m < (j / 3 + 1)*3; m++) { if(table[i][m] == (char)('0' + k)) return false; } } return true; } }
