Time Limit: 1000MS |
Memory Limit: 65536K | |

Total Submissions: 5294 |
Accepted: 1578 |

Description

In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example,

. | 2 | 7 | 3 | 8 | . | . | 1 | . |

. | 1 | . | . | . | 6 | 7 | 3 | 5 |

. | . | . | . | . | . | . | 2 | 9 |

3 | . | 5 | 6 | 9 | 2 | . | 8 | . |

. | . | . | . | . | . | . | . | . |

. | 6 | . | 1 | 7 | 4 | 5 | . | 3 |

6 | 4 | . | . | . | . | . | . | . |

9 | 5 | 1 | 8 | . | . | . | 7 | . |

. | 8 | . | . | 6 | 5 | 3 | 4 | . |

Given some of the numbers in the grid, your goal is to determine the remaining numbers such that the numbers 1 through 9 appear exactly once in (1) each of nine 3 × 3 subgrids, (2) each of the nine rows, and (3) each of the nine columns.

Input

The input test file will contain multiple cases. Each test case consists of a single line containing 81 characters, which represent the 81 squares of the Sudoku grid, given one row at a time. Each character is either a digit (from 1 to 9) or a period (used to indicate an unfilled square). You may assume that each puzzle in the input will have exactly one solution. The end-of-file is denoted by a single line containing the word “end”.

Output

For each test case, print a line representing the completed Sudoku puzzle.

Sample Input

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534. ......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3. end

Sample Output

527389416819426735436751829375692184194538267268174593643217958951843672782965341 416837529982465371735129468571298643293746185864351297647913852359682714128574936

Source

#### 'PKU & UVa problems > Original problem' 카테고리의 다른 글

PKU 3074. Sudoku (0) | 2011.04.18 |
---|---|

PKU 3364. Black and white painting (0) | 2011.04.05 |

UVa 628. Passwords (0) | 2011.03.23 |

PKU 3132. Sum of Different Primes (0) | 2011.03.13 |

PKU 2291. Rotten Ropes (0) | 2011.03.10 |

PKU 2181. Jumping Cows (0) | 2011.03.02 |