An organized Java recursive solution, 87%


  • 0
    R

    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. :)

    Cheers!

    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];
            initVariables(board);
            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
            if(rowCount[row][num]
                    || 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++){
                    if(board[row][col]!='.'){
                        int num = board[row][col]-'1';
                        rowCount[row][num]=true;
                        colCount[col][num]=true;
                        zoneCount[(row/3)*3+col/3][num]=true;
                    }
                }
            }
        }
    
        private Pair<Integer, Integer> generateNextRowCol(int row, int col){
            if(col+1>8){
                col=0;
                row++;
            }
            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.