Sudoku

Time limit1sMemory limit128 MB

Summary
Fill the five empty cells (marked 0) in a 9x9 Sudoku grid so every row, column, and 3x3 box contains the digits 1 through 9 exactly once.
Level

Medium5 of 10

Topics
Backtracking, Implementation, Brute force, Recursion
Solved
No attempts yet

Problem

Sudoku is played on a 9×99 \times 9 grid that is divided into nine 3×33 \times 3 boxes. You must fill the grid with the digits 11 through 99 so that every digit appears exactly once in each row, exactly once in each column, and exactly once in each 3×33 \times 3 box.

A puzzle is given as a 9×99 \times 9 grid in which a filled cell holds its digit and an empty cell holds 00. Given such a puzzle, write a program that solves it.

Input

The first line contains the number of test cases. Each test case consists of 99 lines describing a Sudoku grid; each line is a string of 99 digits from 00 to 99, where 00 marks an empty cell. Every test case contains exactly five 00s.

Output

If the grid cannot be completed without breaking the Sudoku rules, print

Could not complete this grid.

Otherwise, print the solved grid over 99 lines using the same format as the input. Print a blank line between consecutive test cases. Whenever a grid can be solved, the input is guaranteed to have a unique solution.

Examples1

  1. Example 1

    Input
    2
481253697
267948105
539671204
654389712
908704563
173562849
702136958
315897426
896425371
481253697
267948105
539671284
654289710
908704562
173562849
702136958
315897426
896425371
    Expected output
    481253697
267948135
539671284
654389712
928714563
173562849
742136958
315897426
896425371

Could not complete this grid.