Seletiva para Maratona de Programação do IME – 2006
O jogo de Sudoku espalhou-se rapidamente por todo o mundo, tornando-se hoje o passatempo mais popular em todo o planeta. Muitas pessoas, entretanto, preenchem a matriz de forma incorreta, desrespeitando as restrições do jogo. Sua tarefa neste problema é escrever um programa que verifica se uma matriz preenchida é ou não uma solução para o problema.
A matriz do jogo é uma matriz de inteiros 9 x 9 . Para ser uma solução do problema, cada linha e coluna deve conter todos os números de 1 a 9. Além disso, se dividirmos a matriz em 9 regiões 3 x 3, cada uma destas regiões também deve conter os números de 1 a 9. O exemplo abaixo mostra uma matriz que é uma solução do problema.
Entrada
São dadas várias instâncias. O primeiro dado é o número n > 0 de matrizes na entrada. Nas linhas seguintes são dadas as n matrizes. Cada matriz é dada em 9 linhas, em que cada linha contém 9 números inteiros.
Saída
Para cada instância seu programa deverá imprimir uma linha dizendo “Instancia k“, onde k é o número da instância atual. Na segunda linha, seu programa deverá imprimir “SIM” se a matriz for a solução de um problema de Sudoku, e “NAO” caso contrário. Imprima uma linha em branco após cada instância.
| Exemplo de Entrada | Exemplo de Saída |
| 2 1 3 2 5 7 9 4 6 8 4 9 8 2 6 1 3 7 5 7 5 6 3 8 4 2 1 9 6 4 3 1 5 8 7 9 2 5 2 1 7 9 3 8 4 6 9 8 7 4 2 6 5 3 1 2 1 4 9 3 5 6 8 7 3 6 5 8 1 7 9 2 4 8 7 9 6 4 2 1 5 3 1 3 2 5 7 9 4 6 8 4 9 8 2 6 1 3 7 5 7 5 6 3 8 4 2 1 9 6 4 3 1 5 8 7 9 2 5 2 1 7 9 3 8 4 6 9 8 7 4 2 6 5 3 1 2 1 4 9 3 5 6 8 7 3 6 5 8 1 7 9 2 4 8 7 9 6 4 2 1 3 5 |
Instancia 1 SIMInstancia 2 NAO
|
Solução em C
#include <stdio.h>
int main() {
int k, i, j, temp, instancia = 0, solucao = 1;
int matriz[9][9], somaLinha[9], somaColuna[9], somaMatriz[3][3];
scanf("%i", &k);
for(int cont = 0; cont < k; cont++) {
//leitura de valores para a matriz
for(i = 0; i < 9; i++) {
for(j = 0; j < 9; j++) {
scanf("%i", &matriz[i][j]);
}
}
//inicializa variáveis somadoras com zero
for (i = 0; i < 9; i++) {
somaLinha[i] = 0;
somaColuna[i] = 0;
somaMatriz[i/3][i%3] = 0;
//descomente o prinf abaixo para facilitar o entendimento sobre
//como a matriz está sendo preenchida sem utilizar dois for
//printf("%i %i \n", i/3, i%3);
}
//contabiliza valores para resolver o problema
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
temp = matriz[i][j] * matriz[i][j];
somaLinha[i] += temp;
somaColuna[j] += temp;
somaMatriz[i/3][j/3] += temp;
//printf("%i %i %i %i %i\n", i, j, i/3, j/3, matriz[i][j]);
if (i == 8 && somaColuna[j] != 285) { break; }
}
if (somaLinha[i] != 285) { break; }
}
//mostra os resultados
instancia++;
printf("Instancia %i\n", instancia);
//determina se é a solução
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (somaMatriz[i][j] != 285) {
solucao = 0;
}
}
}
if (solucao == 1) {
printf("SIM\n\n");
} else {
printf("NAO\n\n");
}
solucao = 1;
}
return 0;
}
Teste o código em: http://ideone.com/MBGDJq