## LeetCode: Check Valid Sudoku
Sudoku is a popular puzzle involving a 9×9 grid that is divided into nine 3×3 subgrids. The objective is to fill the grid with digits so that each column, each row, and each of the nine 3×3 subgrids contain all of the digits from 1 to 9. This LeetCode problem challenges you to write a function that checks if a given 9×9 grid is a valid Sudoku puzzle.
### Understanding the Problem
Before diving into the solution, let’s clarify the constraints and requirements:
– The grid is a 9×9 2D array.
– The numbers in the grid are from 1 to 9.
– A number must not appear in the same row, column, or 3×3 subgrid more than once.
### Solution Overview
The solution involves iterating through the grid and checking each row, column, and 3×3 subgrid for duplicates. If any duplicates are found, the Sudoku is invalid.
### Implementation
Here’s a step-by-step breakdown of the implementation:
1. **Iterate through the grid**: Loop through each cell in the 9×9 grid.
2. **Check rows and columns**: For each cell, check the corresponding row and column to ensure no duplicates are present.
3. **Check 3×3 subgrids**: Use the cell’s coordinates to determine which 3×3 subgrid it belongs to and check for duplicates within that subgrid.
“`python
def isValidSudoku(board):
for i in range(9):
for j in range(9):
num = board[i][j]
if num != ‘.’:
# Check row
for x in range(9):
if x != j and board[i][x] == num:
return False
# Check column
for y in range(9):
if y != i and board[y][j] == num:
return False
# Check 3×3 subgrid
start_row = i – i % 3
start_col = j – j % 3
for x in range(3):
for y in range(3):
if (x != (j – j % 3) or y != (i – i % 3)) and board[x + start_row][y + start_col] == num:
return False
return True
“`
### FAQs
**Q: Can a valid Sudoku grid have empty cells?**
A: Yes, a valid Sudoku grid can have empty cells represented by ‘.’.
**Q: What if the input grid is not a 9×9 matrix?**
A: If the input grid is not a 9×9 matrix, the function will return `False` immediately since the size requirement is not met.
**Q: How do I handle overlapping rows and columns?**
A: The nested loops ensure that we only compare cells within the same row, column, or subgrid. If a cell is part of more than one group, it will be checked multiple times, which is acceptable.
**Q: Can this function handle grids with non-numeric characters?**
A: The function assumes that the input grid contains only numeric characters (1-9) or empty cells (‘.’). If the grid contains non-numeric characters, the function will return `False`.
**Q: Is this solution efficient?**
A: The solution is efficient with a time complexity of O(1) since the grid size is fixed at 9×9. However, it may seem like it has a higher complexity due to the nested loops, but the constant factor of the grid size ensures linear time complexity.
By following this solution and understanding the FAQs, you should be well-equipped to tackle the “Check Valid Sudoku” problem on LeetCode.
