Tabuleiro de Sudoku

É-lhe fornecido um tabuleiro de Sudoku de 9x9 com algumas células já preenchidas. O seu objetivo é resolver este tabuleiro e encontrar uma solução válida. Caso existam várias soluções possíveis, pode imprimir qualquer uma delas.
Um tabuleiro de Sudoku é uma grelha de 9x9 dividida em nove subgrelhas de 3x3. Cada célula na grelha pode conter um número entre 1 e 9. O objetivo do Sudoku é preencher as células vazias de forma a que cada linha, cada coluna e cada subgrelha de 3x3 contenham todos os números de 1 a 9 sem repetições.

Entrada

A entrada consiste em 9 linhas, cada uma com 9 inteiros separados por espaços, representando o estado do tabuleiro de Sudoku. Os números fornecidos variam entre 1 e 9, e as células vazias são representadas por 0.

Saída

Imprima 9 linhas, cada uma com 9 inteiros separados por espaços, representando a solução do tabuleiro de Sudoku. Se existirem várias soluções possíveis, pode imprimir qualquer uma delas.

Exemplos

Entrada
Saída
9 8 0 0 0 0 3 2 1 0 0 0 0 0 3 0 8 5 0 0 1 0 2 0 0 0 0 0 0 0 5 0 7 0 0 0 0 0 4 0 0 0 1 0 0 0 9 0 0 0 0 0 0 0 5 1 0 0 0 0 0 7 3 0 0 2 0 1 0 0 0 0 8 6 0 0 4 0 0 0 9
9 8 7 6 5 4 3 2 1 2 4 6 1 7 3 9 8 5 3 5 1 9 2 8 7 4 6 1 2 8 5 3 7 6 9 4 6 3 4 8 9 2 1 5 7 7 9 5 4 6 1 8 3 2 5 1 9 2 8 6 4 7 3 4 7 2 3 1 9 5 6 8 8 6 3 7 4 5 2 1 9

Constraints

Time limit: 50 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue