1565 - Sudoku:: HUST Online Judge

1565 - Sudoku

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 244

Solved: 66

Description

Sudoku isa logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 gridwith digits so that the final grid will satisfy the constraint: each column, each row, and each of the nine 3×3 sub-grids contains all of the digits from 1to 9.The puzzle setter provides a partially completed grid, which typically has a unique solution.

For example, look at the picture below, you’ll get a partially completed grid(shown as the left picture) as starting position, your task is to fill in the remaining cells using digits from 1 to 9, so that every row, every column and every region contains each of the digits from 1 to 9 exactly once(show as the right picture).

Here I’ll give you a simple method to fill in some cells, it’s called Only-Number method. First you choose an empty cell, then check which digits can be put in that cell and it won’t break the constraint we mentioned before. If there’s only one digit can be put in the cell, we just put that digit into the cell.

For example, let’s consider the center cell in the left picture, it’s obviously that digit 1,2,3,4,6,7,8,9 can’t be put in that cell, so only digit 5 can be put in the cell. What you need to do is put 5 into the cell.

Now you should write a program to help playing Sudoku. For each empty cell, you should use Only-Number method to check it, if you find a cell which any digit couldn’t be put in, or you find two cells in the same row/column/region that has the same digit after filling, it means the current position have some mistake, and you should leave a message for this circumstance.

Input

The first line contains an integer T (T <= 20), indicates the total test cases.

Each test case will consist of a 9x9 grid of characters, where each character will either be a digit between 1 and 9 inclusively or be ‘*’ indicating an empty cell.

There will be a blank line between each test cases.

Output

For each test case, first print a line “Case #X:”, where X is the test case number(starting with 1).

And then:

If we can’t fill any grid by using Only-Number method, output “No suggestion.”(Quote for clarify). If there exists at least one grid that any digit couldn’t be put in, output “Mistake situation.”(Quote for clarify).

Otherwise, output an 9x9 grid of characters consists of ‘*’ and digits from 1 to 9, indicating the final position we get by using Only-Number method.

sample input

3
1****35*9
*4***7*6*
5*9**42**
*1**8235*
*6*****7*
*3295**1*
**14**7*5
*2*1***9*
6*72****1

5**8***9*
3****57**
***943**8
**97**83*
6*******4
*32**46**
7**239***
**34****5
*1***7**9

1****35*9
*4***7*6*
5*9**42**
*1**8235*
*6*****7*
*3295**1*
**14**7*5
*2*1***96
6*72****1

sample output

Case #1:
1****35*9
*4***7*6*
5*9**42**
*14*8235*
*6*3*1*7*
*32956*1*
**14**7*5
*2*1***9*
6*72****1
Case #2:
No suggestion.
Case #3:
Mistake situation.

hint

In test case 1, first we’ll find the cell at cell(4, 3), only digit 4 can be put into the cell, so we fill in the empty cell with 4. Pay attention to cell(4, 9), digit 4 and digit 6 can be put into that cell, so your program won’t determine the digit in cell(4, 9) even if you know the digit 4 should be placed in cell(4, 3).

In test case 2, you can’t find any cell which can fill digit in by using Only-Number method.

In test case 3, both cell(4, 3) and cell(4, 9) can be determined by Only-Number method, and each of them can only place digit 4, so it break the constraint we mentioned before.

source

Zehua HONG