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