Sudoku
Time limit2sMemory limit256 MB
Solve a given 9x9 Sudoku puzzle via backtracking and output the lexicographically smallest completed board if multiple solutions exist.
- Level
Medium6 of 10
- Topics
- Backtracking, Matrix, Brute force
- Solved
- No attempts yet
Problem
Sudoku is a number puzzle played on a 9×9 grid. Every row, every column, and each of the nine 3×3 subgrids must contain each digit from 1 through 9 exactly once.
You are given a partially filled Sudoku board. Fill every empty cell and print a completed board.
Input
The board is given in 9 lines. Each line contains 9 digits, and an empty cell is written as 0.
Output
Print the completed Sudoku board in 9 lines. If there is more than one solution, print the one whose 81-character string, formed by reading the rows from top to bottom, is lexicographically smallest.
Constraints
- Every input is a Sudoku puzzle that can be solved within the time limit.
- Time limit: 2 seconds
- Memory limit: 256 MB