1641: 求解数独矩阵
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：12
解决：5
题目描述
数独是一种风靡全球的智力游戏，也称为Sudoku，Number Place。正规的数独题目需要保证每个题目仅有一个解。
数独规则
标准数独由9行，9列共81的小格子构成。分别在格子中填入1到9的数字，要求满足下面的条件：
1) 每一行都用到1,2,3,4,5,6,7,8,9
2) 每一列都用到1,2,3,4,5,6,7,8,9
3) 每3×3的格子都用到1,2,3,4,5,6,7,8,9
现在你的任务是：
根据9×9盘面上的已知数字，推理出所有剩余空格的数字，使每个数字在每一行、每一列和每一宫中都仅出现一次。
例如，给你如下形式的数据：
推导出最后的结果：
输入
输入有多组数据。
每组第一行输入一个正整数n，表示总共有n个数独矩阵需要计算，n==0结束输入。
随后有n*9行数据，每9行一组，代表一个数独矩阵；每一行有9个由0-9构成的数字。其中0表示该位置为空，需要计算。给定的输入数独能确保有唯一解。
输出
输出每个数独矩阵的计算结果。输出格式见范例。
样例输入 复制
2
006004050
000950070
570000409
005040003
060002180
490806000
700080062
209700000
003005907
643009700
709800000
000007200
000090030
904000007
167040090
000300026
000605008
050000000
0
样例输出 复制
case 1:
936274851
148953276
572618439
825147693
367592184
491836725
714389562
259761348
683425917
case 2:
643129785
729856413
518437269
285791634
934268157
167543892
891374526
372615948
456982371