Sudoku Solver
Advanced Backtracking DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Solving an incomplete 9x9 Sudoku puzzle using a backtracking algorithm, Backtracking, Recursion, Matrices, Two-dimensional Array Traversal, Time Complexity, Space Complexity, In-place Algorithm, constraints, backtracking, search space optimization, matrix traversal, recursion, validation, Backtracking Constraints.
Given a 9x9 incomplete Sudoku board, solve it such that it becomes a valid Sudoku. A valid Sudoku board must satisfy the following properties: 1. All rows must be filled with numbers (1 9) exactly once. 2. All columns must be filled with numbers (1 9) exactly once. 3. Each of the nine 3x3 sub boxes within the grid must be filled with numbers (1 9) exactly once. The character '.' indicates an empty cell. Note: There can exist many valid arrangements of numbers. The solution can provide any one of them. Input Format: A 9x9 character matrix board representing the incomplete Sudoku board. Output Format: Modify the input board in place to contain a valid Sudoku solution. Example: Input: Output: Explanation: The empty cells are filled with the possible numbers. There can exist many such arrangements of numbers. The above solution is one of them. Each row, column, and 3x3 sub box contains numbers 1 9 exactly once.