数独问题_数独输入9行,每行为空格隔开的9个数字,为0的地方就是需要填充的。

学会了这个算法，就再也不怕有做不出来的数独啦！
题目如下：
数独是一个非常有名的游戏。整个是一个9X9的大宫格，其中又被划分成9个3X3的小宫格。要求在每个小格中放入1-9中的某个数字。要求是：每行、每列、每个小宫格中数字不能重复。 现要求用计算机求解数独。

输入描述:
输入9行，每行为空格隔开的9个数字，为0的地方就是需要填充的数字

思路：
这个问题很明显就是要用回溯法做的，可是问题来了，要是每一个空都要回溯一次的话栈会溢出，所以一些情况是要剪掉的。本来我是打算先把能够确定的值都确定下来，然后就能减少每一个空搜索的次数，但不得不说这方法有点麻烦，最后我还是放弃了。后来看了一下别人的代码，其实好像并不用剪枝…这真的尴尬，只要让错误的探测走不到最后一步就行了，这样栈也不会太深，自然就不会栈溢出。
下面是加了注释的源代码：

package com.wangyi;
import java.util.*;
//a 97 A 65
/*
 * 
0 9 0 0 0 0 0 6 0
8 0 1 0 0 0 5 0 9
0 5 0 3 0 4 0 7 0
0 0 8 0 7 0 9 0 0
0 0 0 9 0 8 0 0 0
0 0 6 0 2 0 7 0 0
0 8 0 7 0 5 0 4 0
2 0 5 0 0 0 8 0 7
0 6 0 0 0 0 0 9 0
*/
import java.util.*;
public class Main{
    static int[][] s;
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        s=new int[10][10];
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++)
                s[i][j]=in.nextInt();
        }
        findNumber(0,0);
    }
    static void findNumber(int row,int col){
    
        if(row==8&&col==9){
             print();
            return;
        }
        if(col==9){
           row++;
            col=0;
        }
        if(s[row][col]==0){
             for(int i=1;i<=9;i++){
                 //必须在该项找到一个可用值他才会继续往下一个寻找
                 //即要是该项是错误的话，他是不可能一直走到最后一个的
                 //可是问题来了，回溯的过程中要是错误了，它就会影响到canUse的判断
                 //如果错误了，那么他之前填的值要变为0
                 if(canUse(row,col,i)){
                     s[row][col]=i; 
                    findNumber(row, col+1);
                 }else{
                	 //要是找不到能用的值，就必须把它置为0，所以回溯过程要是错误了，就能修正
                	 //要是一直找不到，则会直接返回，不会继续找下一个，这也决定了错误的答案是走不到最后一个的
                	 s[row][col]=0;
                 }
             }
             
        }else{
            findNumber(row,col+1); 
        }
    }
    static boolean canUse(int row,int col,int number){
        int m=row/3,n=col/3;
        for(int i=0;i<9;i++){
        	if(s[row][i]==number||s[i][col]==number){
        		return false;
        	}
        }
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(s[m*3+i][n*3+j]==number)
                    return false;
            }
        }
        return true;
    }
    static void print(){
         for(int i=0;i<9;i++){
            for(int j=0;j<9;j++)
               System.out.print(s[i][j]+" ");
            System.out.println();
        }
         System.out.println("==========================");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

注释特别多的地方，其实就是我一开始有点迷惑的地方，我一直在想回溯过程要是错误了的话，他要怎么修正。结论就是当前一个值错了的时候，下一个找不到合适的值填充，自然变为0，那也证明了前面的是错了，不会继续走下去，通过循环（注意这里有个从1到9的循环）也把前面错误的值改为0，这样自然不会影响canUse的判断。细微的地方足以体现这个作者的智慧。