Valid Sudoku

To determine if a given 9 x 9 Sudoku board is valid, you must ensure that the numbers 1-9 do not repeat in any row, any column, or any of the nine 3 x 3 sub-grids. Here’s a Python method to check the validity of the Sudoku board:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # Check rows
        for row in board:
            nums = [num for num in row if num != '.']
            if len(nums) != len(set(nums)):
                return False

        # Check columns
        for col in range(9):
            nums = [board[row][col] for row in range(9) if board[row][col] != '.']
            if len(nums) != len(set(nums)):
                return False

        # Check 3x3 sub-grids
        for i in range(0, 9, 3):
            for j in range(0, 9, 3):
                nums = [board[x][y] for x in range(i, i + 3) for y in range(j, j + 3) if board[x][y] != '.']
                if len(nums) != len(set(nums)):
                    return False

        return True

Explanation:

  1. Rows: Iterate through each row and collect all the numbers, ignoring the ‘.’ character. If the set of numbers has a different length than the original list, it means there are duplicates, and the Sudoku is not valid.

  2. Columns: The same logic as for rows but applied to columns.

  3. 3x3 Sub-grids: Check all nine 3 x 3 sub-grids by iterating through them with a step of 3. Collect all numbers in each sub-grid and apply the same logic as for rows and columns.

The function returns True if the Sudoku board is valid according to the given rules and False otherwise.

Identifying Problem Isomorphism

“Determine if a 9x9 Sudoku Board is Valid” is an approximate isomorphism for “Valid Sudoku”.

In both problems, we are given a 9x9 Sudoku board, and the goal is to verify whether the given board is a valid Sudoku.

In “Valid Sudoku”, a Sudoku board is considered valid if all rows, columns, and 3x3 sub-boxes contain unique digits, and non-empty cells contain digits from 1 to 9.

Similarly, in “Determine if a 9x9 Sudoku Board is Valid”, the board is considered valid under the same conditions. However, this problem additionally specifies that empty cells are filled with the ‘.’ character.

The commonality is in the goal of verifying the validity of a Sudoku board using similar criteria. However, the slight variation in the representation of empty cells makes the mapping between the problems an approximate one.

They have similar complexities as they both require checking each row, column, and 3x3 sub-box of the Sudoku board. Therefore, neither problem is inherently simpler or more complex than the other.

“Valid Sudoku” involves understanding of the rules of Sudoku and how to apply them to check a given 9x9 grid. Here are 10 problems to prepare for this problem:

  1. Two Sum (LeetCode 1): This problem involves hashing and can help you to learn how to keep track of seen numbers, a skill useful in “Valid Sudoku”.

  2. Contains Duplicate (LeetCode 217): This problem is about finding if an array contains any duplicates which introduces the idea of keeping track of seen elements.

  3. Single Number (LeetCode 136): This problem can help you learn how to deal with numbers in an array where each element appears twice except for one that appears once.

  4. Find All Numbers Disappeared in an Array (LeetCode 448): This problem requires understanding of how to work with arrays and find missing numbers, which is useful in the context of Sudoku.

  5. First Unique Character in a String (LeetCode 387): This problem asks for finding the first non-repeating character in a string and can be solved with a hash map, similarly to “Valid Sudoku”.

  6. Intersection of Two Arrays (LeetCode 349): This problem introduces you to the concept of finding common elements between two arrays, which may aid in understanding how to check rows, columns, and boxes in Sudoku.

  7. Find the Difference (LeetCode 389): This problem can help you practice dealing with characters and their frequencies, a similar concept to checking numbers in Sudoku.

  8. Missing Number (LeetCode 268): This problem involves finding the missing number in an array, which might be useful in the context of a Sudoku problem.

  9. Rotate Array (LeetCode 189): This problem could be helpful for understanding how to manipulate arrays, a necessary skill for solving Sudoku.

  10. Isomorphic Strings (LeetCode 205): This problem involves finding a way to map one string to another, which can help you understand how to map Sudoku row and column indices to box numbers.

1
2
3
4
5
6
7
8
9

class Solution(object):
    def isValidSudoku(self, board):
        res = []
        for i in range(9):
            for j in range(9):
                element = board[i][j]
                if element != '.':
                    res += [(i, element), (element, j), (i // 3, j // 3, element)]
        return len(res) == len(set(res))

Problem Classification

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to 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 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition. Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules.

Example 1:

Input: board = [[“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”]] Output: true Example 2:

Input: board = [[“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”]] Output: false Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8’s in the top left 3x3 sub-box, it is invalid.

Constraints:

board.length == 9 board[i].length == 9 board[i][j] is a digit 1-9 or ‘.’.

Language Agnostic Coding Drills

The code is a solution to the problem of validating a Sudoku board, using the rules of Sudoku. Below are the key elements in this solution that one needs to understand, broken down into the smallest units of learning. They are listed in order of increasing difficulty.

  1. Basic Syntax and Structure: Understand how to define a class and methods, and how to use loops and conditional statements.

  2. Lists and List Manipulation: Learn how to create, add elements to, and manipulate lists.

  3. Basic Data Types: Understand the string and integer data types, and how to check for equality and inequality.

  4. Working with 2D Arrays: Learn how to traverse and access elements of a 2D array (like the Sudoku board in this case).

  5. Tuples: Understand how to create and use tuples. In this case, tuples are used to represent the row, column, and value of each cell in the Sudoku board.

  6. List Comprehension: Understand how to use list comprehension to add elements to a list in a single line of code.

  7. Division Operator: Understand the difference between normal division (/) and floor division (//), as well as when and why to use each.

  8. Sets and Set Operations: Learn how to create sets, and understand the concept of uniqueness in sets. In this case, a set is used to eliminate duplicate elements.

  9. Boolean Operations: Understand how to use boolean operators (==) to compare values and return a boolean result.

  10. Problem-Solving: Understand the rules of Sudoku and how to check for a valid Sudoku solution. Learn to conceptualize the problem and develop an algorithmic solution.

Once the above concepts are understood and can be coded separately, they can be combined to form the final solution to the Sudoku validation problem.

Targeted Drills in Python

  1. Basic Syntax and Structure: Create a class with a method that prints “Hello, World!”.
1
2
3
4
5
6
7

class HelloWorld:
    def print_message(self):
        print("Hello, World!")

# Create an object and call the method
obj = HelloWorld()
obj.print_message()
  1. Lists and List Manipulation: Create a list, add elements to it, and print it.
1
2
3
4
5

list1 = []
list1.append(5)
list1.append(10)
list1.append(15)
print(list1)
  1. Basic Data Types: Check if two strings are equal and print the result.
1
2
3

str1 = 'Python'
str2 = 'Python'
print(str1 == str2)
  1. Working with 2D Arrays: Create a 2D array and print the element at row 2, column 3.
1
2

array2d = [[1,2,3],[4,5,6],[7,8,9]]
print(array2d[1][2])
  1. Tuples: Create a tuple, add elements to it, and print it.
1
2
3

tuple1 = ()
tuple1 = (1, 'two', 3)
print(tuple1)
  1. List Comprehension: Create a list of squares of numbers from 0 to 9.
1
2

squares = [i**2 for i in range(10)]
print(squares)
  1. Division Operator: Divide 7 by 3 using both normal division and floor division, and print the results.
1
2

print(7 / 3)
print(7 // 3)
  1. Sets and Set Operations: Create a set, add elements to it, and print it.
1
2
3
4
5

set1 = set()
set1.add(1)
set1.add(2)
set1.add(3)
print(set1)
  1. Boolean Operations: Compare whether 5 is greater than 3 and print the result.
1

print(5 > 3)
  1. Problem-Solving: Create a drill to understand the rules of Sudoku. Start with a 3x3 Sudoku grid and write a program that checks if it is valid.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def is_valid_sudoku(grid):
    # Checking rows
    for row in grid:
        if len(set(row)) != len(row):
            return False
    # Checking columns
    for column in zip(*grid):
        if len(set(column)) != len(column):
            return False
    return True

grid = [[5, 3, 4], [6, 7, 2], [1, 9, 8]]
print(is_valid_sudoku(grid))

This solution only checks for uniqueness in each row and column but doesn’t check the sub-grids. For the original problem, you’d need to add a check for each 3x3 sub-grid as well. This should be implemented once the learner is comfortable with the concepts explained above.