Kiểm tra bảng Sudoku 9×9 hợp lệ bằng Python: Thuật toán & Tối ưu

Tại sao bạn nên làm bài này?

• Đây là bài toán kinh điển giúp bạn làm chủ thao tác trên mảng 2 chiều (Matrix).

• Rèn tư duy logic chia nhỏ vấn đề và cách sử dụng Hash Set để tra cứu O(1).

• Sau bài này, bạn sẽ hiểu cách biến đổi index tuyến tính thành tọa độ lưới 3×3 cực kỳ chuyên nghiệp.

Tóm tắt nội dung

• 3 quy tắc vàng của Sudoku cần kiểm tra.

• Giải pháp “Clean Code”: Chia nhỏ hàm kiểm tra hàng, cột, vùng.

• Giải pháp “Hacker”: Gom nhóm logic chỉ trong 1 lần duyệt vòng lặp.

• Phân tích độ phức tạp Time & Space.

Bạn xem thêm:

• Hướng Dẫn Lập File Kế Toán Excel Theo Thông Tư 133 Cho SMEs
• 10 Thủ Thuật Excel Nâng Cao Cho Kế Toán Tổng Hợp
• 50 Bài Tập Python Cơ Bản Có Lời Giải

1. Đề bài 

Vì đề bài chỉ có tên, được xây dựng phiên bản chuẩn hóa Input/Output thường gặp trong các hệ thống chấm bài tự động để bạn dễ kiểm thử.

Đề bài:

Cho một bảng Sudoku kích thước 9×9 đã được điền đầy đủ các số. Hãy kiểm tra xem bảng này có hợp lệ hay không.

Một bảng Sudoku hợp lệ khi thỏa mãn 3 điều kiện:

1. Mỗi hàng chứa các số từ 1 đến 9, không trùng lặp.

2. Mỗi cột chứa các số từ 1 đến 9, không trùng lặp.

3. Mỗi ô vuông nhỏ 3×3 (trong tổng số 9 ô vuông con) chứa các số từ 1 đến 9, không trùng lặp.

Input:

• 9 dòng, mỗi dòng chứa 9 số nguyên cách nhau bởi khoảng trắng.

Output:

• In ra YES nếu hợp lệ, NO nếu không hợp lệ.

Constraints (Giới hạn):

• Giá trị mỗi ô: 1 <= A[i][j] <= 9.

• Kích thước cố định: 9×9.

Ví dụ 1:

Input:

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

Output:

YES

Ví dụ 2:

Input (Hàng đầu tiên có hai số 5)

5 3 4 6 7 8 9 1 5
... (các dòng còn lại hợp lệ)

Output:

NO

2. Phân tích tư duy 

Để giải quyết bài toán kiểm tra Sudoku Python, chúng ta cần tư duy về cách máy tính truy cập mảng 2 chiều.

Logic Step-by-Step:

1. Hàng (Rows): Duyệt từng dòng grid[i], ném vào một tập hợp (Set). Nếu kích thước set == 9 => Hàng hợp lệ.

2. Cột (Columns): Duyệt từng cột j. Tập hợp các phần tử là grid[0][j], grid[1][j], ..., grid[8][j]. Check tương tự.

3. Vùng 3×3 (Sub-boxes): Đây là phần khó nhất. Làm sao để duyệt?

   • Bảng 9×9 chia làm 9 ô vuông con.

   • Ô vuông con thứ k (từ 0-8) sẽ bắt đầu tại hàng (k // 3) * 3 và cột (k % 3) * 3.

   • Hoặc cách khác: Với mỗi ô (i, j), nó thuộc về khối 3×3 thứ (i // 3) * 3 + (j // 3).

Bẫy thường gặp:

• Input sai format: Đề bài giả định input là số nguyên, nhưng thực tế có thể có ký tự lạ (cần try-except nếu làm dự án thật).

• Index Out of Bound: Tính toán chỉ số vùng 3×3 sai dẫn đến lỗi truy cập mảng.

3. Giải pháp 1: 

Cách tiếp cận này chia bài toán thành 3 hàm con riêng biệt. Tuy code dài hơn nhưng cực kỳ dễ debug và bảo trì. Đây là style được khuyến khích khi học lập trình Python qua bài tập.

Code Python 

import sys
def check_list_valid(nums):
    """
    Kiểm tra một list 9 số có chứa đủ 1-9 không trùng lặp hay không.
    Sử dụng Set để kiểm tra trùng lặp.
    """
    # Nếu có số nằm ngoài 1-9 -> False
    for x in nums:
        if x < 1 or x > 9:
            return False
            
    # Dùng set để loại bỏ phần tử trùng
    seen = set(nums)
    # Nếu số lượng phần tử duy nhất là 9 -> Hợp lệ
    return len(seen) == 9
def is_valid_sudoku(board):
    # 1. Kiểm tra 9 Hàng
    for i in range(9):
        row = board[i]
        if not check_list_valid(row):
            return False
            
    # 2. Kiểm tra 9 Cột
    for j in range(9):
        # Tạo list chứa các phần tử của cột j
        col = [board[i][j] for i in range(9)]
        if not check_list_valid(col):
            return False
            
    # 3. Kiểm tra 9 Vùng 3x3
    # Duyệt qua toạ độ góc trái trên của từng ô 3x3
    # Các góc này là: (0,0), (0,3), (0,6), (3,0),...
    for r in range(0, 9, 3):
        for c in range(0, 9, 3):
            block = []
            # Duyệt nội bộ trong ô 3x3
            for i in range(3):
                for j in range(3):
                    block.append(board[r + i][c + j])
            
            if not check_list_valid(block):
                return False                
    return True
# --- Phần đọc Input chuẩn ---
def solve():
    board = []
    try:
        # Đọc 9 dòng từ stdin
        for _ in range(9):
            # Đọc dòng, tách chuỗi, chuyển thành int
            line = list(map(int, sys.stdin.readline().split()))
            if len(line) != 9:
                raise ValueError("Mỗi dòng phải đủ 9 số")
            board.append(line)
        
        if len(board) != 9:
             raise ValueError("Phải đủ 9 dòng")
        if is_valid_sudoku(board):
            print("YES")
        else:
            print("NO")
            
    except ValueError as e:
        # Xử lý trường hợp input lỗi format
        print("NO") # Hoặc in e để debug
if __name__ == "__main__":
    solve()

Phân tích Big-O:

• Time Complexity: O(N^2) hay cụ thể là O(9x 9). Chúng ta duyệt qua bảng 3 lần (hàng, cột, vùng).

• Space Complexity: O(N) để lưu trữ mảng tạm col, block hoặc set.

4. Giải pháp 2: Tối ưu 

Đây là cách giải thường dùng. Thay vì duyệt 3 lần, chúng ta chỉ duyệt bảng đúng 1 lần duy nhất.

Chúng ta sẽ mã hóa vị trí của số vào một tập hợp seen.

Ví dụ: Số 5 ở hàng 0, cột 0, khối 0 sẽ được lưu là 3 chuỗi string:

• "row 0 has 5"

• "col 0 has 5"

• "block 0-0 has 5"

Nếu bất kỳ chuỗi nào đã tồn tại trong seen, nghĩa là bị trùng => Return False.

import sys
def is_valid_sudoku_optimized(board):
    seen = set()
    
    for i in range(9):
        for j in range(9):
            num = board[i][j]
            
            # Kiểm tra giá trị hợp lệ
            if num < 1 or num > 9:
                return False
            
            # Tạo key mã hoá
            # Key hàng: (0, i, num) -> số 0 đại diện cho loại 'hàng'
            # Key cột: (1, j, num) -> số 1 đại diện cho loại 'cột'
            # Key khối: (2, i//3, j//3, num) -> số 2 đại diện cho loại 'khối'
            
            row_key = f"row {i} has {num}"
            col_key = f"col {j} has {num}"
            blk_key = f"blk {i//3}-{j//3} has {num}"
            
            if row_key in seen or col_key in seen or blk_key in seen:
                return False
            
            seen.add(row_key)
            seen.add(col_key)
            seen.add(blk_key)
            
    return True
# --- Phần đọc Input (Tương tự bên trên) ---
def solve():
    board = []
    try:
        lines = sys.stdin.read().split() # Đọc toàn bộ
        if len(lines) != 81: # 9x9 = 81 số
            print("NO")
            return
            
        iterator = iter(lines)
        for _ in range(9):
            row = []
            for _ in range(9):
                row.append(int(next(iterator)))
            board.append(row)
        if is_valid_sudoku_optimized(board):
            print("YES")
        else:
            print("NO")
    except:
        print("NO")
if __name__ == "__main__":
    solve()

Phân tích Big-O:

• Time Complexity: O(N^2) (Duyệt bảng 1 lần). Thực tế nhanh hơn cách 1 về hệ số.

• Space Complexity: O(N^2) trong trường hợp tệ nhất (lưu tất cả các trạng thái vào set).

5. Biến thể nâng cao

Biến thể 1: Kiểm tra Sudoku chưa điền hết

Đề bài: Bảng có các ô trống biểu thị bằng số 0 (hoặc dấu .). Chỉ cần kiểm tra các số đã điền có hợp lệ không.

Hướng giải:

Trong vòng lặp ở Giải pháp 2, chỉ cần thêm điều kiện:

if num == 0:
    continue # Bỏ qua ô trống
# Các logic check set giữ nguyên

Biến thể 2: Sudoku Solver

Đề bài: Cho bảng Sudoku điền dở, hãy điền nốt các số sao cho hợp lệ.

Hướng giải: Sử dụng thuật toán Quay lui (Backtracking).

1. Tìm ô trống đầu tiên.

2. Thử điền 1-9.

3. Nếu điền được (check valid), đệ quy sang ô tiếp theo.

4. Nếu điền sai (không giải được), quay lại (backtrack) thử số khác.

   Đây là nền tảng của python sudoku solver logic.

6. Lỗi thường gặp & Checklist

7. FAQ: Câu hỏi thường gặp

1. Làm sao để tối ưu vòng lặp Python trong bài này?

Sử dụng set thay vì list để kiểm tra sự tồn tại (lookup) giúp giảm độ phức tạp từ O(N) xuống O(1) trung bình. Cách giải “One Pass” ở trên là ví dụ điển hình.

2. Tại sao tôi bị lỗi Time Limit Exceeded (TLE)?

Với 9×9 thì khó TLE, nhưng nếu là thuật toán sudoku 9×9 tổng quát cho NxN lớn, việc dùng List để check in (if x in list) sẽ rất chậm. Hãy đổi sang Set.

3. Bài này có dùng Đệ quy (Recursion) không?

Bài kiểm tra hợp lệ (check) thì không cần, chỉ dùng vòng lặp. Nhưng bài giải Sudoku (solver) thì đệ quy là bắt buộc (Backtracking).

8. Học tiếp gì sau bài này? 

Bạn đã làm chủ mảng 2 chiều và Hash Set. Bước tiếp theo để nâng trình xử lý mảng 2 chiều python:

1. Làm bài Sudoku Solver  – Áp dụng Backtracking.

2. Làm bài Rotate Image (Xoay ma trận 90 độ) – Thao tác index nâng cao.

3. Tìm hiểu thư viện NumPy nếu muốn xử lý ma trận khoa học dữ liệu.

Các khóa học liên quan: 

• Làm chủ Python trong 4 tuần

• Học python căn bản thông qua lập trình 1 game

• Python Excel cho người đi làm

• Học lập trình Python cho mọi lứa tuổi

• Thành thạo xử lý dữ liệu với Python

• Tập làm kĩ sư Amazon vận hành robot nông nghiệp với Python

Một số sản phẩm từ Python:

• Tool MMO: “Máy xay clip” chuẩn MMO cho TikTok, YouTube Shorts, Facebook Reels

Một số sách lập trình Python bạn hãy tham khảo

• Tiki: Python
• Shopee: Pyhon