数独(抽象dfs)
import java.util.Scanner;
public class 结果填空__数独 {
public static char mp[][] = new char[10][10];
public static int visx[][] = new int[10][10];
public static int visy[][] = new int[10][10];
public static int visv[][] = new int[10][10];
public static int find = 0;
//public static int a[][] = {{1,0},{-1,0},{0,-1},{0,1}};
public static void main(String[] args) {
Scanner sca = new Scanner(System.in);
for(int i = 0;i < 9; i ++) {
mp[i] = sca.next().toCharArray();
}
for(int i = 0;i < 9;i ++) {
for(int j = 0;j < 9; j ++) {
if(mp[i][j] != '*') {
//System.out.println(mp[i][j]);
visx[i][mp[i][j] - '0'] = 1;
visy[j][mp[i][j] - '0'] = 1;
visv[i/3 *3 + j/3 ][mp[i][j] - '0'] = 1;
}
}
}
dfs(0,0);
}
private static void dfs(int x,int y) {
if(find == 1) {
return ;
}
if(x == 9) {
find = 1;
for(int i = 0;i < 9;i ++) {
for(int j = 0;j < 9; j ++) {
System.out.print(mp[i][j]);
}
System.out.println();
}
return ;
}
if(y == 9) {
x = x + 1;
y = 0;
}
if(mp[x][y] != '*') {
dfs(x, y + 1);
return ;
}
for(int i = 1 ;i <= 9; i ++) {
if( (visx[x][i] == 0) && (visy[y][i] == 0) && (visv[x/3 *3 + y/3 ][i] == 0)) {
visx[x][i] = 1;
visy[y][i] = 1;
visv[x/3 *3 + y/3 ][i] = 1;
mp[x][y] = (char) ('0' + i);
dfs(x,y + 1);
visx[x][i] = 0;
visy[y][i] = 0;
visv[x/3 *3 + y/3 ][i] = 0;
mp[x][y] = '*';
}
}
}
}
/*
*26******
***5*2**4
***1****7
*3**2*18*
***3*9***
*54*1**7*
5****1***
6**9*7***
******75*
*/