https://codingcompetitions.withgoogle.com/kickstart/round/0000000000434ad7/00000000004347b3
Sudoku is a popular single player game. The objective is to fill a 9x9 matrix with digits so that each column, each row, and all 9 non-overlapping 3x3 sub-matrices contain all of the digits from 1 through 9. Each 9x9 matrix is partially completed at the start of game play and typically has a unique solution.
Given a completed N2xN2 Sudoku matrix, your task is to determine whether it is a valid solution. A valid solution must satisfy the following criteria:
Each row contains each number from 1 to N2, once each.
Each column contains each number from 1 to N2, once each.
Divide the N2xN2 matrix into N2 non-overlapping NxN sub-matrices. Each sub-matrix contains each number from 1 to N2, once each.
My code:
#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;
}
}
My results:
Case #1: Yes
Case #2: No
Case #3: No
Example results:
Case #1: Yes
Case #2: No
Case #3: No
Is it because it's not fast enough?
As mentioned by @jabaa you forgot to check the sub-matrices.
Moreover, checking the sums is not enough, as for example 1 + 3 = 2 + 2.
An efficient solution consists in checking, in each line, column or sub-matrix, that no number arrives twice.
This is efficient, at the condition to first check that all numbers are in the good range [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;
}