Naive java recursion approach


  • 0
    A
    public class Solution {
        
        /**
         * Assumptions:
         * numbers are between 1 and 9
         * there is a solution
         * board is always 9 X 9 fields
         * 
         * approach
         * dfs of solution space
         * backtracking if a change results in an invalid board
         */
        public void solveSudoku(char[][] board) {
            if ( isSolution(board) ) { return; }
            for ( int r = 0; r < 9; r++ ) {
                for ( int c = 0; c < 9; c++ ) {
                    if ( isEmpty(board, r, c) ) {
                        for ( int i = 1; i <= 9; i++ ) {
                            board[r][c] = Character.forDigit(i, 10);
                            if ( isValidRow(board, r) && isValidCol(board, c) && isValidBlock(board, r, c) ) {
                                solveSudoku(board);
                                if ( isSolution(board) ) { return; }
                            }
                        }
                        board[r][c] = '.';
                        return;
                    }
                }
            }
        }
    
        private static boolean isEmpty(char[][] board, int r, int c) {
            return board[r][c] == '.';
        }
        
        static boolean isSolution(char[][] board) {
            for ( int r = 0; r < 9; r++ ) 
                if ( !isCompleteRow(board, r) || !isValidRow(board, r) ) return false;
            for ( int c = 0; c < 9; c++ ) 
                if ( !isValidCol(board, c) ) return false;
            for ( int i = 0; i < 9; i = i + 3 ) 
                for ( int j = 0; j < 9; j = j + 3 ) 
                    if ( !isValidBlock(board, i, j) ) return false;
            return true;
        }
    
        private static boolean isCompleteRow(char[][] board, int r) {
          for ( int c = 0; c < 9; c++ ) {
            if ( board[r][c] == '.' ) { return false; }
          }
          return true;
        }
    
        private static boolean isValidBlock(char[][] board, int i, int j) {
            i = i / 3;
            j = j / 3;
            BitSet nums = new BitSet();
            for ( int r = i * 3, n = r + 3; r < n ; r++ ) 
                for ( int c = j * 3, m = c + 3; c < m ; c++ ) {
                    if ( !isEmpty(board, r, c) ) {
                        if ( nums.get(board[r][c] - '0') ) return false;
                        nums.set(board[r][c] - '0');
                    }
                }
            return true;
        }
        
        static boolean isValidRow(char[][] board, int r) {
            BitSet nums = new BitSet();
            for ( int c = 0; c < 9; c++ ) {
                if ( !isEmpty(board, r, c) ) {
                    if ( nums.get(board[r][c] - '0') ) return false;
                    nums.set(board[r][c] - '0');
                }
            }
            return true;
        }
    
        static boolean isValidCol(char[][] board, int c) {
            BitSet nums = new BitSet();
            for ( int r = 0; r < 9; r++ ) {
                if ( !isEmpty(board, r, c) ) {
                    if ( nums.get(board[r][c] - '0') ) return false;
                    nums.set(board[r][c] - '0');
                }
            }
            return true;
        }
    }

Log in to reply
 

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