题解 | Sudoku

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
           int row = 9;
           int column = 9;
           int[][] vals = new int[row][column];
           for(int i = 0; i < row; i ++)
           {
               for(int j = 0; j < column; j ++)
               {
                   vals[i][j] = scanner.nextInt();
               }
           }
            fillVals(vals);
            /**
             * 打印
             */
            for(int i = 0; i < 9; i ++)
            {
                for(int j = 0; j < 9; j ++)
                {
                    System.out.print(vals[i][j] + " ");
                }
                System.out.print("\n");
            }


        }
    }
    public static boolean fillVals(int[][] vals)
    {
        for(int i = 0; i < 9; i ++)
        {
            for(int j = 0; j < 9; j ++)
            {
                if(vals[i][j] != 0)
                {
                    continue;
                }

                for(int k = 1; k <= 9; k ++)
                {
                    //请注意，这个标志位要在此处定义，不要在for(int k = 1; k <= 9; k ++)这个循环外定义
                    boolean flag = false;
                    int ir = i;
                    int ic = j;


                    int rStart = -1;
                    int rEnd = -1;
                    if(ir >= 0 &&
                            ir <= 2){
                        rStart = 0;
                        rEnd = 2;
                    }else if( ir >= 3 &&
                            ir <= 5){
                        rStart = 3;
                        rEnd = 5;
                    }else if( ir >= 6 &&
                            ir <= 8)
                    {
                        rStart = 6;
                        rEnd = 8;
                    }

                    int cStart = -1;
                    int cEnd = -1;
                    if(ic >= 0 &&
                            ic <= 2){
                        cStart = 0;
                        cEnd = 2;
                    }else if( ic >= 3 &&
                            ic <= 5){
                        cStart = 3;
                        cEnd = 5;
                    }else if( ic >= 6 &&
                            ic <= 8)
                    {
                        cStart = 6;
                        cEnd = 8;
                    }

                    //看包括（i,j）位置的3行，3列的正方形位置的元素是否有包括k，如果有包括k肯定不能把
                    //k放到位置(i,j)
                    boolean flag1 = false;
                    boolean flag2 = false;
                    boolean flag3 = false;
                    for(int r = rStart; r <= rEnd; r ++)
                    {

                        for(int c = cStart; c <= cEnd; c ++) {
                            if(vals[r][c] == k) {
                            flag1 = true;
                            break;
                            }
                        }
                        //说明包括（i,j）位置的3行，3列的正方形框里某个位置有元素等于k
                        if(flag1) {
                        break;
                        }
                    }
                    //flag1如果继续为false，说明包括（i,j）位置的3行，3列的正方形框里没有任何元素等于k，
                    //那就可以继续判断i行，0到8列的元素是否有包括k，如果包括k肯定不能把
                    //k放到位置(i,j)
                    if(!flag1) {
                        for(int c = 0; c < 9; c ++) {
                           if(vals[i][c] == k) {
                           flag2 = true;
                           break;
                           }
                        }
                        //flag2为false说明第i行，0到8列的元素中没有任何元素等于k,
                        //那就可以继续判断0行到8行，第j列的元素是否有包括k,如果包括k肯定不能把
                        //k放到位置(i,j)
                        if(!flag2) {
                            for(int r = 0; r < 9; r ++) {
                                if(vals[r][j] == k) {
                                    flag3 = true;
                                    break;
                                }
                            }
                        }
                    }

                    //说明：
                    //1、包括（i,j）位置的3行，3列的正方形位置的元素中没有任何元素等于k
                    //2、第i行，0到8列的元素中没有元素等于k
                    //3、第0到8行，j列的元素中没有元素等于k
                    //所以可以把k元素放到位置（i,j）
                    if(!flag1 &&
                    !flag2 &&
                    !flag3) {
                        vals[i][j] = k;
                        flag = true;
                    }
                    //位置（i,j）存放元素k之后，还得继续递归
                    if(flag) {
                        if (fillVals(vals)) {
                            return true;
                        }else{
                            //回溯
                            vals[i][j] = 0;
                        }
                    }
                }
                //这9个数都试完毕了，还是未找到合适的数字填充在位置（i,j），那么就返回false
                return false;

            }
        }
        return true;

    }
}