题解 | #Sudoku#

//这道题代码不难, 但是思路比较拗口
//首先判断一个数是否满足要求需要写一个isSignal()函数, 判断行或列比较简单, 只要固定一个不变遍历另一个即可
//但是遍历9宫格有技巧, 主要是第一个行坐标和第一个列坐标  (i/3)*3比较难想到
//然后是对这道题的分析. 首先在二维数组中找到值为0的元素, 然后这个元素有1~9   9种选择, 选择一个满足条件后, 选择下一个, 如果下一个所有选择都不行, 回溯, 将它置为0, 重新选择, 满足条件后再选择下一个, 所以广度是有9种选择, 深度是所有需要选择的元素
//需要注意, 数组遍历完了, 没有false, 即为true, 如果1~9都选择完了没有满足条件的返回false, 如果下一个不需要回溯需要返回true, 以免把1~9遍历完了都返回false

import java.util.Arrays;
import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int[][] arr = new int[9][9];

        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                arr[i][j] = sc.nextInt();
            }
        }
        sudoku(arr);
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                System.out.print(arr[i][j]+" ");
            }
            System.out.println();
        }
    }

    public static boolean sudoku(int [][]arr)
    {

        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if(arr[i][j] == 0)
                {
                    int k = 1;
                    for (; k < 10; k++)
                    {
                        if(isSignal(i,j,k,arr))
                        {
                            arr[i][j] = k;
                            if( !sudoku(arr) )
                            {
                                arr[i][j] = 0;
                            }
                            else return true;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }


    public static boolean isSignal( int row, int col, int digit,  int[][] arr)
    {
        for (int i = 0; i < 9; i++)
        {
            if(arr[row][i] == digit)
            {
                return false;
            }
        }

        for (int i = 0; i < 9; i++)
        {
            if(arr[i][col] == digit)
            {
                return false;
            }
        }
        //遍历九宫格 0,1,2   3,4,5  6,7,8

        for (int i = (row/3)*3; i < (row/3)*3+3; i++)
        {
            for (int j = (col/3)*3; j < (col/3)*3+3; j++)
            {

                if(arr[i][j] == digit)
                {
                    return false;
                }
            }
        }
        return true;
    }
}




/*

import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int[][] board = new int[9][9];
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                board[i][j] = in.nextInt();
            }
        }
        solveSudoku(board);
        //输出二维矩阵
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 8; j++)
            {
                System.out.print(board[i][j] + " ");
            }
            System.out.println(board[i][8]);//换行，每一行的最后一个数字
        }
    }

    public static boolean solveSudoku(int[][] board)
    {
        //「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
        // 一行一***定下来之后，递归遍历这个位置放9个数字的可能性！」
        for (int i = 0; i < 9; i++)
        { // 遍历行
            for (int j = 0; j < 9; j++)
            { // 遍历列
                if (board[i][j] != 0)
                { // 跳过原始数字
                    continue;
                }
                for (int k = 1; k <= 9; k++)
                { // (i, j) 这个位置放k是否合适
                    if (isValidSudoku(i, j, k, board))
                    {
                        board[i][j] = k;//将k放在（i，j）
                        if (solveSudoku(board))
                        { // 如果找到合适一组立刻返回
                            return true;
                        }
                        board[i][j] = 0;//回溯
                    }
                }
                // 9个数都试完了，都不行，那么就返回false
                return false;
                // 因为如果一行一***定下来了，这里尝试了9个数都不行，
                // 说明这个棋盘找不到解决数独问题的解！
                // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
            }
        }
        // 遍历完没有返回false，说明找到了合适棋盘位置了
        return true;
    }


     * 判断棋盘是否合法有如下三个维度:
     * 同行是否重复
     * 同列是否重复
     * 9宫格里是否重复

    public static boolean isValidSudoku(int row, int col, int val, int[][] board)
    {
        // 同行是否重复
        for (int i = 0; i < 9; i++)
        {
            if (board[row][i] == val)
            {
                return false;
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++)
        {
            if (board[j][col] == val)
            {
                return false;
            }
        }
        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++)
        {
            for (int j = startCol; j < startCol + 3; j++)
            {
                if (board[i][j] == val)
                {
                    return false;
                }
            }
        }
        return true;
    }
}
*/