Very Readable DFS Java Solution


  • 0
    S

    DFS with back trace, use a global var boolean found to end the recursion.

    public class Solution {
        boolean found;
        public void solveSudoku(char[][] board) {
            found = false;
            dfs(board, 0, 0);
        }
        
        private void dfs(char[][] board, int x, int y){
            // position correction
            if(x==9){
                x = 0;
                y = y + 1;
            }
            
            // base case
            if(y==9) {found = true;return;}
            
            // recursion
            if(board[x][y]!='.'){
                dfs(board, x+1, y);
            }else{
                List<Integer> list = validNum(board, x, y);
                for(int i = 0;i < list.size();i++){
                    board[x][y] = (char)('0' + list.get(i));
                    dfs(board, x+1, y);
                    if(found) return;
                    board[x][y] = '.';
                }
            }
        }
        
        private List<Integer> validNum(char[][] board, int x, int y){
            List<Integer> list = new ArrayList<Integer>();
            int center_x = x/3 * 3 + 1;
            int center_y = y/3 * 3 + 1;
            boolean[] engaged = new boolean[9];
            for(int i = -1;i <= 1;i++)
                for(int j = -1;j <= 1;j++)
                    if(board[center_x+i][center_y+j]!='.')
                        engaged[(int)(board[center_x+i][center_y+j]-'1')] = true;
            for(int i = 0;i < 9;i++)
                if(board[i][y]!='.') engaged[(int)(board[i][y] - '1')] = true;
            for(int j = 0;j < 9;j++)
                if(board[x][j]!='.') engaged[(int)(board[x][j] - '1')] = true;
            for(int i = 0;i < engaged.length;i++)
                if(!engaged[i]) list.add(i+1);
            return list;
        }
    }

Log in to reply
 

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