Valid Sudoku

 

1. Clarify the problem: Before diving into solving the problem, let's clarify the requirements:

  • We are given a 9x9 Sudoku board, partially filled with digits from 1 to 9.
  • We need to determine if the Sudoku board is valid.
  • A valid Sudoku board satisfies the following rules:
    • Each row must contain the digits 1-9 without repetition.
    • Each column must contain the digits 1-9 without repetition.
    • Each of the nine 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

2. Analyze the problem: To solve this problem, we can iterate through each cell of the Sudoku board and check the validity of each row, column, and 3x3 sub-box. We can use sets to keep track of the digits encountered in each row, column, and sub-box.

3. Design an algorithm: Here is the algorithm to validate a Sudoku board:

  1. Create empty sets row_set, col_set, and box_set to store the encountered digits in each row, column, and 3x3 sub-box.
  2. Iterate through each cell in the Sudoku board:
    • If the current cell is not empty:
      • Check if the digit is already in the corresponding row, column, or sub-box sets. If so, return False as it violates the Sudoku rules.
      • Add the digit to the corresponding row, column, and sub-box sets.
  3. If all cells pass the validation checks, return True, indicating a valid Sudoku board.

4. Explain your approach: The approach involves iterating through each cell of the Sudoku board and maintaining sets to keep track of the digits encountered in each row, column, and sub-box. We check if a digit is already present in the sets corresponding to the current row, column, and sub-box. If a digit violates the Sudoku rules, we return False. Otherwise, if all cells pass the validation checks, we return True.

5. Write clean and readable code:

python
def isValidSudoku(board):
    n = 9

    def validate(nums):
        seen = set()
        for num in nums:
            if num != ".":
                if num in seen:
                    return False
                seen.add(num)
        return True

    for i in range(n):
        row = board[i]
        if not validate(row):
            return False

        column = [board[j][i] for j in range(n)]
        if not validate(column):
            return False

        start_row = (i // 3) * 3
        start_col = (i % 3) * 3
        sub_box = [board[start_row + m][start_col + n] for m in range(3) for n in range(3)]
        if not validate(sub_box):
            return False

    return True

6. Test your code:

python
# Test case 1
board1 = [
    ["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"]
]
print(isValidSudoku(board1))  # True

# Test case 2
board2 = [
    ["8","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"]
]
print(isValidSudoku(board2))  # False

# Test case 3 (Invalid sub-box)
board3 = [
    ["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",".","9","7","9"]  # Invalid sub-box: two 9's in the last row
]
print(isValidSudoku(board3))  # False

7. Optimize if necessary: The solution provided has a time complexity of O(1) since the Sudoku board size is fixed and small (9x9). The space complexity is also O(1) since we are using a constant amount of additional space.

8. Handle error cases: The code assumes that the input Sudoku board is a valid 9x9 grid containing digits from 1 to 9 or empty cells represented by ".". If the input does not meet these requirements, the code may produce incorrect results or raise exceptions. To handle such cases, we can add input validation at the beginning of the function to ensure the input is of the correct format.

Next Post Previous Post