sudoku.java

PKU中一些数据结构基本算法题的java实现

package PKU.DFS;
import java.util.Scanner;


/**ID:2676
 * DFS
 * @author yhm
 *
 */
public class Sudoku {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseNum = cin.nextInt();
		for(int i=0;i<caseNum;i++){
			int[][] m = new int[9][9];
			for(int j=0;j<9;j++){
				String str = cin.next();
				for(int k=0;k<9;k++){
					m[j][k] = str.charAt(k)-'0';
				}
			}
			//check(m,0,4,4);
			dfs(m,0);
		}

	}
	static boolean dfs(int[][] m, int n){
		
		if(n==81){
			for(int i=0;i<9;i++){
				for(int j=0;j<9;j++){
					System.out.print(m[i][j]);
				}
				System.out.println();
			}
			return true;
		}
		
		int x = n%9;
		int y = n/9;
		
		
		if(m[x][y]!=0){
			return dfs(m,n+1);
		}
		else{
			for(int value=1;value<=9;value++){
				boolean chR = check(m,x,y,value);
				if(chR){
					m[x][y] = value;
					if(dfs(m,n+1)){
						return true;
					}
					m[x][y] = 0;
				}			
			}
		}


		return false;
	}
	static boolean check(int[][] m, int x, int y, int value){
		for(int i=0;i<9;i++){
			if(value==m[x][i] || value==m[i][y]){
				return false;
			}
		}
		int j = x/3;
		int k = y/3;
		int j1 = j*3;
		int k1 = k*3;
		int l1 = j1+3;
		int l2 = k1+3;
		for(j=j1;j<l1;j++){
			for(k=k1;k<l2;k++){
				int temp = m[j][k];
				if(value==temp){
					return false;
				}
			}
		}
		return true;
	}

}