โปรแกรมตรวจสอบ Sudoku Grid ว่า Valid หรือไม่ (Python)

ปัญหา

ตรวจสอบ 9×9 Sudoku grid ว่า valid หรือไม่ (เฉพาะช่องที่กรอกแล้ว) ตามกฎ:
1. แต่ละแถว: 1-9 ไม่ซ้ำ
2. แต่ละคอลัมน์: 1-9 ไม่ซ้ำ
3. แต่ละ 3×3 sub-box: 1-9 ไม่ซ้ำ

วิธีแก้: Single Pass Validation

วนผ่าน grid ครั้งเดียว ตรวจ row, column, box พร้อมกัน

อัลกอริทึม

1. วน i = 0 ถึง 8:
   • สร้าง set/dict สำหรับ row, column, block
   • row_cube = 3 × (i // 3), col_cube = 3 × (i % 3) → มุมซ้ายบนของ box i
   • วน j = 0 ถึง 8:
     • เช็ค board[i][j] ใน row
     • เช็ค board[j][i] ใน column
     • rc = row_cube + j//3, cc = col_cube + j%3 → เซลล์ใน box
     • เช็ค board[rc][cc] ใน block
2. ไม่มี conflict → True

โค้ด Python

class Solution:
    def isValidSudoku(self, board):
        for i in range(9):
            row = set()
            col = set()
            block = set()
            
            row_cube = 3 * (i // 3)
            col_cube = 3 * (i % 3)
            
            for j in range(9):
                # Check row
                if board[i][j] != '.' and board[i][j] in row:
                    return False
                row.add(board[i][j])
                
                # Check column
                if board[j][i] != '.' and board[j][i] in col:
                    return False
                col.add(board[j][i])
                
                # Check 3x3 block
                rc = row_cube + j // 3
                cc = col_cube + j % 3
                if board[rc][cc] != '.' and board[rc][cc] in block:
                    return False
                block.add(board[rc][cc])
        
        return True

# ทดสอบ
ob = Solution()
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"]
]
print(ob.isValidSudoku(board))  # True

# Invalid case
board2 = [
    ["8","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],  # Duplicate 8 in col 0
    # ... rest
]
print(ob.isValidSudoku(board2))  # False

ความซับซ้อน

• Time: O(1) - คงที่ 9×9 = 81 cells
• Space: O(1) - sets ขนาดคงที่

Alternative: 3 Separate Passes

def isValidSudoku_separate(self, board):
    # Check rows
    for row in board:
        seen = set()
        for c in row:
            if c != '.' and c in seen:
                return False
            seen.add(c)
    
    # Check columns
    for j in range(9):
        seen = set()
        for i in range(9):
            if board[i][j] != '.' and board[i][j] in seen:
                return False
            seen.add(board[i][j])
    
    # Check 3x3 boxes
    for bi in range(0, 9, 3):
        for bj in range(0, 9, 3):
            seen = set()
            for i in range(3):
                for j in range(3):
                    c = board[bi+i][bj+j]
                    if c != '.' and c in seen:
                        return False
                    seen.add(c)
    return True

เวอร์ชันแยก passes อ่านง่ายกว่า แต่ single pass มีประสิทธิภาพ cache ดีกว่า