Valid Sudoku: kiểm tra ràng buộc ba nhóm và pattern canonical-key

Chín hàng, chín cột, chín box 3x3 — và một câu hỏi duy nhất được đặt ra 81 lần: chữ số này đã xuất hiện ở nơi nào đó không được phép chưa? Bài toán không khó về mặt thuật toán. Điều đáng học là cách cấu trúc ràng buộc quyết định implementation. Ngay khi đọc "mỗi hàng, mỗi cột, mỗi box 3x3 không được lặp lại", bạn đã biết cần dùng cấu trúc dữ liệu gì: một cơ chế tracking cho mỗi nhóm, tổng cộng 27 nhóm. Tất cả phần còn lại suy ra từ đó.

Một điểm đề bài dễ bỏ qua: bạn không giải bảng Sudoku. Một bảng điền dở hơi hợp lệ miễn là các ô đã điền không vi phạm quy tắc — kể cả khi không tồn tại cách hoàn thành nào. Chỉ các ô điền ('1' đến '9') được kiểm tra; '.' bị bỏ qua.

Đề bài

Cho một bảng Sudoku 9x9, xác định bảng có hợp lệ không bằng cách kiểm tra rằng mỗi hàng, mỗi cột, và mỗi trong chín ô vuông con 3x3 không chứa chữ số lặp lại từ 1 đến 9 — chỉ các ô đã điền cần được kiểm tra, không cần xét liệu bảng có thể hoàn thành hay không. Đề gốc: LeetCode 36.

Ràng buộc:
- board.length == 9
- board[i].length == 9
- board[i][j] là chữ số 1-9 hoặc '.'.

Kích thước cố định 9x9 có nghĩa gì

Các constraint là board.length == 9, board[i].length == 9, và board[i][j] là chữ số '1'-'9' hoặc '.'. Bảng luôn có đúng 81 ô. Đây không phải bài toán ma trận n x n tổng quát.

Hậu quả thực tế: mọi độ phức tạp O cho bài này về mặt kỹ thuật đều là O(1) vì kích thước đầu vào bị chặn bởi hằng số (81). Khi viết "O(81)" hay "O(27)" dưới đây, đó là dạng trung thực. Tôi vẫn phân tích như thể bảng là n x n để reasoning có thể tổng quát hóa — nhưng đừng để nhãn O(1) đánh lừa bạn nghĩ hai approach không có sự khác biệt thực tế nào.

Bảng chữ số 9 ký tự (hoặc 10 kể cả .) nghĩa là mỗi nhóm chứa tối đa 9 phần tử. Không có nguy cơ overflow, không có nhầm lẫn sentinel. Phần duy nhất không hiển nhiên là công thức box: cho hàng i và cột j, box 3x3 nào chứa ô đó?

box_index = (i // 3) * 3 + (j // 3)

Công thức này ánh xạ chín tổ hợp của (i // 3, j // 3) — mỗi giá trị là 0, 1, hoặc 2 — sang các số nguyên từ 0 đến 8. Viết sai (dùng i // 3 + j // 3 thay vì (i // 3) * 3 + j // 3) và các box 0-8 bị gộp lại thành chỉ số 0-4, âm thầm trộn lẫn các box riêng biệt. Vẽ bảng một lần và kiểm tra:

(0,0)->0  (0,1)->1  (0,2)->2
(1,0)->3  (1,1)->4  (1,2)->5
(2,0)->6  (2,1)->7  (2,2)->8

Đây là phần duy nhất không tự nhiên trong bài. Phần còn lại chỉ là lặp và kiểm tra set membership.

Approach 1: ba lượt riêng biệt

Cách đọc tự nhiên nhất là làm đúng theo đề bài. Chạy ba lần duyệt riêng: một lần cho tất cả hàng, một lần cho tất cả cột, một lần cho chín box. Mỗi lần duyệt tạo một hash set mới, kiểm tra duplicate, rồi bỏ set đó đi trước khi tiếp tục.

class Solution:
    def isValidSudoku(self, board):
        # Kiểm tra tất cả các hàng
        for row in range(9):
            seen = set()
            for col in range(9):
                if board[row][col] != '.':
                    if board[row][col] in seen:
                        return False
                    seen.add(board[row][col])
 
        # Kiểm tra tất cả các cột
        for col in range(9):
            seen = set()
            for row in range(9):
                if board[row][col] != '.':
                    if board[row][col] in seen:
                        return False
                    seen.add(board[row][col])
 
        # Kiểm tra tất cả chín box 3x3
        for box_row in range(3):
            for box_col in range(3):
                seen = set()
                for row in range(box_row * 3, box_row * 3 + 3):
                    for col in range(box_col * 3, box_col * 3 + 3):
                        if board[row][col] != '.':
                            if board[row][col] in seen:
                                return False
                            seen.add(board[row][col])
 
        return True

public class Solution {
    public bool IsValidSudoku(char[][] board) {
        // Kiểm tra tất cả các hàng
        for (int row = 0; row < 9; row++) {
            var seen = new HashSet<char>();
            for (int col = 0; col < 9; col++) {
                if (board[row][col] != '.') {
                    if (seen.Contains(board[row][col])) return false;
                    seen.Add(board[row][col]);
                }
            }
        }
 
        // Kiểm tra tất cả các cột
        for (int col = 0; col < 9; col++) {
            var seen = new HashSet<char>();
            for (int row = 0; row < 9; row++) {
                if (board[row][col] != '.') {
                    if (seen.Contains(board[row][col])) return false;
                    seen.Add(board[row][col]);
                }
            }
        }
 
        // Kiểm tra tất cả chín box 3x3
        for (int boxRow = 0; boxRow < 3; boxRow++) {
            for (int boxCol = 0; boxCol < 3; boxCol++) {
                var seen = new HashSet<char>();
                for (int row = boxRow * 3; row < boxRow * 3 + 3; row++) {
                    for (int col = boxCol * 3; col < boxCol * 3 + 3; col++) {
                        if (board[row][col] != '.') {
                            if (seen.Contains(board[row][col])) return false;
                            seen.Add(board[row][col]);
                        }
                    }
                }
            }
        }
 
        return true;
    }
}

Logic trong ba lượt duyệt hoàn toàn giống nhau: tạo set, lặp qua nhóm, early-return khi thấy duplicate, ngược lại thêm vào. Sự lặp lại là điểm yếu. Board bị duyệt ba lần, và cấu trúc làm việc được viết ra ba lần. Code dễ đọc — theo dõi từng kiểm tra hàng, cột, box — nhưng dài hơn cần thiết.

Độ phức tạp. Time: O(81 * 3) = O(243) = O(1). Mỗi trong ba lượt duyệt thăm tối đa 81 ô. Space: O(9) mỗi set, một set tại một thời điểm, nên O(1) peak. Set bị bỏ sau mỗi hàng/cột/box nên bạn không bao giờ giữ hơn 9 ký tự cùng lúc.

Approach 2: one pass với ba mảng set

Nhận xét then chốt: mỗi ô (i, j) đồng thời thuộc đúng một hàng, một cột, và một box. Bạn có thể kiểm tra cả ba membership cùng lúc, trong một lần duyệt duy nhất.

Khởi tạo trước 27 set — rows[0..8], cols[0..8], boxes[0..8] — một set cho mỗi nhóm. Với mỗi ô đã điền, tra chữ số hiện tại trong set hàng, set cột, và set box tương ứng. Nếu bất kỳ tra cứu nào trùng, return false. Ngược lại, chèn chữ số đó vào cả ba.

class Solution:
    def isValidSudoku(self, board):
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
 
        for i in range(9):
            for j in range(9):
                cell = board[i][j]
                if cell == '.':
                    continue
 
                box_index = (i // 3) * 3 + j // 3
 
                if cell in rows[i] or cell in cols[j] or cell in boxes[box_index]:
                    return False
 
                rows[i].add(cell)
                cols[j].add(cell)
                boxes[box_index].add(cell)
 
        return True

public class Solution {
    public bool IsValidSudoku(char[][] board) {
        var rows = new HashSet<char>[9];
        var cols = new HashSet<char>[9];
        var boxes = new HashSet<char>[9];
 
        for (int k = 0; k < 9; k++) {
            rows[k] = new HashSet<char>();
            cols[k] = new HashSet<char>();
            boxes[k] = new HashSet<char>();
        }
 
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char cell = board[i][j];
                if (cell == '.') continue;
 
                int boxIndex = (i / 3) * 3 + j / 3;
 
                if (rows[i].Contains(cell) ||
                    cols[j].Contains(cell) ||
                    boxes[boxIndex].Contains(cell)) {
                    return false;
                }
 
                rows[i].Add(cell);
                cols[j].Add(cell);
                boxes[boxIndex].Add(cell);
            }
        }
 
        return true;
    }
}

Độ phức tạp. Time: O(81) = O(1). Một lần duyệt, ba thao tác O(1) trên hash set mỗi ô. Space: O(27 * 9) = O(243) = O(1). Tất cả 27 set tồn tại đồng thời, mỗi set chứa tối đa 9 ký tự. Đây là trade-off: phiên bản one-pass dùng nhiều bộ nhớ hơn ở peak (243 slot ký tự so với 9), nhưng hằng số vẫn nhỏ không đáng kể.

Trace tay qua một phần của Example 1

Hãy đi qua năm ô không trống đầu tiên của hàng 0. Board bắt đầu bằng:

Hàng 0: ['5','3','.','.','7','.','.','.','.']

Trạng thái ban đầu: rows[0] = {}, cols[0..8] = {}, boxes[0..2] = {}.

Ô (0,0) = '5'
  box_index = (0//3)*3 + (0//3) = 0*3 + 0 = 0
  '5' in rows[0]? Không. '5' in cols[0]? Không. '5' in boxes[0]? Không.
  -> rows[0] = {'5'}, cols[0] = {'5'}, boxes[0] = {'5'}

Ô (0,1) = '3'
  box_index = 0*3 + 0 = 0
  '3' in rows[0]? Không. '3' in cols[1]? Không. '3' in boxes[0]? Không.
  -> rows[0] = {'5','3'}, cols[1] = {'3'}, boxes[0] = {'5','3'}

Ô (0,2) = '.'  -> bỏ qua

Ô (0,3) = '.'  -> bỏ qua

Ô (0,4) = '7'
  box_index = 0*3 + (4//3) = 0 + 1 = 1
  '7' in rows[0]? Không. '7' in cols[4]? Không. '7' in boxes[1]? Không.
  -> rows[0] = {'5','3','7'}, cols[4] = {'7'}, boxes[1] = {'7'}

Bây giờ xét Example 2, nơi ô trên cùng bên trái đổi thành '8', và hàng 3 cũng bắt đầu bằng '8'. Khi đến ô (3,0) = '8':

Ô (3,0) = '8'
  box_index = (3//3)*3 + (0//3) = 1*3 + 0 = 3
  '8' in rows[3]? Không (ô đầu tiên của hàng 3). '8' in cols[0]? Có (từ (0,0)='8').
  -> return False

Kiểm tra cột phát hiện ngay. Kiểm tra box cũng sẽ bắt được nếu thay vào đó bạn có '8' tại (0,0) và '8' tại (1,1) — chúng chia sẻ box 0 nhưng không chung hàng hay cột. Cơ chế tổng quát là vậy; Example 2 chỉ tình cờ có lỗi ở cột.

Bảng so sánh

Cả hai đều O(1) time và space trên input kích thước cố định này. Ở kích thước 9x9, sự chênh lệch giữa 243 và 81 lần thăm ô là không đáng kể. Điều quan trọng hơn là khả năng mở rộng: nếu board có kích thước n x n, phiên bản one-pass duyệt mỗi ô đúng một lần — đó là mức tối thiểu lý thuyết.

Các edge case quan trọng

Bảng toàn dấu chấm (bảng trống). Mọi ô đều rơi vào if cell == '.' và bị bỏ qua. Tất cả set vẫn rỗng. Trả về true. Bảng trống hợp lệ theo đề bài — không có ô nào được điền để kiểm tra.

Chỉ một ô được điền. Một lần chèn vào một row set, một col set, một box set. Không có entry nào trước đó. Trả về true. Một ô duy nhất không thể vi phạm bất kỳ ràng buộc nào.

Duplicate trong cùng hàng. Giả sử '8' xuất hiện hai lần trong hàng 3. Lần xuất hiện thứ hai thấy '8' đã có trong rows[3] và trả về false. Các kiểm tra cột và box không chạy cho ô đó — short-circuit evaluation dừng tại hit đầu tiên.

Duplicate trong cùng box, khác hàng khác cột. Đây là trường hợp thú vị: '8' tại (0,0) và '8' tại (1,1) không chung hàng, không chung cột, nhưng cùng box 0. Kiểm tra row và col đều pass — chỉ kiểm tra box mới bắt được. Đó là lý do cần cả ba set.

Ô ở ranh giới box. Ô (2,2) và (3,3) nằm trong các box khác nhau (0 và 4), dù chúng gần nhau về mặt hình học. Công thức (i//3)*3 + j//3 xử lý đúng: (2//3)*3 + (2//3) = 0 và (3//3)*3 + (3//3) = 4. Nếu nghi ngờ công thức box, liệt kê một vài ô ở ranh giới để kiểm tra thủ công.

Pattern ẩn: canonical-key bucketing

Điều bài toán này thực sự luyện là một pattern tôi gọi là canonical-key bucketing. Bạn có một tập hợp các items (các ô), mỗi item đồng thời thuộc nhiều nhóm. Bạn muốn phát hiện bất kỳ nhóm nào chứa hai item giống hệt nhau. Cơ chế: với mỗi nhóm có thể có, duy trì một set. Với mỗi item, tra key của nó trong set của tất cả các nhóm nó thuộc về; khi trùng, reject; ngược lại, chèn vào.

"Key" ở đây chỉ là ký tự chữ số. "Nhóm" là hàng, cột, box. Nhưng pattern hoàn toàn giống xuất hiện trong:

• Contains Duplicate (217): một nhóm (toàn bộ mảng), key là giá trị phần tử.
• Group Anagrams (49): mỗi item (từ) được bucketed theo canonical key (các ký tự đã sắp xếp). Các item chia sẻ key thuộc cùng nhóm.
• Longest Consecutive Sequence (128): set dùng để kiểm tra O(1) membership thay vì bucketing, nhưng nguyên tắc "phần tử này đã có trong nhóm khái niệm này chưa" là giống hệt.

Nhận ra canonical-key bucketing giúp bạn giải Valid Sudoku ngay lần đầu gặp. Khi đề bài mô tả các constraint nhóm (hàng, cột, box), bạn biết cần một tracking set cho mỗi nhóm, và câu hỏi rút gọn thành "công thức định danh nhóm là gì?"

Tôi sẽ ship phiên bản nào, và tại sao

Tôi sẽ viết phiên bản one-pass. Không phải vì nó chạy nhanh hơn đáng kể trên bảng 9x9 — không phải vậy. Lý do là sự rõ ràng khi bảo trì: phiên bản ba lượt lặp lại cùng logic "tạo set, duyệt nhóm, kiểm tra duplicate" ba lần với các pattern lặp khác nhau. Bất kỳ thay đổi nào trong tương lai — kích thước board khác, ràng buộc bổ sung, nguồn dữ liệu khác — đòi hỏi cập nhật ba khối song song. Phiên bản one-pass biểu diễn cùng logic một lần và tính toán cả ba group membership bằng một công thức duy nhất. Ngắn hơn và khó để các phần bị lệch nhau.

Phần duy nhất không hiển nhiên là công thức box index, và đáng để comment trong code production. Một dòng comment, và công thức trả lại xứng đáng bằng sự rõ ràng.

Vị trí bài này trong series arrays-hashing

Đây là bài thứ tám trong series. Các bài trước đã thiết lập các pattern hash set và hash map nền tảng: Two Sum (1) cho complement lookup, Valid Anagram (242) cho frequency counting, Contains Duplicate (217) cho set-membership check đơn giản nhất, Group Anagrams (49) cho key-based bucketing. Valid Sudoku là bài đầu tiên đòi hỏi nhiều set đồng thời — một set cho mỗi nhóm — thay vì một cấu trúc toàn cục duy nhất. Đó là bước khái niệm mà bài này thêm vào.

Sudoku Solver (37) là phần mở rộng tự nhiên. Trong khi bài này hỏi "bảng hiện tại có hợp lệ không", Solver hỏi "bạn có thể điền các ô trống để làm cho nó hợp lệ không". Implementation dùng backtracking, và nó gọi kiểm tra hợp lệ tại mỗi bước điền — một kiểm tra trông giống hệt những gì chúng ta đã viết ở đây. Hiểu bài 36 là điều kiện tiên quyết thực sự cho bài 37.

Set Matrix Zeroes (73) là một loại matrix constraint đa nhóm khác: nếu một ô bằng 0, toàn bộ hàng và cột của nó trở thành 0. Sự phối hợp "ô này ảnh hưởng đến hàng và cột của nó đồng thời" là ý tưởng cấu trúc giống như "ô này được kiểm tra với hàng và cột của nó đồng thời."

N-Queens (51) tổng quát hóa cấu trúc ràng buộc. Hàng và cột xuất hiện lại, nhưng bạn thay thế box 3x3 bằng các đường chéo. Canonical-key cho một đường chéo là row - col hoặc row + col. Cùng pattern bucketing, công thức key khác.

Unique Paths with Constraints (980) thêm một twist: việc tracking ràng buộc trở nên động khi bạn khám phá board qua backtracking. Khái niệm group membership vẫn còn; điều thay đổi là membership được xây dựng và tháo rời dần dần.