Sudoku Solver Challenge

This challenge asks you to develop an algorithm that can solve a given Sudoku puzzle. A Sudoku puzzle is a 9x9 grid partially filled with numbers, and the goal is to fill the remaining empty cells such that each row, each column, and each of the nine 3x3 subgrids contains all of the digits from 1 to 9 exactly once. Solving Sudoku puzzles is a classic problem that demonstrates backtracking and constraint satisfaction techniques.

Problem Description

You will be given a 9x9 Sudoku board represented as a 2D array (or equivalent data structure). Some cells will contain digits from 1 to 9, while others will be empty. Your task is to fill in all the empty cells (represented by a specific placeholder, e.g., 0 or a dot) with digits such that the Sudoku rules are satisfied. The function should modify the input board in-place or return a solved board.

Key Requirements:

• Valid Solution: The returned board must be a valid Sudoku solution.
• One Solution: It is guaranteed that each puzzle will have exactly one unique solution.
• In-place Modification (Optional): If possible, modify the input board directly rather than creating a new one.

Expected Behavior:

The algorithm should systematically attempt to fill empty cells with valid numbers. If a number leads to a contradiction, it should backtrack and try a different number.

Edge Cases:

• Pre-filled Board: The input board might be fully solved already.
• Empty Board: While not typical for Sudoku challenges, consider how an empty board would be handled (though problem constraints usually prevent this).

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:
[
  [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 (represented by 0) have been filled to satisfy Sudoku rules.

Example 2:

Input:
[
  [1, 2, 3, 4, 5, 6, 7, 8, 9],
  [4, 5, 6, 7, 8, 9, 1, 2, 3],
  [7, 8, 9, 1, 2, 3, 4, 5, 6],
  [2, 1, 4, 3, 6, 5, 8, 9, 7],
  [3, 6, 5, 8, 9, 7, 2, 1, 4],
  [8, 9, 7, 2, 1, 4, 3, 6, 5],
  [5, 3, 1, 6, 4, 2, 9, 7, 8],
  [6, 4, 2, 9, 7, 8, 5, 3, 1],
  [9, 7, 8, 5, 3, 1, 6, 4, 2]
]

Output:
[
  [1, 2, 3, 4, 5, 6, 7, 8, 9],
  [4, 5, 6, 7, 8, 9, 1, 2, 3],
  [7, 8, 9, 1, 2, 3, 4, 5, 6],
  [2, 1, 4, 3, 6, 5, 8, 9, 7],
  [3, 6, 5, 8, 9, 7, 2, 1, 4],
  [8, 9, 7, 2, 1, 4, 3, 6, 5],
  [5, 3, 1, 6, 4, 2, 9, 7, 8],
  [6, 4, 2, 9, 7, 8, 5, 3, 1],
  [9, 7, 8, 5, 3, 1, 6, 4, 2]
]

Explanation: The input board is already a valid Sudoku solution. The solver should return it as is.

Constraints

• The Sudoku board will always be a 9x9 grid.
• The input will be a 2D array (or equivalent) containing integers from 0 to 9.
  • 0 (or a specified placeholder) represents an empty cell.
  • 1-9 represent pre-filled digits.
• The input board will have exactly one unique solution.
• Your solution should aim for reasonable performance, completing within typical competitive programming time limits for Sudoku problems.

Notes

• Consider how you will check if a number is valid for a given cell (i.e., not already present in its row, column, or 3x3 subgrid).
• A common and effective approach for this problem is backtracking. Think about how you would explore possibilities and undo choices if they lead to an invalid state.
• You will likely need helper functions to:
  • Find the next empty cell.
  • Check the validity of placing a number in a cell.
• The 3x3 subgrids can be identified by their top-left corner coordinates. For example, the top-left subgrid spans rows 0-2 and columns 0-2, the top-middle spans rows 0-2 and columns 3-5, and so on.