1383 - Sudoku

Vamos ver que não é tão fácil assim fazer as regrinhas do jogo...

Descrição

beecrowd Talent Cloudbeecrowd

Solução

Eu decidi separar o conjunto de regras em três funções diferentes:

1. Verificação de linha: verificar se todos os números aparecem na linha uma e apenas uma vez.

2. Verificação de coluna: verificar se todos os números aparecem na coluna uma e apenas uma vez.

3. Verificação de quadrado: verificar se todos os números aparecem no quadrado uma e apenas uma vez.

Daí executar o programa para cada uma das 9 linhas, 9 colunas e 9 quadrados.

Nas linguagens de programação onde era permitido, utilizei conjuntos para adicionar todos os números de uma determinada linha, coluna ou quadrado e depois verificar se tal conjunto tinha tamanho exatamente 9. Para linguagens onde tal estrutura não é trivial, utilizei um vetor para marcar cada número e se fosse marcar um número já marcado, apontar a irregularidade.

Para definir onde começa cada quadrado, onde x é o identificador do quadrado, fiz 3*(x/3) para definir a linha e 3*(x%3) para definir a coluna da coordenada de cada quadrado. Dessa maneira, temos as seguintes coordenadas para os 9 quadrados:

Quadrado	Coordenada
0	(0, 0)
1	(0, 3)
2	(0, 6)
3	(3, 0)
4	(3, 3)
5	(3, 6)
6	(6, 0)
7	(6, 3)
8	(6, 6)

C99

#include <stdio.h>

int sudoku[9][9];

int verificaLinha(int x){
    int numeros[10];

    for(int i = 0; i < 10; ++i){
        numeros[i] = 0;
    }

    for(int i = 0; i < 9; ++i){
        if(numeros[sudoku[x][i]])   return 0;
        numeros[sudoku[x][i]] += 1;
    }

    return 1;
}

int verificaColuna(int x){
    int numeros[10];

    for(int i = 0; i < 10; ++i){
        numeros[i] = 0;
    }

    for(int i = 0; i < 9; ++i){
        if(numeros[sudoku[i][x]])   return 0;
        numeros[sudoku[i][x]] += 1;
    }

    return 1;
}

int verificaQuadrado(int x){
    int numeros[10];
    int linha = 3*(x/3), coluna = 3*(x%3);

    for(int i = 0; i < 10; ++i){
        numeros[i] = 0;
    }

    for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
            if(numeros[sudoku[linha + i][coluna + j]])  return 0;
            numeros[sudoku[linha + i][coluna + j]] += 1;
        }
    }

    return 1;
}

int main(){
    int n;
    char* resposta;

    scanf("%d", &n);

    for(int k = 1; k <= n; ++k){
        for(int i = 0; i < 9; ++i){
            for(int j = 0; j < 9; ++j){
                scanf("%d", &sudoku[i][j]);
            }
        }

        printf("Instancia %d\n", k);

        resposta = "SIM";
        for(int i = 0; i < 9; ++i){
            if(!verificaLinha(i) || !verificaColuna(i) || !verificaQuadrado(i)){
                resposta = "NAO";
                break;
            }
        }

        printf("%s\n\n", resposta);
    }

    return 0;
}

C++17

JavaScript 12.18

Python 3.9