本文主要是介绍DFS 求数独问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述
如下所示,玩家需要根据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;}}
这篇关于DFS 求数独问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
