Problem Set
#5
Sudoku Solver
HardAcceptance: 61.8%•ArrayBacktrackingMatrix•MicrosoftAmazonGoogleMetaUberAppleTCS DigitalInfosys DSE
Problem Statement
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the digits
1-9must occur exactly once in each of the93x3sub-boxes of the grid.
The '.' character indicates empty cells.
Note: It is guaranteed that the input board has only one unique solution.
Examples
Example 1
Input:
board = [
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]Output:
[
["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]
]Explanation:
The empty cells are filled such that every row, column, and 3x3 subgrid contains unique digits from 1 to 9.
Constraints
board.length == 9board[i].length == 9board[i][j] is a digit ('1'-'9') or '.'It is guaranteed that the input board has only one solution.
Hints
1
2
3
4
5
6
7
8
9
10
Input board (9x9 character array):