EASUDOKU - Easy sudoku

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

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

hide comments
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
2017-03-23 15:18:52
backtracking :-)
2016-10-20 13:26:45 JD
Attempt this one too http://www.spoj.com/problems/EZSUDOKU/
2016-07-25 11:01:11
AC in one go, BFS to easy
2016-07-25 11:00:00


Last edit: 2016-07-25 11:11:09
2016-07-24 19:11:49
Easy backTrack, accept one go!
2015-08-06 13:38:21
Simple backTrack
2013-11-26 09:15:11 Chirag Gupta
@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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.