800. Sudoku Solver (Optimized Backtracking)

HardRecursionRecursion

Given a 9×9 Sudoku board (0=empty), determine if it is solvable. Use optimized backtracking with constraint propagation. Return true/false.

Input: A JSON 9×9 2D array.

Output: Return boolean.

Examples

Example 1 
Input: [[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,7,9]]
Output: true
Explanation: Classic solvable Sudoku.
Example 2 
Input: [[5,5,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
Output: false
Explanation: Duplicate 5 in row 0.

Constraints

Asked by

AmazonMicrosoftBloombergGoogleMetaApple
Solve this problem in the editor →