For a classic Sudoku, your aim 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 contain all of the digits from 1 to 9. To make it easier, we guarantee that:
If you choose the order wisely, you can always find such a special blank that its row (column, or 3*3 subgrid) has already been filled with 8 numbers, so that you can determine its value quite easily. (Hint may help you understand the definition of special blanks).
However, if you cannot find such special blank till you complete the Sudoku, just point out that the test data is incorrect.
There is a Sudoku presented by ‘1~9’ and ‘ x ’. ‘x’ shows the blank you need to fill.(More details can be found at Sample input.) (Number of 'x's is greater than 1.)
If you can always find ‘special blank’ till you complete the sudoku, print your solution of Sudoku as the given format. Otherwise print 'The test data is incorrect!'(without quotes), instead.
'Special blank' means that its row has been filled with 8 numbers, or its column has been filled with 8 numbers, or its 3*3 subgrid has been filled with 8 numbers.
For the sample input, you can choose the order (5,5)，(4,8)，(5,8) to fill the blank. Initially, (5,5) and (4,8) are the 'special blanks', since that (5,5)'s 3*3 subgrid and (4,8)'s row have already been filled with eight numbers. When (5,5) is filled, (5,8) becomes a new 'special blank'. After filling (4,8) and (5,8), the sudoku is completed.
6 1 8 | 5 3 7 | 4 9 2 |
5 9 4 | 1 x x | 6 3 7 |
2 3 7 | 4 6 9 | 8 5 1 |
3 7 2 | 6 5 1 | 9 4 8 |
9 4 5 | 3 x x | 1 2 6 |
1 8 6 | 2 9 4 | 5 7 3 |
7 6 3 | 8 4 5 | 2 1 9 |
8 5 1 | 9 2 3 | 7 6 4 |
4 2 9 | 7 1 6 | 3 8 x |
For this test case, the most lower-right x is the first 'special blank' that we seek. However, after filling that, you can not find any other 'special blank', so just print 'The test data is incorrect!'