An organized Java recursive solution, 87%

  • 0

    Code is a bit long due to declaring multiple functions. Runtime is mediocre, 87%. However I think it should be easy for everyone to understand since every action is put into different functions.

    Feel free to make it more concise yet still understandable! I know there are geniuses who already post awesome code on this discussion thread. If you want faster version, plz refer to other threads like this. :)


    import java.util.TreeSet;
    public class Solution {
        boolean[][] rowCount, colCount, zoneCount;  // record the status of every row, col and zone
        public void solveSudoku(char[][] board) {
            rowCount = new boolean[9][9];
            colCount = new boolean[9][9];
            zoneCount = new boolean[9][9];
            solveSudoku(board, 0, 0);
        private boolean solveSudoku(char[][] board, int row, int col){
            Pair<Integer, Integer> next = generateNextRowCol(row, col);;
            if(row==-1 || col==-1) return true;
            if(board[row][col]!='.'){   // given by the problem. We can't change it
                return solveSudoku(board, next.first, next.second);
            }else{  // we keep changing this to find the answer
                for(int i='1'; i<='9'; i++){
                    if(checkRepeat(row, col, i-'1')) continue;
                    toggleCount(row, col, i-'1');
                    board[row][col] = (char)i;
                    if(solveSudoku(board, next.first, next.second)) return true;    // so that we can preserve board status
                    toggleCount(row, col, i-'1');
                board[row][col] = '.';
                return false;
        private void toggleCount(int row, int col, int num){
            // use this we set or unset all the count related to the row & col & zone
            rowCount[row][num] = !rowCount[row][num];
            colCount[col][num] = !colCount[col][num];
            zoneCount[(row/3)*3+col/3][num] = !zoneCount[(row/3)*3+col/3][num];
        private boolean checkRepeat(int row, int col, int num){
            // based on row & col, we know which zone we are going to check
            // 0 1 2
            // 3 4 5
            // 6 7 8
                    || colCount[col][num]
                    || zoneCount[(row/3)*3+col/3][num]) return true;
            return false;
        private void initVariables(char[][] board){
            // set row & colCount first to facilitate the speed.
            for(int row=0; row<board.length; row++){
                for(int col=0; col<board[row].length; col++){
                        int num = board[row][col]-'1';
        private Pair<Integer, Integer> generateNextRowCol(int row, int col){
            else col++;
            if(row>8) return new Pair<>(-1, -1);
            return new Pair<>(row, col);
    class Pair<K, V>{
        public K first;
        public V second;
        public Pair(){};
        public Pair(K f, V s){
            first = f;
            second = s;

Log in to reply

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