Valid Sudoku ใน C++

โจทย์

ตรวจสอบว่า 9×9 Sudoku Board ถูกต้องตามกฎหรือไม่ (ไม่ต้องแก้ แค่ Validate)

กฎ Sudoku

1. แต่ละ Row มีตัวเลข 1-9 ไม่ซ้ำ (เว้น . ไว้)
2. แต่ละ Column มีตัวเลข 1-9 ไม่ซ้ำ
3. แต่ละ 3×3 Sub-box มีตัวเลข 1-9 ไม่ซ้ำ

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

bool isValidSudoku(vector<vector<char>>& board) {
    // Check Rows
    for (int i = 0; i < 9; i++) {
        vector<bool> seen(10, false); // 1-9
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                int num = board[i][j] - '0';
                if (seen[num]) return false;
                seen[num] = true;
            }
        }
    }
    
    // Check Columns
    for (int j = 0; j < 9; j++) {
        vector<bool> seen(10, false);
        for (int i = 0; i < 9; i++) {
            if (board[i][j] != '.') {
                int num = board[i][j] - '0';
                if (seen[num]) return false;
                seen[num] = true;
            }
        }
    }
    
    // Check 3x3 Sub-boxes
    for (int boxRow = 0; boxRow < 3; boxRow++) {
        for (int boxCol = 0; boxCol < 3; boxCol++) {
            vector<bool> seen(10, false);
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    int r = boxRow * 3 + i;
                    int c = boxCol * 3 + j;
                    if (board[r][c] != '.') {
                        int num = board[r][c] - '0';
                        if (seen[num]) return false;
                        seen[num] = true;
                    }
                }
            }
        }
    }
    
    return true;
}

// Optimized: Single Pass with 3 Arrays
bool isValidSudokuOptimized(vector<vector<char>>& board) {
    // rows[9][10], cols[9][10], boxes[9][10]
    bool rows[9][10] = {}, cols[9][10] = {}, boxes[9][10] = {};
    
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') continue;
            int num = board[i][j] - '0';
            int boxIdx = (i / 3) * 3 + (j / 3);
            
            if (rows[i][num] || cols[j][num] || boxes[boxIdx][num]) {
                return false;
            }
            rows[i][num] = cols[j][num] = boxes[boxIdx][num] = true;
        }
    }
    return true;
}

// Bitmask Version (Fastest)
bool isValidSudokuBitmask(vector<vector<char>>& board) {
    int rows[9] = {}, cols[9] = {}, boxes[9] = {};
    
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') continue;
            int bit = 1 << (board[i][j] - '0');
            int boxIdx = (i / 3) * 3 + (j / 3);
            
            if (rows[i] & bit) return false;
            if (cols[j] & bit) return false;
            if (boxes[boxIdx] & bit) return false;
            
            rows[i] |= bit;
            cols[j] |= bit;
            boxes[boxIdx] |= bit;
        }
    }
    return true;
}

int main() {
    vector<vector<char>> 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'}
    };
    
    cout << "Valid: " << (isValidSudoku(board) ? "True" : "False") << endl;
    cout << "Optimized: " << (isValidSudokuOptimized(board) ? "True" : "False") << endl;
    cout << "Bitmask: " << (isValidSudokuBitmask(board) ? "True" : "False") << endl;
    
    // Invalid board (duplicate in row 0)
    board[0][1] = '5'; // Two 5's in row 0
    cout << "Invalid: " << (isValidSudoku(board) ? "True" : "False") << endl;
    
    return 0;
}

Complexity

• Time: O(1) - Fixed 9×9 = 81 Cells (Technically O(81) = O(1))
• Space: O(1) - Fixed-size Arrays (9×10 or 9 ints)

Bitmask Technique

ใช้ Integer 32-bit เก็บ Seen Digits:

• Bit 1 = Digit 1 Seen, Bit 2 = Digit 2 Seen, ..., Bit 9 = Digit 9 Seen
• Check: (mask & bit) != 0
• Set: mask |= bit
• เร็วกว่า Array/Vector มาก

ผลลัพธ์

Valid: True
Optimized: True
Bitmask: True
Invalid: False

สรุป

Valid Sudoku = Check Rows, Cols, 3x3 Boxes ไม่มี Duplicate 1-9 ใช้ Bitmask ทำได้ O(1) Time/Space เนื่องจาก Board Size คงที่ - LeetCode 36