DiffPush Tier Recursion · Try Out All Combos O(9^m) where m is the blank count · O(1) auxiliary; the board is modified in place (recursion depth <= 81)
A data center encodes its rack access schedule as a 9x9 matrix where each row, column, and 3x3 zone must contain every clearance digit 1-9 exactly once; scheduled cells are fixed and blank cells must be completed. The auditor scans for the next blank, trials each digit that violates no zone, and locks it in before recursing — reverting on contradiction until the matrix fills.
Input: A 9x9 grid of characters, '1'-'9' for filled cells and '.' for blanks; the test input uses 0 for blanks.
Output: The completed grid: a 9x9 character matrix satisfying all three all-different rules.
the given grid is 9 x 9exactly one solution exists for the stored test casesboard values are digits '1'-'9' or blanks ('0' in the test encoding)Input: {"board":[[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: [[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]]
A lightly-blanked board whose completion the verifier re-checks cell by cell against all three rules and the given cells.
Input: {"board":[[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,0,0,8,5,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: "VALID"
The verifier checks the returned board against all three Sudoku rules plus the original givens, rather than trusting a stored grid.