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). Then the test cases are given. Each of them is given by 81 numbers (from 0 to 9) separated 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 being 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
longtv1804: 2018-12-22 13:02:10

there are many answers for a sudoku, and I take one to write, it's diference from example answer but it is definitely a correct answer. so why I got a WRONG ANSER notice after I submit my solution?

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

[Simes]: late answer, but your solution is invalid. Two 1s in block 1, and same in block 9.

Last edit: 2022-12-05 16:58:45
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:1s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO