Valid Sudoku

Bài toán

Xác định xem một bảng Sudoku 9 x 9 có hợp lệ hay không. Chỉ cần xác định dựa trên các ô đã điền (các ô trống được biểu diễn bằng .).

Quy tắc hợp lệ:

1. Mỗi hàng phải chứa các chữ số 1-9 không trùng lặp.
2. Mỗi cột phải chứa các chữ số 1-9 không trùng lặp.
3. Mỗi ô vuông nhỏ 3 x 3 (trong tổng số 9 ô vuông của bảng chính) phải chứa các chữ số 1-9 không trùng lặp.

Ví dụ:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

Output: true

Phân Tích & Tiếp Cận

Giải pháp: Hash Set đơn giản

Để kiểm tra trùng lặp trong một tập hợp, Hash Set là công cụ tốt nhất. Ta cần kiểm tra 3 loại tập hợp:

1. Hàng (Row): row[0], row[1]...
2. Cột (Col): col[0], col[1]...
3. Hộp 3x3 (Box): Ta có thể đánh index cho các hộp từ 0 đến 8.
   • Công thức để tính index hộp từ tọa độ (r, c) là: boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3).

Cách 1: Mảng các Sets

Ta có thể tạo:

• 9 Sets cho các hàng.
• 9 Sets cho các cột.
• 9 Sets cho các hộp.

Duyệt qua từng ô (r, c) của bảng:

• Nếu là ., bỏ qua.
• Nếu là số:
  • Kiểm tra xem số đó đã có trong rows[r], cols[c], hoặc boxes[boxIndex] chưa.
  • Nếu có -> false.
  • Nếu chưa -> Thêm vào cả 3 Sets tương ứng.

function isValidSudoku(board: string[][]): boolean {
    const rows = new Array(9).fill(0).map(() => new Set<string>());
    const cols = new Array(9).fill(0).map(() => new Set<string>());
    const boxes = new Array(9).fill(0).map(() => new Set<string>());

    for (let r = 0; r < 9; r++) {
        for (let c = 0; c < 9; c++) {
            const val = board[r][c];
            
            if (val === '.') continue;

            const boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3);

            if (rows[r].has(val) || cols[c].has(val) || boxes[boxIndex].has(val)) {
                return false;
            }

            rows[r].add(val);
            cols[c].add(val);
            boxes[boxIndex].add(val);
        }
    }

    return true;
}

Cách 2: One Huge Set (String Encoding) - Mẹo thú vị

Thay vì quản lý 27 cái Sets nhỏ, ta dùng 1 Set duy nhất chứa các chuỗi String được mã hóa (Encode). Với mỗi số val tại (r, c), ta tạo ra 3 chuỗi định danh:

• "row:r:val" (vd: "row:0:5")
• "col:c:val" (vd: "col:0:5")
• "box:r/3:c/3:val" (vd: "box:0:0:5")

Nếu bất kỳ chuỗi nào đã tồn tại trong Set -> Trùng lặp.

function isValidSudoku(board: string[][]): boolean {
    const seen = new Set<string>();

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const val = board[i][j];
            if (val !== '.') {
                const rowKey = `row:${i}:${val}`;
                const colKey = `col:${j}:${val}`;
                const boxKey = `box:${Math.floor(i/3)}:${Math.floor(j/3)}:${val}`;

                if (seen.has(rowKey) || seen.has(colKey) || seen.has(boxKey)) {
                    return false;
                }

                seen.add(rowKey);
                seen.add(colKey);
                seen.add(boxKey);
            }
        }
    }
    return true;
}

• Time Complexity: $O(9^2) = O(1)$ vì bảng luôn là 9x9. (Nếu bảng N*N thì là $O(N^2)$).
• Space Complexity: $O(1)$ (vì kích thước bảng cố định).

Pattern Nhận Diện

Bài toán này thuần túy là hashing và matrix traversal. Điểm nhấn là cách Map tọa độ (r, c) sang Box Index. Công thức (r // 3) * 3 + (c // 3) rất hữu ích để xử lý các bài toán Grid chia nhỏ (Sub-grids).

Ứng Dụng Thực Tế

Logic này áp dụng cho mọi việc Validation (Kiểm tra hợp lệ) dữ liệu phức tạp. Khi bạn có một tập dữ liệu lớn và cần đảm bảo nhiều ràng buộc (Constraints) khác nhau (Unique constraints), việc dùng Set để track "những gì đã thấy" là cách nhanh và dễ hiểu nhất.