package il.ac.tau.cs.franji;


/**
 * Created by talfranji on 30/03/2020.
 */
public class Main {
    static final String game =
            " _ _ 4  _ _ _  _ 5 7 " +
                    " 2 _ _  _ _ _  8 _ _ " +
                    " 3 9 _  5 _ _  _ _ 6" +

                    " _ 1 _  4 7 5  9 _ _" +
                    " _ _ _  _ 3 _  _ _ _" +
                    " _ _ 5  2 1 8  _ 3 _" +

                    " 7 _ _  _ _ 9  _ 4 8" +
                    " _ _ 9  _ _ _  _ _ 3" +
                    " 1 8 _  _ _ _  2 _ _";

    static final String gameTest =
            "_ 2 3  4 5 6  7 8 9\n" +
                    "_ 5 _  _ _ _  _ _ _\n" +
                    "_ 6 _  _ _ _  _ _ _\n" +
                    "\n" +
                    "_ 3 _  _ _ _  _ _ _\n" +
                    "_ 4 _  _ _ _  _ _ _\n" +
                    "_ 7 _  _ _ _  _ _ _\n" +
                    "\n" +
                    "_ 8 _  _ _ _  2 3 4\n" +
                    "_ 9 _  _ _ _  5 6 7\n" +
                    "_ _ _  _ _ _  8 9 _\n";

    static int[][][] BoardFromInput(String game) {
        int[][][] res = new int[9][][];
        int x = 0;
        int y = 0;
        for(char ch :game.toCharArray()) {
            int[] item = null;
            if (Character.isDigit(ch)) {
                // constatnt cell
                item = new int[]{1, Character.getNumericValue(ch)};
            } else if (ch == '_') {
                item = new int[]{0, -1};  // empty cell
            } else {
                // not a digit and not empty cell.
                continue;
            }

            if (res[y] == null) {
                res[y] = new int[9][];  // start new line
            }
            res[y][x] = item;
            x += 1;
            if (x >= 9) {
                y += 1;
                x = 0;
            }
            if (y >= 9) {
                break;  //exit even if mnore chars in string
            }
        }
        return res;
    }
    static String repeat(String s, int n) {
        String res = "";
        for (int i = 0; i < n; i++) {
            res += s;
        }
        return res;
    }

    static void PrintBoard(int[][][] board) {
        int y = -1; //line index
        for (int[][] line : board) {
            y += 1;
            if (y % 3 == 0) {
                System.out.println(repeat("-",37));
            }
            int x = -1;
            for (int[] item : line) {
                x += 1;
                if (x % 3 == 0) {
                    System.out.print(" | ");
                }
                if (item[1] >= 0) {
                    System.out.format("%2d ", item[1]);
                } else {
                    System.out.print(" _ ");
                }
            }
            System.out.println("");  // end of line
        }
        System.out.println(repeat("=",37));
    }


    static boolean inLine(int n, int[][][] board, int line) {
        for(int[] item: board[line]) {
            if (n == item[1]) {
                return true;
            }
        }
        return false;
    }

    static boolean inCol(int n, int[][][] board, int col) {
        for(int[][] line: board) {
            if (n == line[col][1]) {
                return true;
            }
        }
        return false;
    }

    static boolean inSq(int n, int[][][] board, int line, int col) {
        int sqY = line / 3;
        int sqX = col / 3;
        for(int l = sqY * 3; l < sqY * 3 + 3; l++) {
            for (int c = sqX * 3; c < sqX * 3 + 3; c++) {
                if (n == board[l][c][1]) {
                    return true;
                }
            }
        }
        return false;
    }



    static boolean Solve(int[][][] board, int i) {
        PrintBoard(board);
        if (i >= 9 * 9) {
            return true;
        }
        int line = i / 9;
        int col = i % 9;
        if (board[line][col][0] == 1) {
            return Solve(board, i + 1);
        }
        for (int n = 1; n <= 9; n++) {
            board[line][col][1] = -1;
            boolean line_bad = inLine(n, board, line);
            boolean row_bad = inCol(n, board, col);
            boolean sq_bad = inSq(n, board, line, col);
            if (line_bad || row_bad || sq_bad) {
                continue;
            }
            board[line][col][1] = n;
            if (Solve(board, i + 1)) {
                return true;
            }
            board[line][col][1] = -1;  // restore
        }
        return false;
    }



    static void test() {
        // assert need VM option -ea in Run configurations
        int[][][] board = BoardFromInput(gameTest);
        assert inLine(2, board, 0);
        assert !inLine(1, board, 0);
        assert inCol(2, board, 1);
        assert !inCol(1, board, 1);
        assert inSq(2, board, 8, 8);
        assert !inSq(1, board, 8, 8);
    }


    public static void main(String[] args) {
        int[][][] board = BoardFromInput(game);
        PrintBoard(board);
        Solve(board, 0);
        //test();
    }


}