| Online Judge | Online Exercise | Online Teaching | Online Contests | Exercise Author |
|
F.A.Q Hand In Hand Online Acmers |
Best Coder beta VIP | STD Contests DIY | Web-DIY beta |
Sudoku
Time Limit: 50000/20000 MS (Java/Others) Memory Limit: 125536/65536 K (Java/Others)Total Submission(s): 741 Accepted Submission(s): 307
Problem Description
AmazingCaddy likes Sudoku very much. One day, he got some Sudoku problems and he wondered whether these problems are well designed. He needs your help now.
Sudoku is a logic-based, combinatorial number-placement 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 regions contain all of the digits from 1 to 9.
-- Wikipedia
In this problem, the grid has three different sizes, with the formal (N^2) ¡Á (N^2), and N will be one in 2, 3 and 4. The rule is the same. The objective is to fill the (N^2) ¡Á (N^2) grid with characters so that each column, each row, and each of the N^2 regions (each size is N ¡Á N) contains all of the characters from 1 to 4(N = 2), 1 to 9(N = 3) or 1 to G (N = 4).
You task is that when you got a grid, you should tell the grid whether a puzzle or not. If it`s a puzzle, you should tell whether it is a minimal puzzle; else you should tell it has no solution or has multiple solutions.
A puzzle is a partially completed grid (the size is (N^2) ¡Á (N^2), N = 2, 3, 4), and has one and only one solution. If remove any character from a puzzle, it will lead to multiple solutions, then it is called a minimal puzzle.
Sudoku is a logic-based, combinatorial number-placement 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 regions contain all of the digits from 1 to 9.
-- Wikipedia
In this problem, the grid has three different sizes, with the formal (N^2) ¡Á (N^2), and N will be one in 2, 3 and 4. The rule is the same. The objective is to fill the (N^2) ¡Á (N^2) grid with characters so that each column, each row, and each of the N^2 regions (each size is N ¡Á N) contains all of the characters from 1 to 4(N = 2), 1 to 9(N = 3) or 1 to G (N = 4).
You task is that when you got a grid, you should tell the grid whether a puzzle or not. If it`s a puzzle, you should tell whether it is a minimal puzzle; else you should tell it has no solution or has multiple solutions.
A puzzle is a partially completed grid (the size is (N^2) ¡Á (N^2), N = 2, 3, 4), and has one and only one solution. If remove any character from a puzzle, it will lead to multiple solutions, then it is called a minimal puzzle.
Input
The input contains several cases. For each case, the first line of the input is the N (2<= N <=4). The next N^2 lines will contain the grid. Each line will have N^2 characters, represent the grid. The empty cell will be represented as ¡¯.¡¯. All input data is legal, and you can get more information from the sample input.
Output
For each case:
If the grid is not a puzzle, and has no solution, print ¡°No Solution¡±, or has multiple solutions print ¡°Multiple Solutions¡±.
If the grid is a puzzle, but not a minimal, print ¡°Not Minimal¡±, or print N lines represent the answer in the same format in the input, and ¡®.¡¯ should be replaced with the right characters. You can get more information from the sample output.
If the grid is not a puzzle, and has no solution, print ¡°No Solution¡±, or has multiple solutions print ¡°Multiple Solutions¡±.
If the grid is a puzzle, but not a minimal, print ¡°Not Minimal¡±, or print N lines represent the answer in the same format in the input, and ¡®.¡¯ should be replaced with the right characters. You can get more information from the sample output.
Sample Input
2 4312 12.4 .... ...1 3 5...9.31. 71.8...9. 32...6... ........3 .8.5.3... 4....1.5. 8..9...4. ...1..9.. .....7... 4 ...86.....D.A... .A.C.G.49....65E .......3B61C..DG 3...89.D7....24. ....4..G.9F2BD.. 49...C5.....7... 1.C..8.B6....... .6A.2.D...4.89.5 8F3BG.E24.A...7. ...6.3.A.1...... D.........5.1E2. .G...D.9........ ......F6.7.....3 6D.9.7..EG...B.. 51B.A..8........ ........F.C..71.
Sample Output
Not Minimal Multiple Solutions 9BG86F253ED4A1C7 7ADC1GB4928F365E F245EA73B61C98DG 3E6189CD7AG5F24B E873461G59F2BDAC 492D3C5FA8EB7G61 15CF98AB6D7G43E2 B6AG2ED7C34189F5 8F3BG1E24CAD6579 C756F38A219EG4BD D49A7B6CGF531E28 2G1E5D498B67CF3A GCE4D5F617B82A93 6DF9C731EG2A5B84 51B7A298D436ECGF A382B4GEF5C9D716
Source
| Home | Top |
Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-05-06 11:23:49, Gzip enabled |
Administration |