Sudoku

import java.util.*;

public class Main {
    public static Stack<Integer> stackI = new Stack<>();
    public static Stack<Integer> stackJ = new Stack<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[][] data = new int[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                data[i][j] = sc.nextInt();
            }
        }
        sudu(data);
        for (int[] datum : data) {
            for (int d : datum) {
                System.out.print(d + " ");
            }
            System.out.println();
        }
    }

    private static void sudu(int[][] data) {
        // 回溯法求解
        Map<Integer, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < 9; i++) {
            map.put(i, 0);
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (data[i][j] == 0) {
                    map.put(i, map.get(i) + 1);
                }
            }
        }
        List<String> strTmp = new ArrayList<>();
        map.entrySet().stream().sorted(Map.Entry.comparingByValue()).forEach(v -> strTmp.add(v.toString()));
        map.clear();
        for (int i = 0; i < 9; i++) {
            String[] str_s = strTmp.get(i).split("=");
            map.put(Integer.parseInt(str_s[0]), Integer.parseInt(str_s[1]));
        }

        for (Integer i : map.keySet()) {
            for (int j = 0; j < 9; j++) {
                if (data[i][j] == 0) {
                    addData(data, i, j, 1);
                }
            }
        }
    }

    private static void addData(int[][] data, int i, int j, int k) {
        if (k > 9) {
            int ITmp = stackI.pop();
            int JTmp = stackJ.pop();
            int kTmp = data[ITmp][JTmp] + 1;
            data[ITmp][JTmp] = 0;
            data[i][j] = 0;
            addData(data, ITmp, JTmp, kTmp);
            addData(data, i, j, 1);
            return;
        }
        boolean flag = true;
        for (; k <= 9; k++) {
            data[i][j] = k;
            if (checkisOK(data, i, j)) {
                stackI.push(i);
                stackJ.push(j);
                flag = false;
                break;
            }
        }
        if (flag) { // i， j 插不进去 ，出栈
            int ITmp = stackI.pop();
            int JTmp = stackJ.pop();
            int kTmp = data[ITmp][JTmp] + 1;
            data[ITmp][JTmp] = 0;
            data[i][j] = 0;
            addData(data, ITmp, JTmp, kTmp);
            addData(data, i, j, 1);
        }
    }
    
    // 判断行、列、块是否满足插入
    private static boolean checkisOK(int[][] data, int i, int j) {
        for (int k = 0; k < 9; k++) {
            if (k != j && data[i][j] == data[i][k]) {
                return false;
            }
            if (k != i && data[i][j] == data[k][j]) {
                return false;
            }
        }

        int row = i / 3 * 3;
        int col = j / 3 * 3;
        for (int k = row; k < row + 3; k++) {
            for (int l = col; l < col + 3; l++) {
                if (k == i && l == j) {
                    continue;
                }
                if (data[k][l] == data[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
          Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int[][] db = new int[10][10];//保存原始数据
            List<int[]> arr = new ArrayList<>();//记录0元素的位置 
            for (int i = 1; i <= 9; i++) {
                for (int j = 1; j <= 9; j++) {
                    db[i][j] = in.nextInt();
                    if ( db[i][j] == 0){
                        arr.add(new int[]{i,j});
                    }
                }
            }

            dfs(arr, db);
            //打印
            for (int i = 1; i <= 9; i++) {
                for (int j = 1; j <= 9; j++) {
                    System.out.print(db[i][j]+" ");
                }
                System.out.println();
            }
        }
    }
     private static boolean dfs(List<int[]> arr, int[][] db) {
        for (int j = 0; j < arr.size(); j++) {
            int hang = arr.get(j)[0];
            int lie =arr.get(j)[1];
            //1-9去计算是否符合
            for (int i = 1; i <= 9; i++) {
                if (check(db, hang, lie,i)){
                    db[hang][lie] = i;
                    List<int[]> temp = new ArrayList<>();
                    temp.addAll(arr);
                    temp.remove(j);
                    if (dfs(temp,db)){
                        return true;
                    }else {
                        db[hang][lie] = 0;//回溯
                    }
                }
            }
            return false;
        }
        return true;
    }
    //行,列,3*3判断
    private static boolean check(int[][] db,int x,int y,int current){
        for (int i = 1; i <= 9; i++) {
            //行
            if (db[x][i] == current)return false;
            //列
            if (db[i][y] == current)return false;
        }
        //3*3   1 4
        int hang = (x-1)/3 *3 +1; //3*3的起始行
        int lie = (y-1)/3 *3 +1; //3*3的起始列
        for (int i = hang; i < hang+3; i++) {
            for (int j = lie; j < lie+3; j++) {
                if (db[i][j] == current){
                    return false;
                }
            }
        }
        return true;
    }

}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        final int N = 9;
        Scanner in = new Scanner(System.in);
        int[][] board = new int[N][N];
        List<int[]> empty = new ArrayList<>();
        boolean[][] rowFlag = new boolean[N][10];
        boolean[][] columnFlag = new boolean[N][10];
        boolean[][][] squareFlag = new boolean[3][3][10];
        int[] done = new int[]{0};

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int value = in.nextInt();
                board[i][j] = value;
                if (value == 0) {
                    empty.add(new int[]{i, j});
                } else {
                    rowFlag[i][value] = true;
                    columnFlag[j][value] = true;
                    squareFlag[i/3][j/3][value] = true;
                }
            }
        }
        in.close();
        dfs(board, empty, rowFlag, columnFlag, squareFlag, 0, done);
    }

    private static void dfs(int[][] board, List<int[]> empty, boolean[][] rowFlag,
                            boolean[][] columnFlag, boolean[][][] squareFlag,
                            int index, int[] done) {
        if (index == empty.size()) {
            done[0] = 1;
            for (int[] arr : board) {
                for (int x : arr) {
                    System.out.print(x + " ");
                }
                System.out.println();
            }
            return;
        }
        int[] arr1 = empty.get(index);
        int x1 = arr1[0], y1 = arr1[1];
        for (int value = 1; value <= 9 && done[0] == 0; value++) {
            if (rowFlag[x1][value] || columnFlag[y1][value]
                    || squareFlag[x1/3][y1/3][value]) {
                continue;
            }
            rowFlag[x1][value] = columnFlag[y1][value] = squareFlag[x1/3][y1/3][value] = true;
            board[x1][y1] = value;
            dfs(board, empty, rowFlag, columnFlag, squareFlag, index+1, done);
            rowFlag[x1][value] = columnFlag[y1][value] = squareFlag[x1/3][y1/3][value] = false;
            board[x1][y1] = 0;
        }
    }
}

import java.util.Scanner;

/**
 * dfs解数独
 * 从左往右，从上往下遍历每个格子
 * 在空格处 循环1-9，检查能不能放，能放->放入，继续递归。不能放->回溯到上一个空格
 * 当最后一行遍历完了，说明格子都填满了，直接结束。
 */
public class Main {
    //定义数独数组，9行9列
    public static int[][] arr = new int[9][9];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            //初始化数独数组
            for (int i = 0;i < 9;i++){
                for (int j = 0; j < 9;j++){
                    arr[i][j] = sc.nextInt();
                }
            }
            //调用dfs方法
            dfs(0,0);
            //打印结果
            for (int i = 0;i < 9;i++){
                for (int j = 0; j < 9;j++){
                    System.out.print(arr[i][j]+" ");
                }
                System.out.println();
            }
        }
    }

    /**
     * dfs填数独
     * @param x 当前的行
     * @param y 当前的列
     * @return
     */
    public static boolean dfs(int x,int y){
        //x的范围是0-8，如果x到9，说明数组已经全填完了，直接结束,返回true
        if (x == 9){
            return true;
        }
        //y的范围是0-8，如果到9，说明当前行已经遍历完所有列了，跳到下一行
        if (y == 9){
            return dfs(x+1,0);
        }
        //当前格子已经填了数字了，跳到下一个格子
        if (arr[x][y] != 0){
            return dfs(x,y+1);
        }
        //走到这一步说明当前这个格子是空的，还要判断一下是否能填数字
        //循环1-9
        for (int i = 1;i <= 9;i++){
            //当前格子能填数字i
            if (check(x,y,i)){
                //填上
                arr[x][y] = i;
                //继续递归，如果能成功，返回true
                if (dfs(x,y+1)){
                    return true;
                }
                //如果走到这一步，说明后面的某个格子填入失败了，回溯到这一步，把当前格子改回空格，继续循环
                arr[x][y] = 0;
            }
        }
        //如果循环完了没有数字能填入，结束当前dfs，返回false
        return false;
    }

    /**
     * 检查当前这个格子能不能填数字num
     * @param x 当前行
     * @param y 当前列
     * @param num 准备填入的数字
     * @return
     */
    public static boolean check(int x ,int y , int num){
        //循环遍历,拿传入的数字与每行，每列比较
        for (int i = 0;i < 9 ;i++){
            //与当前行其他数字比较
            if (arr[x][i] == num){
                return false;
            }
            //与当前列其他数字比较
            if (arr[i][y] == num){
                return false;
            }
        }
        //循环遍历，那传入的数字与每个小九宫格里的数字比较
        for (int i = (x/3)*3;i < (x/3)*3+3 ; i++){
            for (int j = (y/3)*3; j < (y/3)*3+3;j++){
                if (arr[i][j] == num){
                    return false;
                }
            }
        }
        return true;
    }
}

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[][] grid = new int[9][9];
        boolean[][] rowMap = new boolean[9][9];
        boolean[][] colMap = new boolean[9][9];
        boolean[][] gridMap = new boolean[9][9];
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                grid[i][j] = sc.nextInt();
                if(grid[i][j] != 0) {
                    rowMap[i][grid[i][j]-1] = true;
                    colMap[j][grid[i][j]-1] = true;
                    gridMap[(i/3)*3+j/3][grid[i][j]-1] = true;
                }
            }
        }
        dfs(0, 0, grid, rowMap, colMap, gridMap);
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                System.out.print(grid[i][j]);
                if(j != 8)
                    System.out.print(" ");
            }
            System.out.println();
        }
    }
    
    public static boolean dfs(int row, int col, int[][] grid, boolean[][] rowMap, boolean[][] colMap, boolean[][] gridMap) {
        if(row == 9)
            return true;
        if(col == 9)
            return dfs(row+1, 0, grid, rowMap, colMap, gridMap);
        if(grid[row][col] != 0)
            return dfs(row, col+1, grid, rowMap, colMap, gridMap);
        for(int k = 1; k <= 9; k++) {
            if(!rowMap[row][k-1] && !colMap[col][k-1] && !gridMap[(row/3)*3+col/3][k-1]) {
                grid[row][col] = k;
                rowMap[row][k-1] = true;
                colMap[col][k-1] = true;
                gridMap[(row/3)*3+col/3][k-1] = true;
                if(dfs(row, col+1, grid, rowMap, colMap, gridMap))
                    return true;
                grid[row][col] = 0;
                rowMap[row][k-1] = false;
                colMap[col][k-1] = false;
                gridMap[(row/3)*3+col/3][k-1] = false;
            }
        } 
        return false;
    }
}

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Hj44 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            Integer[][] mat = new Integer[9][9];
            for(int i=0;i<9;i++)
                for(int j=0;j<9;j++)
                    mat[i][j] = in.nextInt();
            //更新相关点的信息
            //Integer[][] 第0行是位置 第一行到第四行是 同一行 同一列 同一个方块儿  最后一行是可能的选择
//            System.out.println("Starting...");
            mat = solveFunc(mat);
            printFunc(mat);
        }
    }
    private static Integer[][] solveFunc(Integer[][] mat ) {
        Stack<Integer[][]> matStack = new Stack<>();
        matStack.push(mat);
        int depth = 0;
        while(!matStack.isEmpty()){
            Integer[][] newMat = matStack.pop();
            HashMap<Integer, Integer[][]> connectArray = construct(newMat);
            if (connectArray == null) continue;
            //推理函数
            boolean success = kenanFunc(connectArray, newMat);
            if(!success) continue;
            if(success && isCorrect(newMat)){
                return newMat;
            }
            int minKey = findMin(connectArray);
            if(minKey == -1) continue;
            Integer[] myChoice = connectArray.get(minKey)[4];
            depth += 1;
            for (Integer newChoice:myChoice) {
//                System.out.print("depth is "+ depth);
//                System.out.println(" Position is " + minKey + ",newChoice is " + newChoice);
                matStack.push(copyFunc(newMat, minKey, newChoice));
            }
        }
        return mat;
    }

    private static boolean kenanFunc(HashMap<Integer, Integer[][]> connectArray, Integer[][] mat) {
        //初始化推理
        Iterator<Integer> iterator = connectArray.keySet().iterator();
        while(!connectArray.isEmpty() && iterator.hasNext()){
            Integer nowKey= iterator.next();
            Integer[][] infos = connectArray.get(nowKey);
            Integer[] myChoice = infos[4];
            for (int i = 0; i < 3; i++) {
                replaceFunc(connectArray, nowKey, infos[i+1]);
            }
            if(connectArray.get(nowKey)[4].length==1){
                Integer[] pos = infos[0];
                mat[pos[0]][pos[1]] = infos[4][0];
                removeKey(connectArray,convert(infos[0]));
                iterator = connectArray.keySet().iterator();
            }else if(connectArray.get(nowKey)[4].length==0)
                return false;
            else if((connectArray.get(nowKey)[4].length-1) > connectArray.get(nowKey)[1].length+connectArray.get(nowKey)[2].length+connectArray.get(nowKey)[3].length)
                return false;
        }
        return true;
    }

    private static Integer[][] copyFunc(Integer[][] mat, Integer minKey, Integer newChoice) {
        Integer[][] newMat = new Integer[9][9];
        for (int d = 0; d < mat.length; d++) {
            newMat[d] = Arrays.copyOf(mat[d], 9);
        }
        int[] tempPos = convert(minKey);
        newMat[tempPos[0]][tempPos[1]] = newChoice.intValue();
        return newMat;
    }

    private static boolean isCorrect(Integer[][] mat) {
        if(haveZero(mat))
            return false;
        //某列的元素
        HashSet<Integer> integers = new HashSet();
        for (int i = 0; i < mat.length; i++) {
            integers.addAll(Arrays.asList(mat[i]));
            if(integers.size()!=9)
                return false;
            else
                integers.clear();
        }
        //某列的元素
        for (int j = 0; j < mat[0].length; j++) {
            for (int i = 0; i < mat.length; i++) {
                integers.add(mat[i][j]);
            }
            if(integers.size()!=9)
                return false;
            else
                integers.clear();
        }
        integers.clear();
        //某个方块的元素
        for (int xSec = 0; xSec < 3; xSec++) {
            for (int ySec = 0; ySec < 3; ySec++) {
                int [] sec1 = {0,1,2,9,10,11,18,19,20};
                for (int d = 0; d < sec1.length;d++){
                    sec1[d] = sec1[d] + xSec*27 + ySec *3;
                }
                for (int g:sec1) {
                    int[] pos = convert(g);
                    int i = pos[0],j=pos[1];
                    integers.add(mat[i][j]);
                }
                if(integers.size()!=9)
                    return false;
                else
                    integers.clear();
            }
        }
        return true;
    }

    private static void printFunc(Integer[][] mat) {
        //输出结果
        for(int i=0;i<9;i++) {
            System.out.print(mat[i][0]);
            for (int j = 1; j < 9; j++) {
                System.out.print(" ");
                System.out.print(mat[i][j]);
            }
            if(i<8)
                System.out.println("");
        }
    }

    private static void removeKey(HashMap<Integer, Integer[][]> connectArray, Integer myKey) {
        for (int i = 1; i < 4; i++) {
            for(Integer youKey:connectArray.get(myKey)[i]){
                Integer[][] tempHash = connectArray.get(youKey);
                ArrayList<Integer> temp = new ArrayList(Arrays.asList(tempHash[i]));
                if(temp.contains(myKey)){
                    temp.remove(myKey);
                    tempHash[i] =temp.toArray(new Integer[temp.size()]);
                    connectArray.put(youKey, tempHash);
                }
            }
        }
        connectArray.remove(myKey);
    }


    public static HashMap<Integer, Integer[][]> construct(Integer[][] mat){
        HashMap<Integer, Integer[][]> connectArray= new HashMap(128);
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                if(mat[i][j] == 0){
                    Integer[][] t = findInfo(mat, convert(new Integer[]{i,j}));
                    connectArray.put(convert(t[0]), t);
                }
        return connectArray;
    }
    public static Integer[][] findInfo(Integer[][] mat, int start){
        ArrayList<Integer> colNeigh = new ArrayList<>();
        ArrayList<Integer> rowNeigh = new ArrayList<>();
        ArrayList<Integer> sqaureNeigh = new ArrayList<>();
        HashSet<Integer> pValues = new HashSet();
        pValues.addAll(Arrays.asList(new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9}));
        int[] point = convert(start);
        int x = point[0], y = point[1];
        //一行的零点
        for(int i = x, j = 0;j<9;j++){
            if(mat[i][j] == 0 && j!=y){
                colNeigh.add(convert(new Integer[]{i,j}));
            }else if(pValues.contains(mat[i][j])){
                pValues.remove(mat[i][j]);
            }
        }
        //一列的元素
        for(int i = 0, j = y;i<9;i++){
            if(mat[i][j] == 0 && i!=x){
                rowNeigh.add(convert(new Integer[]{i,j}));
            }else if(pValues.contains(mat[i][j])){
                pValues.remove(mat[i][j]);
            }
        }
        //一个方块的元素
        int xSec = point[0]/3, ySec = point[1]/3;
        int [] sec1 = {0,1,2,9,10,11,18,19,20};
        for (int d = 0; d < sec1.length;d++){
            sec1[d] = sec1[d] + xSec*27 + ySec *3;
        }
        for (int g:sec1) {
            int[] pos = convert(g);
            int i = pos[0],j=pos[1];
            if(mat[i][j] == 0 && !(i == x && j == y)){
                sqaureNeigh.add(g);
            }else if(pValues.contains(mat[i][j])){
                pValues.remove(mat[i][j]);
            }
        }
        //加入HashMap中
        Integer[][] info = new Integer[5][];
        info[0] = new Integer[]{x,y};
        info[1] = rowNeigh.toArray(new Integer[rowNeigh.size()]);
        info[2] = colNeigh.toArray(new Integer[colNeigh.size()]);
        info[3] = sqaureNeigh.toArray(new Integer[sqaureNeigh.size()]);
        info[4] = pValues.toArray(new Integer[pValues.size()]);
        return info;
    }
    public static int findMin(HashMap<Integer, Integer[][]>connectArray){
        int minKey = -1;
        int minValue = Integer.MAX_VALUE;
        for (Integer key:connectArray.keySet()) {
            if(connectArray.get(key)[4].length<minValue){
                minValue = connectArray.get(key)[4].length;
                minKey = key;
            }
        }
        return minKey;
    }
    public static void replaceFunc(HashMap<Integer, Integer[][]>connectArray, Integer myKey, Integer[] infosn) {
        int flagPosCount = 1;
        //一行的邻居
        Integer[] myChoice = connectArray.get(myKey)[4];
        for(Integer youKey: infosn){
            Integer[] yourChoice = connectArray.get(youKey)[4];
            if(Arrays.equals(myChoice, yourChoice)) {
                flagPosCount++;
            }
        }
        if(flagPosCount==myChoice.length){
            for(Integer you: infosn){
                Integer[] yourChoice = connectArray.get(you)[4];
                if(! Arrays.equals(myChoice, yourChoice)){
                    Integer[] yourChoiceAlter = alterFunc(yourChoice,myChoice);
                    Integer[][] temp = connectArray.get(you);
                    temp[4] = yourChoiceAlter;
                    connectArray.replace(you, temp);
                }
            }
        }
    }
    public static Integer[] alterFunc(Integer[] more, Integer[] less) {
        HashSet<Integer> temp = new HashSet();
        temp.addAll(Arrays.asList(more));
        for (Integer i: less)
            if(temp.contains(i))
                temp.remove(i);
        return temp.toArray(new Integer[temp.size()]);
    }
    private static boolean haveZero(Integer[][] newMat) {
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                if(newMat[i][j] == 0){
                    return true;
                }
        return false;
    }
    public static int[] convert(Integer i) {
        return new int[]{i/9, i%9};
    }
    public static int convert(Integer[] a) {
        return a[0]*9 + a[1];
    }

}

import java.util.*;
public class Main {
    static int[][] grid;
    static boolean[][] rows, cols;
    static boolean[][][] cell;
    static boolean dfs(int x, int y) {
        if(y == 9) {
            x ++; y = 0;
        }
        if(x == 9) return true;
        if(grid[x][y] != 0) 
            return dfs(x,y+1);
        for(int i=0; i < 9; i++) {
            if(!rows[x][i] && !cols[y][i] && !cell[x/3][y/3][i]) {
                grid[x][y] = i+1;
                rows[x][i] = cols[y][i] = cell[x/3][y/3][i] = true;
                if(dfs(x, y+1)) return true;
                rows[x][i] = cols[y][i] = cell[x/3][y/3][i] = false;
                grid[x][y] = 0;
            }
        }
        return false;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = 9;
            grid = new int[n][n];
            rows = new boolean[n][n];
            cols = new boolean[n][n];
            cell = new boolean[3][3][n];
            for(int i=0; i < n; i++)
                for(int j=0; j < n; j++) {
                    grid[i][j] = sc.nextInt();
                    if(grid[i][j] != 0) {
                        int u = grid[i][j] - 1;
                        rows[i][u] = cols[j][u] = cell[i/3][j/3][u] = true;
                    }
                }
            dfs(0, 0);
            for(int i=0; i < n; i++) {
                for(int j=0; j < n-1; j++)
                    System.out.print(grid[i][j] + " ");
                System.out.println(grid[i][n-1]);
            }
        }
    }
}