EZSUDOKU  Easy modified sudoku
Do you know the old famous game, sudoku?
It is a logicbased,combinatorial numberplacement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called "boxes", "blocks", "regions", or "subsquares") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a wellposed puzzle has a unique solution.
Completed puzzles are always a type of Latin square with an additional constraint on the contents of individual regions. For example, the same single integer may not appear twice in the same row, column or in any of the nine 3×3 subregions of the 9x9 playing board.
French newspapers featured variations of the puzzles in the 19th century, and the puzzle has appeared since 1979 in puzzle books under the name Number Place.However, the modern Sudoku only started to become mainstream in 1986 by the Japanese puzzle company Nikoli, under the name Sudoku, meaning single number. It first appeared in a US newspaper and then The Times (UK) in 2004, from the efforts of Wayne Gould, who devised a computer program to rapidly produce distinct puzzles.
Since the Sudoku game is pretty hard, Mr. Bruce Banner, who is also fond in sudoku games, creates a new modified version of normal sudoku. It is tiled by 8x8 grids and divided into 4 areas of 4x4 grids.
The rule is also simplified. You need to place numbers from 1 to 8 to the empty grids(denoted by a number 0) to the sudoku puzzle. Each number in the same columns or row must be distinct. In each area of 4x4 grids, it is allowed to have duplicate numbers up to 2 numbers.
Now, your task is to help Mr. Bruce Banner to determine whether the modified sudoku puzzle he has created is of a valid puzzle or not. If it is a valid puzzle, you will also need to output the solution.
Note: It is guaranteed that here is a unique answer in each test cases t
Input
The first line of input contains an integer T(1 ≤ T ≤ 100), the number of testcases. Then, it will be followed by 8*T lines which contain the modified sudoku puzzles. Each testcases will be separated by a newline.Output
For each case print "Test case #X: ", where X (1 ≤ X ≤ T) is the case number, followed by an answer "YES" or "NO" and a newline. If there exists a valid solution, print the solution of each puzzles, and then print a newline.Example
Input: 2 1 2 3 4 5 6 7 0 5 6 2 1 3 4 0 7 6 5 0 7 2 1 3 4 3 4 7 8 6 5 2 1 2 1 5 6 8 7 4 3 4 3 6 5 7 8 1 2 0 7 1 2 4 3 5 6 7 0 4 3 1 2 6 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Output: Test case #1: YES 1 2 3 4 5 6 7 8 5 6 2 1 3 4 8 7 6 5 8 7 2 1 3 4 3 4 7 8 6 5 2 1 2 1 5 6 8 7 4 3 4 3 6 5 7 8 1 2 8 7 1 2 4 3 5 6 7 8 4 3 1 2 6 5 Test case #2: NO
hide comments
Shubham Jadhav:
20170721 10:43:47
did not realize it was a tutorial problem _ 

k2_ico:
20170531 16:24:38
Changing " i++ " to " ++i " helps in solving TLE Problems. I changed some of mine then it was judged AC.


pranav0123:
20170531 14:08:46
@Admin Can you please check my solution. I have tried it for many test cases but couldn't find the mistake.


natatassi:
20170506 04:38:11
If you are getting WA remember to reassign zero to the empty cell that you are processing when you just tried all the possibilities and you have to backtrack to the previous empty cell. 

greathj:
20161121 03:15:19
I tested for 100 cases and my solution took 50ms. But I got TLE :(


thaihoc06:
20160728 07:09:34
Same EASUDOKU, but this problem is hard to implement in JAVA. TLE :(


manhterry93:
20160727 19:05:08
finnally AC, nth times 

doluongk56:
20160727 17:15:51
NICE Last edit: 20160727 17:18:31 

khanhpqbk:
20160725 16:38:56
@lampv: same here. There must be a problem with output. Can anyone who got AC provides me a strong test case. I would be very thankful!


sfd_team3:
20160725 11:01:51
DFS, AC in two time 
Added by:  hanstan 
Date:  20160528 
Time limit:  0.100s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Self 