谷歌Kickstart 2013年B轮问题数独检查器给出了错误的答案，但它正在工作

Question

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000434ad7/00000000004347b3
数独是一种流行的单人游戏。目标是用数字填充9x9矩阵，以便每列、每行和所有9个不重叠的3x3子矩阵包含从1到9的所有数字。每个9x9矩阵在游戏开始时部分完成，通常有一个独特的解决方案
给定一个完整的N2xN2数独矩阵，您的任务是确定它是否是有效的解决方案。有效的解决方案必须满足以下标准：

每行包含从1到N2的每个数字，每行一次
每列包含从1到N2的每个数字，每列一次
将N2xN2矩阵划分为N2个不重叠的NxN子矩阵。每个子矩阵包含从1到N2的每个数字，每个数字一次

我的代码：

 #include <iostream>
 using namespace std;


 int main()
{
int i, j, k, no, n, sum, t[36][36], validsum;
cin >> no;
for (k = 0; k < no; k++)
{
    cin >> n;

    for (i = 0; i < n * n; i++)
    {
        for (j = 0; j < n * n; j++)
        {
            cin >> t[i][j];
        }
    }

    bool valid = 1;
    
    validsum = ((n*n)*(n*n+1))/2;
    sum = 0;

    if (valid == 1)
    {
        for (i = 0; (i < n * n) && valid == 1; i++)
        {
            sum = 0;
            for (j = 0; (j < n * n) && sum < validsum; j = j+1) {
                sum += t[i][j];
            }
            if (sum != validsum)
                valid = 0;
        }
    }

    if (valid == 1)
    {
        for (j = 0; j < n * n && valid == 1; j++)
        {
            sum = 0;
            for (i = 0; i < n * n && sum < validsum; i++)
            {
                sum += t[i][j];
            }
            if (sum != validsum)
                valid = 0;
        }
    }

    cout << "Case #" << k + 1 << ": ";
    if (valid == 1)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}
}

我的结果是：

Case #1: Yes
Case #2: No
Case #3: No

示例结果：

Case #1: Yes
Case #2: No
Case #3: No

是因为速度不够快吗？

Answer 1

在某些情况下，代码不会返回正确答案。你也必须检查子矩阵，不能用求和来检查。下面是三个测试用例来演示代码中的问题：

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。

Answer 2

正如@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;
}