EASUDOKU - Easy sudoku

no tags 

You are to solve the classic 9x9 sudoku problem.

Input

The first line contains only one number - number of test cases (more than 1 and less then 15). Than the test cases are given. Each of them is given by 81 numbers (from 0 to 9) seperated by single white space (new line after each 9th number). Zero means that it is to solve by your program.

Output

In case of there does not exist the solution write "No solution". If there exist 81 number beeing the solution of sudoku problem, you have to write all those 81 numbers (separated like in input).

Example

Input:
2
0 0 0 0 6 9 8 3 0
9 8 0 0 0 0 0 7 6
6 0 0 0 3 8 0 5 1
2 0 5 0 8 1 0 9 0
0 6 0 0 0 0 0 8 0
0 9 0 3 7 0 6 0 2
3 4 0 8 5 0 0 0 9
7 2 0 0 0 0 0 6 8
0 5 6 9 2 0 0 0 0

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

Output:
5 1 2 7 6 9 8 3 4
9 8 3 5 1 4 2 7 6
6 7 4 2 3 8 9 5 1
2 3 5 6 8 1 4 9 7
1 6 7 4 9 2 3 8 5
4 9 8 3 7 5 6 1 2
3 4 1 8 5 6 7 2 9
7 2 9 1 4 3 5 6 8
8 5 6 9 2 7 1 4 3
No solution

hide comments
vengatesh15: 2017-03-23 15:18:52

backtracking :-)

JD: 2016-10-20 13:26:45

Attempt this one too http://www.spoj.com/problems/EZSUDOKU/

sfd_team3: 2016-07-25 11:01:11

AC in one go, BFS to easy

vovandaihai: 2016-07-25 11:00:00

Last edit: 2016-07-25 11:11:09
lampv: 2016-07-24 19:11:49

Easy backTrack, accept one go!

xamitksx: 2015-08-06 13:38:21

Simple backTrack

Chirag Gupta: 2013-11-26 09:15:11

@roxy kindly help me out. I have posted my problem on the forum
https://www.spoj.com/forum/viewtopic.php?f=3&t=13325&sid=9c789ae87d285f76c7dda4aff1c3b5b3


Added by:Rafal Nowak
Date:2007-03-23
Time limit:0.139s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO