Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

SUDOIME - Sudoku

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.

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

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

Entrada:
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

Saída:
Instancia 1
SIM

Instancia 2
NAO

Adicionado por:Wanderley Guimarăes
Data:2007-09-01
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Seletiva paea Maratona de Programação do IME - 2006

hide comments
2016-10-01 02:28:33
Qual a condição de parada desse problema? e qual o tamanho máximo de n? ta faltando informação nessa questão.
2015-06-05 03:04:07 Davi Ozolin [UFABC]
Acho que a correção agora está considerando a composição individual das submatrizes 3x3. Ele só aceitou quando também fiz essa verificação, além da não-repetição nas linhas e colunas.
2013-11-01 16:55:57 Gerson Moreira Pinto Neto
Eduardo, o seu programa está completamente certo então, porém o que o Matheus quis dizer é que as pessoas podem agir de má fé e pular uma etapa de verificação do problema, sem verificar os espaços 3x3.
2012-06-04 00:02:43 Eduardo Rigamonte [IFES]
Matheus, meu programa foi aceito e esse seu teste da NAO

Last edit: 2012-06-04 00:20:51
2011-10-28 04:18:56 Matheus Gaudencio
Os testes dessa questăo năo estăo de acordo com a especificaçăo. É possível passar com um progama que năo verifica todos os casos.

Exemplo:

Entrada:

1
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 1
3 4 5 6 7 8 9 1 2
4 5 6 7 8 9 1 2 3
5 6 7 8 9 1 2 3 4
6 7 8 9 1 2 3 4 5
7 8 9 1 2 3 4 5 6
8 9 1 2 3 4 5 6 7
9 1 2 3 4 5 6 7 8

Saída esperada:

Instancia 1:
NAO

Saída obtida por um programa submetido:

Instancia 1:
SIM


Last edit: 2011-10-28 04:20:51
2011-09-22 03:16:37 Jonathan Ramos [UNIR]
Eh Fellyp, é nois aqui! :D
2011-07-11 19:19:36 Lucas Maciel [UFMG]
Uma dúvida, se passarem milhares de instancias, o programa deve calculá-las em apenas 1s ou cada instancia deve ser calculada em 1s?
2011-05-08 05:16:14 Rafael Perrella
Felypp, a quantidade de instâncias ou testes nunca é dada... ao menos nunca vi darem.
2010-10-04 13:42:24 Felypp Oliveira [UNIR]
Apesar do tempo limite ser 1s, o que da a entender que a variável n năo será um valor muito grande, seria bom definir um limite para ela.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.