import java.util.Arrays;

public class Backtracking_sudoko {
    static boolean isDebugMode = false;
    static int emptyCell = -1;
    static boolean isEndReached = false;


    public static void main(String[] args)
    {
        // 3 x 3 sudoko
//        int[][] multi = new int[][]{
//                { 3, emptyCell, 6 },
//                { 5, 2, emptyCell },
//                { emptyCell, 8, 7 }
//        };

        // 9 x 9 sudoko
        int[][] multi = new int[][]{
                { 3, emptyCell, 6, 5, emptyCell, 8, 4, emptyCell, emptyCell },
                { 5, 2, emptyCell, emptyCell, emptyCell, emptyCell, emptyCell, emptyCell, emptyCell },
                { emptyCell, 8, 7, emptyCell, emptyCell, emptyCell, emptyCell, 3, 1 },

                { emptyCell, emptyCell, 3, emptyCell, 1, emptyCell, emptyCell, 8, emptyCell},
                { 9, emptyCell, emptyCell, 8, 6, 3, emptyCell, emptyCell, 5},
                { emptyCell, 5, emptyCell, emptyCell, 9, emptyCell, 6, emptyCell, emptyCell},

                { 1, 3, emptyCell, emptyCell, emptyCell, emptyCell, 2, 5, emptyCell},
                { emptyCell, emptyCell, emptyCell, emptyCell, emptyCell, emptyCell, emptyCell, 7, 4},
                { emptyCell, emptyCell, 5, 2, emptyCell, 6, 3, emptyCell, emptyCell},
        };

        System.out.println("initial: ");
        print2DArray(multi);

        int[][] multiFilled = backtracking(multi);

        System.out.println("result: ");
        print2DArray(multiFilled);
    }

    private static int[][] backtracking(int[][] ary) {
        int[][] aryFilled = generateDeepCopy2dAry(ary);
        goDown(aryFilled, 0, 0);
        return aryFilled;
    }

    private static void goDown(int[][] multiFilled, int row, int col){
        if (isDebugMode) System.out.printf("[%d, %d]:%d %n", row, col, multiFilled[row][col]);
        // go down to the next empty cell: left -> right , top -> down
        if (multiFilled[row][col] != emptyCell) {
            if ((col + 1)< multiFilled[row].length) {
                col++;
                goDown(multiFilled, row, col);
            } else {
                col = 0;
                if (row + 1 < multiFilled.length) {
                    row++;
                    goDown(multiFilled, row, col);
                } else {
                    // if no more cells to evaluate
                    isEndReached = true; // if we can reach to this point, it means we found "a" solution
                }
            }
            return;
        }

        // found empty cell
        // try 0 ~ 9
        for (int possibleNo = 0; possibleNo <= 9; possibleNo++) {
            multiFilled[row][col] = possibleNo;
            boolean check001 = checkHorizontal(multiFilled, row);
            boolean check002 = checkVertical(multiFilled, col);
            boolean check003 = checkSqure(multiFilled, row, col);

            if (!check001 || !check002 || !check003) {
                multiFilled[row][col] = emptyCell; // restore change
                // if none succeed, we don't need to explore down forward
                continue;
            }else {
                // if all pass, go on to the next empty cell
                goDown(multiFilled, row, col);
                if (isEndReached) return;
            }
        }

    }

    private static boolean checkSqure(int[][] ary, int nowRow, int nowCol) {
        int[] oneToNine = new int[10]; // the first element we won't use
        int row = (nowRow / 3) * 3; // baseline this run
        int col = (nowCol / 3) * 3; // baseline this run

        int row_limit = row + 3;
        int col_limit = col + 3;

        for (int tmpRow = row; tmpRow < row_limit; tmpRow++) {
            for (int tmpCol = col; tmpCol < col_limit; tmpCol++) {
                if (ary[tmpRow][tmpCol] == emptyCell) continue;
                oneToNine[ary[tmpRow][tmpCol]]++;
                if (oneToNine[ary[tmpRow][tmpCol]] == 2) {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean checkHorizontal(int[][] ary, int row) {
        int[] oneToNine = new int[10]; // the first element we won't use
        for (int col = 0 ; col < ary[row].length ; col++){
            if (ary[row][col] == emptyCell) continue;
            oneToNine[ary[row][col]]++;
            if (oneToNine[ary[row][col]] == 2) {
                return false;
            }
        }
        return true;
    }

    private static boolean checkVertical(int[][] ary, int col) {
        int[] oneToNine = new int[10]; // the first element we won't use
        for (int row = 0 ; row < ary.length ; row++){
            if (ary[row][col] == emptyCell) continue;
            oneToNine[ary[row][col]]++;
            if (oneToNine[ary[row][col]] == 2) {
                return false;
            }
        }
        return true;
    }


    ///// Util Only below /////

    public static int[][] generateDeepCopy2dAry(int[][] original) {
        if (original == null) {
            return null;
        }

        final int[][] result = new int[original.length][];
        for (int i = 0; i < original.length; i++) {
            result[i] = Arrays.copyOf(original[i], original[i].length);
            // For Java versions prior to Java 6 use the next:
            // System.arraycopy(original[i], 0, result[i], 0, original[i].length);
        }
        return result;
    }
    private static void print2DArray(int[][] ary){
        for (int i = 0; i < ary.length; i++) {
            for (int j = 0; j < ary[i].length; j++) {
                System.out.printf("%3d" , ary[i][j]);
            }
            System.out.println();
        }
    }
}