Sudoku hợp lệ (Valid Sudoku) trong C++

Kiểm tra bảng Sudoku 9x9 có hợp lệ không.

Quy tắc Sudoku

• Mỗi hàng: số 1-9 không trùng
• Mỗi cột: số 1-9 không trùng
• Mỗi ô 3x3: số 1-9 không trùng
• '.' đại diện ô trống

Ví dụ

Input: ma trận 9x9 với các giá trị '1'-'9' và '.'

Output: True

Cách tiếp cận

• Kiểm tra từng hàng: đếm tần suất, nếu >1 → false
• Kiểm tra từng cột: tương tự
• Kiểm tra 9 khối 3x3: block_row = (block/3)*3, block_col = (block%3)*3

Code C++

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

bool validSudoku(vector>& sudoku) {
    int count[9];
    // Check rows
    for (int row = 0; row < 9; row++) {
        memset(count, 0, sizeof(count));
        for (int col = 0; col < 9; col++)
            if (sudoku[row][col] != '.') count[sudoku[row][col]-'1']++;
        for (int i = 0; i < 9; i++) if (count[i] > 1) return false;
    }
    // Check cols
    for (int col = 0; col < 9; col++) {
        memset(count, 0, sizeof(count));
        for (int row = 0; row < 9; row++)
            if (sudoku[row][col] != '.') count[sudoku[row][col]-'1']++;
        for (int i = 0; i < 9; i++) if (count[i] > 1) return false;
    }
    // Check 3x3 blocks
    for (int block = 0; block < 9; block++) {
        int br = (block / 3) * 3, bc = (block % 3) * 3;
        memset(count, 0, sizeof(count));
        for (int r = br; r < br+3; r++)
            for (int c = bc; c < bc+3; c++)
                if (sudoku[r][c] != '.') count[sudoku[r][c]-'1']++;
        for (int i = 0; i < 9; i++) if (count[i] > 1) return false;
    }
    return true;
}

int main() {
    vector> sudoku = {
        {'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 << (validSudoku(sudoku) ? "True" : "False") << endl;
    return 0;
}

Kết quả

True