## 21682: Sudoku Solver

[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][36kb]

## 题目描述

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 sub-grids that compose the grid (also called "boxes", "blocks", "regions", or "sub-squares") contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which typically has a unique solution. Or we can say, the same single integer may not appear twice in the same 9×9 playing board row or column or in any of the nine 3×3 sub-regions of the 9×9 playing board. Now you are given a partially filled Sudoku board that has a unique(唯一) solution. Your task is to fill the board.

 Given Sudoku Puzzle Puzzle with Solution

## 输入

Input starts with an integer T (≤ 30), denoting the number of test cases.

Each case starts with a blank line. Then there will be 9 lines, each containing 9 characters denoting the board as described. Empty places will be marked by a '.'.

## 输出

For each case, print the case number in a single line. Then print the solution in 9 lines with 9 characters in each line.

## 样例输入

1
.46...9..
.3.1.....
.2..6..85
...87....
6...3...4
....14...
79..5..3.
.....2.4.
..2...61.

## 样例输出

Case 1:
146528973
835197462
927463185
459876321
618235794
273914856
794651238
361782549
582349617

[提交][状态]