My easily understood solution using simple DFS and pre-process


  • 0
    A

    Note: The tricky part of this problem is the pre-process part not the DFS part

    public class Solution {
            public void solveSudoku(char[][] board) {
                if (board == null || board.length != 9 || board[0].length != 9) {
                	return;
                }
                
                Map<Integer, Set<Character>> map = preProcess(board);
                
                dfs(board, 0, map);
            }
        	
        	private boolean dfs(char[][] board, int steps, Map<Integer, Set<Character>> map) {
        		if (steps == 81) {
        			return true;   // finish traversing, we have got the correct answer
        		}
        		
        		int rowIdx = steps / 9;
        		int colIdx = steps % 9;
        		
        		if (board[rowIdx][colIdx] != '.') {
        			return dfs(board, steps + 1, map);   // search in one step further
        		}
        		
        		Set<Character> allPossibleNums = map.get(getKey(rowIdx, colIdx));
        		for (char number : allPossibleNums) {
        			if (isValid(board, rowIdx, colIdx, number)) {
        				board[rowIdx][colIdx] = number;
        				if (dfs(board, steps + 1, map)) {
        					return true;
        				} else {
        					board[rowIdx][colIdx] = '.';   // reset this slot for other tries
        				}
        			}
        		}
        		
        		return false;
        	}
        	
        	/**
        	 * to check if it is valid to set this slot to be this number
        	 * @param board
        	 * @param rowIdx - the row index of this slot
        	 * @param colIdx - the column index of this slot
        	 * @param number - the checked number
        	 * @return
        	 */
        	private boolean isValid(char[][] board, int rowIdx, int colIdx, char number) {
        		// check the same row
        		for (int i = 0; i < 9; i++) {
        			if (board[rowIdx][i] == number) {
        				return false;
        			}
        		}
        		
        		// check the same column
        		for (int i = 0; i < 9; i++) {
        			if (board[i][colIdx] == number) {
        				return false;
        			}
        		}
        		
        		// check the same block
        		int startRowIdx = rowIdx / 3 * 3;
        		int startColIdx = colIdx / 3 * 3;
        		int endRowIdx = startRowIdx + 3;
        		int endColIdx = startColIdx + 3;
        		
        		for (int i = startRowIdx; i < endRowIdx; i++) {
        			for (int j = startColIdx; j < endColIdx; j++) {
        				if (board[i][j] == number) {
        					return false;
        				}
        			}
        		}
        		
        		return true;
        	}
        	
        	/**
        	 * return a map to record what numbers can be set for a specific slot at row i column j
        	 * @param board
        	 * @return
        	 */
        	private Map<Integer, Set<Character>> preProcess(char[][] board) {
        		List<Set<Character>> rowSet = new ArrayList<>(9); // store all pre-filled numbers for each row
        		List<Set<Character>> colSet = new ArrayList<>(9); // store all pre-filled numbers for each column
        		List<Set<Character>> blockSet = new ArrayList<>(9); // store all pre-filled numbers for each block
        		
        		// initialize row set
        		for (int row = 0; row < 9; row++) {
        			Set<Character> set = new HashSet<>();
        			for (char c : board[row]) {
        				if (c != '.') {
        					set.add(c);
        				}
        			}
        			rowSet.add(set);
        		}
        		
        		// initialize column set
        		for (int col = 0; col < 9; col++) {
        			Set<Character> set = new HashSet<>();
        			for (int row = 0; row < 9; row++) {
        				if (board[row][col] != '.') {
        					set.add(board[row][col]);
        				}
        			}
        			colSet.add(set);
        		}
        		
        		// initialize block set
        		for (int block = 0; block < 9; block++) {
        			int startRowIdx = block / 3 * 3;
        			int endRowIdx = startRowIdx + 3;
        			int startColIdx = block % 3 * 3;
        			int endColIdx = startColIdx + 3;
        			Set<Character> set = new HashSet<>();
        			
        			for (int row = startRowIdx; row < endRowIdx; row++) {
        				for (int col = startColIdx; col < endColIdx; col++) {
        					if (board[row][col] != '.') {
        						set.add(board[row][col]);
        					}
        				}
        			}
        			blockSet.add(set);
        		}
        		
        		Map<Integer, Set<Character>> map = new HashMap<>();
        		for (int row = 0; row < 9; row++) {
        			for (int col = 0; col < 9; col++) {
        				if (board[row][col] == '.') {
        					for (char c = '1'; c <= '9'; c++) {
        						if (!rowSet.get(row).contains(c) 
        								&& !colSet.get(col).contains(c) 
        								&& !blockSet.get(getBlockIdx(row, col)).contains(c)) {
        							int key = getKey(row, col);
        							Set<Character> s = map.get(key);
        							if (s == null) {
        								s = new HashSet<>();
        								s.add(c);
        								map.put(key, s);
        							} else {
        								s.add(c);
        							}
        						}
        					}
        				}
        			}
        		}
        		
        		return Collections.unmodifiableMap(map);
        	}
        	
        	private int getBlockIdx(int row, int col) {
        		return (row / 3) * 3 + col / 3;
        	}
        	
        	private int getKey(int row, int col) {
        		return row + 33 * col;
        	}
        }

Log in to reply
 

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