My clean java code in 54 lines


  • 0
    S

    public class Solution {
    Map<Integer, Set<Character>> rows = new HashMap<Integer, Set<Character>>(),
    columns = new HashMap<Integer, Set<Character>>(),
    cubes = new HashMap<Integer, Set<Character>>();
    Set<Character> init_set = new HashSet<Character>(Arrays.asList(new Character[]{'1','2','3','4','5','6','7','8','9'}));

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; ++i) {
            Set<Character> row = new HashSet<Character>(init_set), 
                column = new HashSet<Character>(init_set),
                cube = new HashSet<Character>(init_set);
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.')
                    row.remove(board[i][j]);
                if (board[j][i] != '.')
                    column.remove(board[j][i]);
                int a = 3 * (i / 3), b = 3 * (i % 3);
                int c = j / 3, d = j % 3;
                if (board[a + c][b + d] != '.')
                    cube.remove(board[a + c][b + d]);
            }
            rows.put(i, row);
            columns.put(i, column);
            cubes.put(i, cube);
        }
        dfs(board, 0, 0);
    }
    
    public boolean dfs(char[][] board, int i, int j) {
        if (i == 9)
            return true;
        int next_i = i, next_j = j;
        if (j == 8) {
            next_i = i + 1; next_j = 0;
        }
        else {
            next_j += 1;
        }
        if (board[i][j] != '.') {
            return dfs(board, next_i, next_j);
        }
        else {
            Set<Character> r = rows.get(i), c = columns.get(j),
                cube = cubes.get(3 * (i / 3) + j / 3);
            Set<Character> tmp = new HashSet<Character>(init_set);
            tmp.retainAll(r); tmp.retainAll(c); tmp.retainAll(cube);
            for (Character candi: tmp) {
                board[i][j] = candi; r.remove(candi); c.remove(candi); cube.remove(candi);
                if (dfs(board, next_i, next_j))
                    return true;
                board[i][j] = '.'; r.add(candi); c.add(candi); cube.add(candi);
            }
            return false;
        }
    }
    

    }


  • 0
    T

    What is the runtime?
    And how is the runtime is measured anyway? It is something that is dependent on underlying hardware and OS and jvm etc.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.