本题采用了非常规的dfs策略,要格外注意退出时机。
(正常dfs策略应该为从左上到右右下依次dfs而不是每次dfs都从新扫描)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
static boolean [][] rows = new boolean[9][10],
cols = new boolean[9][10];
static boolean [][][] blocks = new boolean[3][3][10];
static char[][] g = new char[9][9];
static int cnt = 0;
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception{
for(int i = 0; i < 9; i++) {
String s = reader.readLine();
g[i] = s.toCharArray();
for(int j = 0; j < 9; j++) {
char c = s.charAt(j);
if(c != '.') {
cnt++;
rows[i][c - '0'] = cols[j][c - '0'] = blocks[i / 3][j / 3][c - '0'] = true;
}
}
}
dfs();
log.flush();
log.close();
reader.close();
}
static boolean dfs() throws Exception {
if(cnt == 81) {
for(int i = 0; i < 9; i++) {log.write(g[i]);log.write("\n");}
return true;
}
for(int i = 0; i < 9; i++)
for(int j = 0; j < 9; j++)
if(g[i][j] == '.') {
for(int k = 1; k <=9; k++)
if(!rows[i][k] && !cols[j][k] && !blocks[i / 3][j / 3][k]) {
g[i][j] = (char)(k + '0');
rows[i][k] = cols[j][k] = blocks[i / 3][j / 3][k] = true;
cnt ++;
if(dfs()) return true;
g[i][j] = '.';
rows[i][k] = cols[j][k] = blocks[i / 3][j / 3][k] = false;
cnt --;
}
return false; //剪枝
}
return false;//只在这里false会死循环,why!!!???
}
}