dfs深度搜索模板

import java.util.Scanner;

/**
 * @Author CaesarChang张旭
 * @Date 2021/2/18  12:06 下午
 * @Version 1.0
 */
public class Main {
    public static void main(String[] args) {
        char table[][] = new char[9][9];
        Scanner scanner = new Scanner(System.in);
        for (int i = 0; i < 9; i++) {
            table[i]=scanner.nextLine().toCharArray();
        }

        dfs(table, 0, 0);

    }

    private static void dfs(char[][] table, int x, int y) {

        if (x == 9) {
            printf(table);
            System.exit(0);

        }
        if (table[x][y] == '0') {
            for (int k = 1; k < 10; k++) {
                if (check(table, x, y, k)) {
                    table[x][y]= (char) ('0'+k);
                    dfs(table, x + (y + 1) / 9, (y + 1) % 9);
                }
            }
            table[x][y] = '0';//回溯
        }else{
            dfs(table, x + (y + 1) / 9, (y + 1) % 9);
        }


    }

    private static void printf(char[][] table) {

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {

                System.out.printf("%c",table[i][j]);
            }
            System.out.println();
        }
    }

    private static boolean check(char[][] table, int i, int j, int k) {
        //检查行 & 列
        for (int l = 0; l < 9; l++) {

                if (table[i][l] == (char)('0' + k)) {
                    return false;
                }
                if (table[l][j] == (char)('0' + k)) {
                    return false;
                }
            }


        //检查小矩形
        for (int l = (i / 3) * 3; l < (i / 3 + 1) * 3; l++) {
            for (int m = (j / 3) * 3; m < (j / 3 + 1) * 3; m++) {
                if (table[l][m] == (char)('0' + k)) {
                    return false;
                }
            }
        }
        return true;


    }
}