SAMSUNG R and D OA 2022 | Backtracking, Constraint Satisfaction and Grid Based Recursive Search Interview Problem

Problem Statement Given a partially filled 9×9 Sudoku board, fill the empty cells ('.') so that: Each row contains digits 1-9 exactly once. Each column contains digits 1-9 exactly once. Each 3×3 sub-grid contains digits 1-9 exactly once. Return the completed Sudoku board. A valid solution is guaranteed to exist. Example Input [  ["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"] ]