class Solution {

        boolean flag;

        public void solveSudoku(char[][] board) {

                flag = false;                   // flag = true denotes that a sudoku is solved.
                logic(board, 0, 0);
                for (char val[]: board)
                                System.out.println(Arrays.toString(val));
                        
        }

        public void logic(char board[][], int cr, int cc) { // cr denotes current row, cc denotes current column

                 if (flag)              // if sudoku is solved then no need for futher recursion, and altering contents of the board
                        return;

                if (cr >= 9) {
                        flag = true; // flag = true will indicate that a solution was found, and since unique solution is guranteed, therefore board[][] is a valid solved sudoku rightnow.
                        return;
                }

                int ni = 0; // ni denotes new i that is new value of row for next recursive call
                int nj = 0; // nj denotes new j that is new value of column for next recursive call

                if (cc == 8) {
                        ni = cr + 1;
                        nj = 0;
                } else {
                        ni = cr;
                        nj = cc + 1;
                }

                if (board[cr][cc] != '.') {

                        logic(board, ni, nj);

                } else if (board[cr][cc] == '.')
                        for (char val = '1'; val <= '9'; ++val) {

                                if (isSafe(board, cr, cc, val)) {

                                        // for (char arr[]: board)
                                        //         System.out.println(Arrays.toString(arr));
                                        // System.out.println();

                                        board[cr][cc] = val;

                                        logic(board, ni, nj);

                                        board[cr][cc] = '.';
                                }
                        }

        }

        public boolean isSafe(char board[][], int row, int col, char val) {

                int i = row;
                int j = col;

                for (j = 0; j < 9; ++j)
                        if (board[row][j] == val)
                                return false;

                i = row;
                j = col;

                for (i = 0; i < 9; ++i)
                        if (board[i][col] == val)
                                return false;

                int corner_i = row / 3 * 3;
                int corner_j = col / 3 * 3;

                for (i = 0; i < 3; ++i)
                        for (j = 0; j < 3; ++j)
                                if (board[corner_i + i][corner_j + j] == val)
                                        return false;

                /*
                // region 9

                if (row > 5) {

                        if (col > 5)
                                for (i = 6; i < 9; ++i)
                                        for (j = 6; j < 9; ++j)
                                                if (board[i][j] == val)
                                                        return false;

                        // region 8

                        if (col > 2)
                                for (i = 3; i < 5; ++i)
                                        for (j = 3; j < 5; ++j)
                                                if (board[i][j] == val)
                                                        return false;

                        // region 7

                        for (i = 0; i < 3; ++i)
                                for (j = 0; j < 3; ++j)
                                        if (board[i][j] == val)
                                                return false;

                }

                // region 6
                else if (row > 2) {

                        if (col > 5)
                                for (i = 3; i < 6; ++i)
                                        for (j = 6; j < 9; ++j)
                                                if (board[i][j] == val)
                                                        return false;

                        // region 5

                        if (col > 2)
                                for (i = 3; i < 6; ++i)
                                        for (j = 3; j < 6; ++j)
                                                if (board[i][j] == val)
                                                        return false;

                        // region 4       
                        for (i = 3; i < 6; ++i)
                                for (j = 0; j < 3; ++j)
                                        if (board[i][j] == val)
                                                return false;

                }

                // region 3
                else {

                        if (col > 5)
                                for (i = 0; i < 3; ++i)
                                        for (j = 6; j < 9; ++j)
                                                if (board[i][j] == val)
                                                        return false;

                        // region 2

                        if (col > 2)
                                for (i = 0; i < 3; ++i)
                                        for (j = 3; j < 6; ++j)
                                                if (board[i][j] == val)
                                                        return false;

                        // region 1

                        for (i = 0; i < 3; ++i)
                                for (j = 0; j < 3; ++j)
                                        if (board[i][j] == val)
                                                return false;

                }
                
                */

                return true;
        }
}