Share my clean solution based on Valid Sudoku


  • 3
    H

    Basically we will stop at each '.' in matrix, then do DFS on it. If none of 1-9 values can meet requirement, then we know above recursion has assigned an inappropriate value, so we will return back and try another
    value in above recursion. Repeat this until we can fill the whole matrix. It is not tricky, just like a brute force or enumerate solution.

    public void solveSudoku(char[][] board) {
        boolean[][] cols = new boolean[9][9];
        boolean[][] rows = new boolean[9][9];
        boolean[][] blocks = new boolean[9][9];
        
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.') continue;
                
                int val = board[i][j] - '0' - 1;
                int k = i/3*3 + j/3;
                
                rows[i][val] = true;
                cols[j][val] = true;
                blocks[k][val] = true;
            }
        }
        
        DFS(board, cols, rows, blocks);
    }
    
    public boolean DFS(char[][] board, boolean[][] cols, boolean[][] rows, boolean[][] blocks){
        
        for(int i = 0; i < 9; i++){
        	for(int j = 0; j < 9; j++){
                if(board[i][j] == '.'){
                	int k = i/3*3 + j/3;
                    for(int l = 0; l < 9; l++){
                        if(!cols[j][l] && !rows[i][l] && !blocks[k][l]){
                            rows[i][l] = cols[j][l] = blocks[k][l] = true;
                            board[i][j] = (char) ('0' + 1 + l);
                            if(DFS(board, cols, rows, blocks)) return true;
                            rows[i][l] = cols[j][l] = blocks[k][l] = false;
                            board[i][j] = '.';                            
                        }
                    }                 
                    return false;
                }        		
        	}
        }
    
    	
        return true;
    }

  • 0
    H

    thanks for your solution. Here I just list my code which makes me a little easier to understand.

    public class Solution {
        public void solveSudoku(char[][] board) {
            boolean[][] cols = new boolean[9][9];
            boolean[][] rows = new boolean[9][9];
            boolean[][] blocks = new boolean[9][9];
            for(int i=0; i<9; i++) {
                for(int j=0; j<9; j++) {
                    if (board[i][j]!='.') {
                        int block = i/3*3+j/3;
                        int value = board[i][j]-'1';
                        rows[i][value] = cols[j][value] = blocks[block][value] = true;
                    }
                }
            }
            dfs(board, 0, rows, cols, blocks);
        }
        private boolean dfs(char[][] board, int pos, boolean[][] rows, boolean[][] cols, boolean[][] blocks){
            if (pos==81) return true;
            int i = pos / 9;
            int j = pos % 9;
            int block = i/3*3+j/3;
            
            if (board[i][j]!='.') return dfs(board, pos+1, rows, cols, blocks);
            
            for(char chr = '1'; chr <= '9'; chr++){
                int num = chr - '1';
                if(!rows[i][num] && !cols[j][num] && !blocks[block][num]){
                    board[i][j] = chr;
                    rows[i][num] = cols[j][num] = blocks[block][num] = true;
                    
                    if(dfs(board, pos + 1, rows, cols, blocks)) return true;
                    
                    board[i][j] = '.';
                    rows[i][num] = cols[j][num] = blocks[block][num] = false;
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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