解数独(回溯法)

问题描述

本题的要求就是输入数独题目，程序输出数独的唯一解。我们保证所有已知数据的格式都是合法的，并且题目有唯一的解。
格式要求，输入9行，每行9个字符，0代表未知，其它数字为已知。 输出9行，每行9个数字表示数独的解。
输入：
005300000
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700
输出：
145327698
839654127
672918543
496185372
218473956
753296481
367542819
984761235
521839764

java实现

import java.util.Scanner;publicclassMain {publicstaticboolean flag =false;// 标记是否已找到publicstaticvoidmain(String[] args) {
        Scanner sc =new Scanner(System.in);int arr[][] =newint[10][10];
        String str =new String();for (int i =1; i < arr.length; i++) {
            str = sc.nextLine();for (int j =1; j < arr[i].length; j++)
                arr[i][j] = str.charAt(j -1) -'0';
        }
        sc.close();
        dfs(1,1, arr);
    }privatestaticvoiddfs(int x,int y,int[][] arr) {if (flag)return;if (x >9) {
            output(arr);
            flag =true;return;
        }if (y >9) {
            dfs(x +1,1, arr);
        }elseif (arr[x][y] !=0)
            dfs(x, y +1, arr);else {for (int i =1; i <10; i++) {if (check(x, y, i, arr)) {
                    arr[x][y] = i;
                    dfs(x, y +1, arr);//所选路径错误则置0,回溯选择新的路径
                    arr[x][y] =0;
                }
            }
        }
    }// 判断数独所选路径是否正确,返回布尔型privatestaticbooleancheck(int x,int y,int num,int[][] arr) {// 检查x轴for (int i =1; i <10; i++) {if (arr[x][i] == num)returnfalse;
        }// 检查y轴for (int i =1; i <10; i++) {if (arr[i][y] == num)returnfalse;
        }// 检查九宫格for (int i = (x -1) /3 *3 +1; i <= (x -1) /3 *3 +3; i++) {for (int j = (y -1) /3 *3 +1; j <= (y -1) /3 *3 +3; j++) {if (arr[i][j] == num)returnfalse;
            }
        }returntrue;
    }// 输出对应的数独解privatestaticvoidoutput(int[][] arr) {for (int i =1; i < arr.length; i++) {for (int j =1; j < arr[i].length; j++) {
                System.out.print(arr[i][j]);
            }
            System.out.println();
        }
    }
}