import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Optional;
import java.util.stream.Collectors;


class Solution {
    public void solveSudoku(char[][] board) {
        char[][] x = solve(board);
        for(int i = 0; i < board.length; i++)
            for(int j = 0; j < board[i].length; j++)
                board[i][j] = x[i][j];
    }


    public static char[][] solve(char[][] sudoku) {
        if (isFullFilled(sudoku))
            return sudoku;

        Optional<Cord> cord1 = findEasiestToFulfill(sudoku);
        if (!cord1.isPresent())
            return null;

        Cord cord = cord1.get();
        List<Character> possibleNr = getPossibleNr(sudoku, cord.x, cord.y);
        if (possibleNr.size() == 0)
            return null;

        List<char[][]> collect = possibleNr
                .parallelStream()
                .map(x -> solve(sudoku, cord, x))
                .filter(Objects::nonNull)
                .collect(Collectors.toList());

        if (collect.size() == 0)
            return null;
        else
            return solve(collect.get(0));
    }

    private static char[][] solve(char[][] sudoku, Cord cord, char x) {
        char[][] test = copy(sudoku);
        test[cord.x][cord.y] = x;
        return solve(test);
    }

    private static boolean isFullFilled(char[][] sudoku) {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (sudoku[i][j] == '.')
                    return false;
        return true;
    }

    private static List<Character> getPossibleNr(char[][] sudoku, int x, int y) {
        ArrayList<Character> characters = new ArrayList<>();

        if (isValid(sudoku, '1', x, y))
            characters.add('1');
        if (isValid(sudoku, '2', x, y))
            characters.add('2');
        if (isValid(sudoku, '3', x, y))
            characters.add('3');
        if (isValid(sudoku, '4', x, y))
            characters.add('4');
        if (isValid(sudoku, '5', x, y))
            characters.add('5');
        if (isValid(sudoku, '6', x, y))
            characters.add('6');
        if (isValid(sudoku, '7', x, y))
            characters.add('7');
        if (isValid(sudoku, '8', x, y))
            characters.add('8');
        if (isValid(sudoku, '9', x, y))
            characters.add('9');

        return characters;
    }

    private static char[][] copy(char[][] x) {
        char[][] tab = new char[x.length][x[0].length];
        for (int i = 0; i < x.length; i++)
            System.arraycopy(x[i], 0, tab[i], 0, x[i].length);
        return tab;
    }


    static boolean isValid(char[][] matrix, char value, int actualX, int actualY) {
        int howManyInSquare = howManyUnfilledInSquare(matrix, actualX, actualY, value);
        int howManyInColumn = howManyUnfilledInColumn(matrix, actualY, value);
        int howManyInRow = howManyUnfilledInRow(matrix, actualX, value);

        return howManyInColumn + howManyInRow + howManyInSquare == 0;
    }

    static Optional<Cord> findEasiestToFulfill(char[][] matrix) {
        Optional<Cord> cord = Optional.empty();
        int minUnknown = 21;

        for (int x = 0; x < matrix.length; x++)
            for (int y = 0; y < matrix[x].length; y++) {
                if (matrix[x][y] == '.') {

                    int howManyInSquare = howManyUnfilledInSquare(matrix, x, y, '.');
                    int howManyInColumn = howManyUnfilledInColumn(matrix, y, '.');
                    int howManyInRow = howManyUnfilledInRow(matrix, x, '.');

                    int sum = howManyInColumn + howManyInRow + howManyInSquare - 3;
                    if (minUnknown > sum) {
                        minUnknown = sum;
                        cord = Optional.of(new Cord(x, y));
                    }
                }
            }

        return cord;
    }

    private static int howManyUnfilledInRow(char[][] matrix, int currentX, char value) {
        int unknown = 0;
        for (int y = 0; y < 9; y++)
            if (matrix[currentX][y] == value)
                unknown++;

        return unknown;
    }

    private static int howManyUnfilledInColumn(char[][] matrix, int currentY, char value) {
        int unknown = 0;
        for (int x = 0; x < 9; x++)
            if (matrix[x][currentY] == value)
                unknown++;

        return unknown;
    }

    private static int howManyUnfilledInSquare(char[][] matrix, int currentX, int currentY, char value) {
        if (currentX <= 2 && currentX >= 0 && currentY <= 2 && currentY >= 0)
            return count(matrix, 0, 0, value);

        if (currentX <= 5 && currentX >= 3 && currentY <= 2 && currentY >= 0)
            return count(matrix, 3, 0, value);

        if (currentX <= 8 && currentX >= 6 && currentY <= 2 && currentY >= 0)
            return count(matrix, 6, 0, value);


        if (currentX <= 2 && currentX >= 0 && currentY <= 5 && currentY >= 3)
            return count(matrix, 0, 3, value);

        if (currentX <= 5 && currentX >= 3 && currentY <= 5 && currentY >= 3)
            return count(matrix, 3, 3, value);

        if (currentX <= 8 && currentX >= 6 && currentY <= 5 && currentY >= 3)
            return count(matrix, 6, 3, value);


        if (currentX <= 2 && currentX >= 0 && currentY <= 8 && currentY >= 6)
            return count(matrix, 0, 6, value);

        if (currentX <= 5 && currentX >= 3 && currentY <= 8 && currentY >= 6)
            return count(matrix, 3, 6, value);

        if (currentX <= 8 && currentX >= 6 && currentY <= 8 && currentY >= 6)
            return count(matrix, 6, 6, value);

        return 0;
    }

    private static int count(char[][] matrix, int x, int y, char value) {
        int unknown = 0;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (matrix[(x + i)][y + j] == value)
                    unknown++;

        return unknown;
    }

private static class Cord {

    int x;
    int y;

    Cord(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

}