1383 - Sudoku
Vamos ver que não é tão fácil assim fazer as regrinhas do jogo...
Descrição
Solução
Eu decidi separar o conjunto de regras em três funções diferentes:
Verificação de linha: verificar se todos os números aparecem na linha uma e apenas uma vez.
Verificação de coluna: verificar se todos os números aparecem na coluna uma e apenas uma vez.
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)
#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;
}
Last updated
Was this helpful?