Sudoku Board
You are given a
9x9 Sudoku board with some of the cells filled in. Your task is to solve the given Sudoku board and find a valid solution. If there are multiple valid solutions, you can print any of them.A Sudoku board is a
9x9 grid divided into nine 3x3 sub-grids. Each cell in the grid can contain a number from 1 to 9. The goal of Sudoku is to fill in the empty cells of the board in such a way that each row, each column, and each 3x3 sub-grid contains all the numbers from 1 to 9 without repetition.Input
The input consists of 9 lines, each containing 9 space-separated integers representing the state of the Sudoku board. The given numbers range from
1 to 9, and an empty cell is represented by 0.Output
Print nine lines, each containing nine space-separated integers representing the solution to the given Sudoku board. If there are multiple valid solutions, you can print any of them.
Examples
Input | Output |
9 8 0 0 0 0 3 2 1
0 0 0 0 0 3 0 8 5
0 0 1 0 2 0 0 0 0
0 0 0 5 0 7 0 0 0
0 0 4 0 0 0 1 0 0
0 9 0 0 0 0 0 0 0
5 1 0 0 0 0 0 7 3
0 0 2 0 1 0 0 0 0
8 6 0 0 4 0 0 0 9 | 9 8 7 6 5 4 3 2 1
2 4 6 1 7 3 9 8 5
3 5 1 9 2 8 7 4 6
1 2 8 5 3 7 6 9 4
6 3 4 8 9 2 1 5 7
7 9 5 4 6 1 8 3 2
5 1 9 2 8 6 4 7 3
4 7 2 3 1 9 5 6 8
8 6 3 7 4 5 2 1 9 |
Constraints
Time limit: 50 seconds
Memory limit: 512 MB
Output limit: 1 MB