Google Kickstart 2013 Round B Проблема Средство проверки судоку дает неправильный ответ, но работает

Как упоминалось в @jabaa, вы забыли проверить подматрицы.

Более того, проверки сумм недостаточно, как например 1 + 3 = 2 + 2.

Эффективное решение состоит в проверке в каждой строке, столбце или подматрице, чтобы ни одно число не приходило дважды.

Это эффективно при условии, что сначала нужно проверить, что все числа находятся в хорошем диапазоне [1, n^2]

#include <iostream>
#include <vector>

bool check_line (int sudo[36][36], const int &n, const int &n2, const int &line) {
    std::vector<int> vali(n2 + 1, 0);
    for (int i = 0; i < n2; i++) {
        int num = sudo [line][i];
        if (vali[num]) return false;
        vali[num] = 1;
    }
    return true;
}

bool check_col (int sudo[36][36], const int &n, const int &n2, const int &col) {
    std::vector<int> vali(n2 + 1, 0);
    for (int i = 0; i < n2; i++) {
        int num = sudo [i][col];
        if (vali[num]) return false;
        vali[num] = 1;
    }
    return true;
}

//  line and col represent the position of the first cell of the submatrix
bool check_sub_matr (int sudo[36][36], const int &n, const int &n2, const int &line, const int &col) {
    std::vector<int> vali(n2 + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int num = sudo [line+i][col+j];
            if (vali[num]) return false;
            vali[num] = 1;
        }
    }
    return true;
}

bool validity (int sudo[36][36], const int& n, const int& n2) {
    // First check validity of numbers
    for (int i = 0; i < n2; i++) {
        for (int j = 0; j < n2; j++) {
            int number = sudo[i][j];
            if ((number < 1) || (number > n2)) return false;
        }
    }
    // Check lines
    for (int i = 0; i < n2; i++) {
        auto check = check_line (sudo, n, n2, i);
        if (!check) return false;
    }
    // Check columns
    for (int i = 0; i < n2; i++) {
        auto check = check_col (sudo, n, n2, i);
        if (!check) return false;
    }
    // Check sub-matrices
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; ++j) {
            auto check = check_sub_matr (sudo, n, n2, i*n, j*n);
            if (!check) return false;
        }
    }   
    return true;
}

int main() {
    int sudo[36][36];
    int nt;
    std::cin >> nt;
    
    for (int t = 1; t <= nt; ++t) {
        int n, n2;
        std::cin >> n;
        n2 = n*n;
        for (int i = 0; i < n2; i++) {
            for (int j = 0; j < n2; j++) {
                std::cin >> sudo[i][j];
            }
        }
        auto valid = validity (sudo, n, n2);
        std::cout << "Case #" << t << ": ";
        if (valid) std::cout << "Yes" << std::endl;
        else std::cout << "No" << std::endl;
    }
    return 0;
}

В некоторых случаях ваш код не возвращает правильные ответы. Вы также должны проверить подматрицы, и вы не можете проверить их с помощью суммы. Вот три тестовых примера, чтобы продемонстрировать проблемы в вашем коде:

3
3
5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5
3
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
8 5 9 7 6 1 4 2 3
1 9 8 3 4 2 5 6 7
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
3
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
2 8 8 3 4 2 5 6 7
7 6 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

Ваш код возвращает Yes в обоих случаях, но ожидаемый результат - No в обоих случаях.