TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

76.2% (16/21)

Tags

Description

Have you ever heard the game called "suduku"?
Yeah, it's a game played on a 9 x 9 board with number 1 to 9.

But 残念です, the game that we will talk is called "kukuku".

"kukuku" is played on 4 x 4 board with number 1 to 4.
The board is partite by 4 big blocks and each big block is partite by 4 small blocks -- There are totally 16 small blocks.

By the Game Rule, you have to put the number between 1 and 4 in each small block,
you must assume each number appears exactly one time in each of rows,columns and big blocks.

NOW, you have a board that some number is already put on it, please count how many ways to solve it, and output the alphabetically first solution.

Example,
1234
4312
2143
3421
is better than
4321
2134
3412
1243

If you solve this problem, you can say "KUKUKU" and have a nice day!!

Input Format

There is four rows, and each row has four number,
the numbers means the numbers that are put on the small block already.
If the number is 0, it means the block is empty now, you should put the number on it.

Output Format

Please count how many ways to solve it, and output the alphabetically first solution like Sample Output.

And if there is no way to solve it, please output the message "I can not solve!!"(no double quotation marks)

Sample Input

1 2 3 4
4 3 1 2
2 1 4 3
3 4 2 0

Sample Output

1234
4312
2143
3421

We have 1 way(s) to solve it!!

Hints

Problem Source

原TIOJ1581

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10