Sudoku

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'
You may assume that there will be only one unique solution.

A sudoku puzzle,

and its solution numbers marked in red.

For the above given diagrams, the corresponding input to your program will be

[[53..7....], [6..195...], [.98....6.], [8...6...3], [4..8.3..1], [7...2...6], [.6....28.], [...419..5], [....8..79]]

and we would expect your program to modify the above array of array of characters to

[[534678912], [672195348], [198342567], [859761423], [426853791], [713924856], [961537284], [287419635], [345286179]]

Method:

Be careful that for one dot, if we exhaust all the options, then we need to return false and go back to previous number.

Solution:

Time: O(n^n)
Space: O(n)

public class Solution {
    public void solveSudoku(ArrayList<ArrayList<Character>> a) {
        solve(a);
    }
    
    private boolean solve(ArrayList<ArrayList<Character>> a) {
        for (int i = 0; i < a.size(); i ++) {
            ArrayList<Character> row = a.get(i);
            for (int j = 0; j < row.size(); j ++) {
                char c = row.get(j);
                if (c == '.') {
                    for (char k = '1'; k <= '9'; k ++) {
                        if (isValid(a, i, j, k)) {
                            row.set(j, k);
                            if (solve(a)) {
                                return true;
                            } else {
                                row.set(j, '.');
                            }
                        }
                    }
                    return false;
                }
            }   
        }
        return true;
    }
    
    private boolean isValid(ArrayList<ArrayList<Character>> board, int x, int y, char val) {
        Set<Character> row = new HashSet<>();
        Set<Character> col = new HashSet<>();
        Set<Character> zone = new HashSet<>();
        row.add(val);
        col.add(val);
        zone.add(val);
        for (int i = 0; i < board.size(); i ++) {
            ArrayList<Character> r = board.get(i);
            for (int j = 0; j < r.size(); j ++) {
                char c = r.get(j);
                if (c == '.') continue;
                if (i == x) {
                    if (!row.add(c)) {
                        return false;
                    }
                }
                if (j == y) {
                    if (!col.add(c)) {
                        return false;
                    }
                }
                if (i / 3 == x / 3 && j / 3 == y / 3) {
                    if (!zone.add(c)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}