Share my Java Solution using Sets to check duplicates


  • 0
    M
            public void solveSudoku(char[][] board) {
    		if (board == null || board.length == 0) return;
    		int m = board.length, n = board[0].length;
    		if (m != 9 || n != 9 || m != n) return;
    		List<Set<Character>> row = new ArrayList<>(), col = new ArrayList<>(), block = new ArrayList<>();
    		for (int i = 0; i < n; ++i) {
    			row.add(new HashSet<Character>());
    			col.add(new HashSet<Character>());
    			block.add(new HashSet<Character>());
    		}
    		for (int i = 0; i < m; ++i) {
    			for (int j = 0; j < n; ++j) {
    				if (board[i][j] != '.') {
    					row.get(i).add(board[i][j]);
    					col.get(j).add(board[i][j]);
    					block.get(i / 3 * 3 + j / 3).add(board[i][j]);
    				}
    			}
    		}
    		solve(board, 0, 0, row, col, block);
    	}
    	private boolean solve(char[][] board, int i, int j, List<Set<Character>> row, List<Set<Character>> col, List<Set<Character>> block) {
    		if (j >= board[0].length) {
    			++i;
    			j = 0;
    		}
    		if (i >= board.length) return true;
    		if (board[i][j] != '.') {
    			return solve(board, i, j + 1, row, col, block);
    		}
    		for (char c = '1'; c <= '9'; ++c) {
    			if (row.get(i).contains(c) || col.get(j).contains(c) || block.get(i / 3 * 3 + j / 3).contains(c)) continue;
    			row.get(i).add(c);
    			col.get(j).add(c);
    			block.get(i / 3 * 3 + j / 3).add(c);
    			board[i][j] = c;
    			if (solve(board, i, j + 1, row, col, block)) return true;
    			block.get(i / 3 * 3 + j / 3).remove(c);
    			col.get(j).remove(c);
    			row.get(i).remove(c);
    		}
    		board[i][j] = '.';
    		return false;
    	}
    

Log in to reply
 

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