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.|

BSUDO - Sudoku

Sudoku é uma tarefa muito simples. Um tabela quadrada com 9 linhas e 9 colunas é dividida em 9 quadrados menores de 3 x 3 como mostrado na figura. Em algumas das celulas estão escritos digitos de 1 a 9. As outras celulas são vazias. O objetivo é preencher as celulas vazias com digitos decimais de 1 a 9, um digito por celula, de tal modo que em cada linha, em cada coluna, e em cada subquadrado 3 x 3, todos os digitos de 1 a 9 apareçam. Escreva um programa que resolva um Sudoku.

sudoku

Entrada

A entrada iniciará com o numero de casos de teste. Para cada caso de teste, 9 linhas se seguem, correspondendo às linhas da tabela. Em cada linha, uma string com exatamente 9 digitos decimais é dada, correspondendo às celulas nesta linha. Se uma celula está vazia, isto é representa por um '0'.

Saída

Para cada caso de teste, seu programa deve imprimir a solução no mesmo formato dos dados de entrada. As celulas vazias tem de ser preenchidas de acordo com as regras. Em caso de haver mais de uma solução, imprima qualquer uma. É garantido que todas entradas tem solução válida.

Exemplo

Entrada:
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107 Saída: 143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

 

 


Adicionado por:gogo40
Data:2009-11-28
Tempo limite:0.265s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP OBJC PERL6 PY_NBC SCALA SQLITE TCL
Origem:ACM ICPC SEERC 2005

hide comments
2010-08-07 02:01:57 André Costa [UFPE]
Consegui 0.00s! \o/

Fiz com operaçőes bitwise e tive que precompilar alguns cálculos pra conseguir um tempo baixo. Submeti e tinha dado 0.01s. Como năo via mais formas de otimizar o algoritmo, fui otimizar a saída. Imprimir o sudoku de uma vez (em vez de valor por valor :S) tirou o centésimo que faltava. :)

[]'s
2009-11-29 02:50:24 gogo40
É possível passar esse problema! O TL apertado é para estimular vocês a usarem certas técnicas que resolvem um sudoku bem rapidamente.

PS.: Este problema tem corretor especial.

Last edit: 2009-11-29 18:27:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.