Java Solution


  • 0
    Y
    public class SudokuSolver {
        private final static Set<Character> CANDIDATES = new HashSet<>(Arrays.asList('1', '2', '3', '4', '5', '6', '7', '8', '9'));
        private final static char MISSED = '.';
    
        public void solveSudoku(char[][] board) {
            fill(board);
        }
    
        private void fill(char[][] board) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == MISSED) {
                        Set<Character> candidates = possible(board, i, j);
                        for (char candidate : candidates) {
                            board[i][j] = candidate;
                            fill(board);
                            if (isFilled(board)) {
                                return;
                            }
                        }
                        board[i][j] = MISSED;
                        return;
                    }
                }
            }
        }
    
        private Set<Character> possible(char[][] board, int y, int x) {
            Set<Character> candidates = new HashSet<>(CANDIDATES);
            for (int i = 0; i < 9; i++) {
                candidates.remove(board[y][i]);
                candidates.remove(board[i][x]);
            }
            return candidates;
        }
    
        private boolean isFilled(char[][] board) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == MISSED) {
                        return false;
                    }
                }
            }
            return true;
        }
    }
    

Log in to reply
 

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