数独

import java.util.*;

public class Main {
    public static int[][] sudo = new int[9][9];//创建数组
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sudo[i][j] = sc.nextInt(); //创建数独
                }
            }
            if (backTracking(sudo)) {
                for (int i = 0; i < 9; i++) {
                    for (int j = 0; j < 9; j++) {
                        if (j == 8) {
                            //最后一位数需要换行输出
                            System.out.println(sudo[i][j]);
                        } else {
                            System.out.print(sudo[i][j] + " ");
                        }
                    }
                }
            }
        }
    }

    public static boolean backTracking(int[][] sudo) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) { //遍历数组
                if (sudo[i][j] != 0) { //如果不需要填数字直接continue
                    continue;
                }
                for (int k = 1; k <= 9; k++) { //循环填数字
                    if (isValid(i, j, k, sudo)) { //判断填入数字是否符合要求
                        sudo[i][j] = k; //填数字
                        if (backTracking(sudo)) { //递归
                            return true;
                        }
                        sudo[i][j] = 0; //回溯
                    }
                }
                return false;//如果没有符合要求的数字返回false
            }
        }
        return true;
    }

    public static boolean isValid(int row, int col, int k, int[][] sudo) {
        for (int i = 0; i < 9; i++) { //检查行
            if (sudo[row][i] == k) {
                return false;
            }
        }
        for (int i = 0; i < 9; i++) { //检查列
            if (sudo[i][col] == k) {
                return false;
            }
        }
        int startRow = (row / 3) * 3;
        int endCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) { //检查九宫格
            for (int j = endCol; j < endCol + 3; j++) {
                if (sudo[i][j] == k) {
                    return false;
                }
            }
        }
        return true;
    }
}

import java.util.*;
public class Test{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        List<Set<Integer>> listRow=new ArrayList<Set<Integer>>();
        List<Set<Integer>> listCol=new ArrayList<Set<Integer>>();
        List<Set<Integer>> listGroup=new ArrayList<Set<Integer>>();
        int[][] Soduku=new int[9][9];
        for(int i=0;i<9;i++) {
            listRow.add(new TreeSet<Integer>());
            listCol.add(new TreeSet<Integer>());
            listGroup.add(new TreeSet<Integer>());
        }
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) {
                Soduku[i][j]=scanner.nextInt();
                listRow.get(i).add(Soduku[i][j]);
                listCol.get(j).add(Soduku[i][j]);
                listGroup.get(i/3*3+j/3).add(Soduku[i][j]);
            }
        }
        soduku(Soduku,listRow,listCol,listGroup,0);
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
            	if(j!=8) {
            		System.out.print(Soduku[i][j]+" ");
            	}else {
            		System.out.println(Soduku[i][j]);
            	} 
            } 
        }
    }
    public static Boolean soduku(int[][] Soduku,List<Set<Integer>> listRow,List<Set<Integer>> listCol,List<Set<Integer>> listGroup,int index){
    	Set<Integer> temp=new TreeSet<Integer>();
        Set<Integer> set1=new TreeSet<Integer>();
        Set<Integer> set2=new TreeSet<Integer>();
        int row=index/9;
        int col=index%9;
        int group=row/3*3+col/3;
//        System.out.println(index);
        if(index>80) {
        	return true;
        }
        for(int i=0;i<10;i++) {
        	temp.add(i);
        }
        if(Soduku[row][col]!=0) {
        	return soduku(Soduku, listRow, listCol, listGroup, index+1);
        }else {
        	set1.addAll(listRow.get(row));
        	set1.addAll(listCol.get(col));
        	set1.addAll(listGroup.get(group));
        	set2.addAll(temp);
        	set2.removeAll(set1);
        	if(set2.size()==0) {
        		return false;
        	}
//        	System.out.print(set2+"--->"+set2.size());
        	for(Iterator<Integer> it=set2.iterator();it.hasNext();) {
        		int t=it.next();
//        		System.out.println("-------->"+t);
//        		System.out.println(t);
        		Soduku[row][col]=t;
        		listRow.get(row).add(t);
        		listCol.get(col).add(t);
        		listGroup.get(row/3*3+col/3).add(t);
        		if(soduku(Soduku, listRow, listCol, listGroup, index+1)) {
        			return true;
        		}
//        		System.out.println(index+"------>"+t);
        		Soduku[row][col]=0;
        		listRow.get(row).remove(t);
        		listCol.get(col).remove(t);
        		listGroup.get(row/3*3+col/3).remove(t);
        	}
        	set1.clear();
        	set2.clear();
	        return false;
        }
    }
}

import java.util.Scanner;
public class Main {
    private int[][] numMap = new int[9][9];
    private int staLen;
    private Coordinate[] stack = new Coordinate[81];

    public void run() {
        init();
        find(0);
    }
       //dfs
    private void find(int step) {
        if (step == staLen) {
                     //判断是否找到一个解
            show();
                     System.exit(0);
        } else {
            for (int i = 1; i <= 9; i++) {
               int x = stack[step].x;
               int y = stack[step].y;
                if (tryNum(x, y, i)) {
                    numMap[y][x] = i;
                                   find(step + 1);//若可填入，继续尝试下一个空
                    numMap[y][x] = 0;//回溯时把原来填的数字归0
                }
            }
        }
    }
       //判断坐标（x,y）能否填入num
    private boolean tryNum(int x, int y, int num) {
              //先判断同行同列有无重复
        for (int i = 0; i < 9; i++) {
            if (numMap[y][i] == num || numMap[i][x] == num) {
                return false;
            }
        }
              //分组判断
        x /= 3;
        y /= 3;
        for (int i = y * 3; i < y * 3 + 3; i++) {
            for (int j = x * 3; j < x * 3 + 3; j++) {
                if (numMap[i][j] == num) {
                    return false;
                }
            }
        }
        return true;
    }
       //初始化读入数据
    private void init() {
              Scanner sc = new Scanner(System.in);
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                numMap[y][x] = sc.nextInt();
                if (numMap[y][x] == 0) {
                    stack[staLen++] = new Coordinate(x, y);
                }
            }
        }
        sc.close();
    }
       //输出
    private void show() {
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                               //每行第一个数字前面没有空格
                if(x == 0){
                    System.out.print(numMap[y][x]);
                }else{
                    System.out.print(" " + numMap[y][x]);
                }
            }
            System.out.println();
        }
    }
       //坐标类
    static class Coordinate {
        int x;
        int y;
        Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static void main(String[] args){
        new Main().run();
    }
}