3
\$\begingroup\$

The problem statement is as follows:

Sudoku is a game played on a 9x9 grid. The goal of the game is to fill all cells of the grid with digits from 1 to 9, so that each column, each row, and each of the nine 3x3 sub-grids (also known as blocks) contain all of the digits from 1 to 9.

Sudoku Solution Validator

**Write a function that accepts a Sudoku board, and returns true if it is a valid Sudoku solution, or false otherwise. The cells of the input Sudoku board may also contain 0's, which will represent empty cells. Boards containing one or more zeroes are considered to be invalid solutions.

Here is my code which passes all the test cases.

I would like feedback on performance, clarity, and readability. Thank you



def has_valid_rows(rows):
    VALID_ROW = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    for row in rows:
        if 0 in row or set(row) != set(VALID_ROW):
            return False

    return True



def has_valid_columns(columns):
    VALID_COLUMN = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    for column in columns:
        if 0 in column or set(column) != set(VALID_COLUMN):
            return False
    
    return True



def has_valid_subgrids(input_board):
    VALID_SUBGRID = [1, 2, 3, 4, 5, 6, 7, 8, 9]

    top_left_subgrid = input_board[0][:3] + input_board[1][:3] + input_board[2][:3]
    top_middle_subgrid = input_board[0][3:6] + input_board[1][3:6] + input_board[2][3:6]
    top_right_subgrid = input_board[0][6::] + input_board[1][6::] + input_board[2][6::]

    middle_left_subgrid = input_board[3][:3] + input_board[4][:3] + input_board[5][:3]
    middle_middle_subgrid = input_board[3][3:6] + input_board[4][3:6] + input_board[5][3:6]
    middle_right_subgrid = input_board[3][6::] + input_board[4][6::] + input_board[5][6::]

    bottom_left_subgrid = input_board[6][:3] + input_board[7][:3] + input_board[8][:3]
    bottom_middle_subgrid = input_board[6][3:6] + input_board[7][3:6] + input_board[8][3:6]
    bottom_right_subgrid = input_board[6][6::] + input_board[7][6::] + input_board[8][6::]

    subgrids = [top_left_subgrid, top_middle_subgrid, top_right_subgrid, middle_left_subgrid, middle_middle_subgrid, middle_right_subgrid, bottom_left_subgrid, bottom_middle_subgrid, bottom_right_subgrid]

    for subgrid in subgrids:
        if set(subgrid) != set(VALID_SUBGRID) or 0 in subgrid:
            return False

    return True



def validate_sudoku(board):
    rows = board
    columns = zip(*board)
    
    if has_valid_rows(rows) and has_valid_columns(columns) and has_valid_subgrids(board):
        return True

    return False


\$\endgroup\$
3
  • \$\begingroup\$ This is CodeWars' version; it's different to LeetCode 36 in the following ways: Cells are represented as int, not string. Cells may also contain 0's, which will represent empty cells. [But] boards containing one or more zeroes are considered to be invalid solutions. Hence you're complicating your code with the early-termination checks if 0 in row/col/subgrid... Whereas in LeetCode, cells are represented as strings and allowed to be empty (".") \$\endgroup\$
    – smci
    Commented Jun 25, 2023 at 0:47
  • \$\begingroup\$ Oh and something really basic but important for code legibility: the variable name input_board gets used a whole lot, so rename it board or brd (or even b, although that's discouraged). Look how unwieledy the code in your has_valid_subgrids() is. \$\endgroup\$
    – smci
    Commented Jun 25, 2023 at 0:58
  • \$\begingroup\$ When you say "performance", this one is a tradeoff between CPU and memory, so which do you prefer? Currently your approach is to make duplicate copies of the data in each row/col/subgrid; more memory-efficient would be to use Python SliceObjects, and iterators. But you don't really need to duplicate the data, only keep value-counts. A lower-memory alternative with decent CPU performance is to make only one pass over each cell of the input grid, keep 9x9x3 counters for counts of each of the 9 values in each of the 9x3 rows/columns/subgrids, and increment all the counters as you go. \$\endgroup\$
    – smci
    Commented Jun 25, 2023 at 1:04

1 Answer 1

3
\$\begingroup\$

Naming

Your function names has_valid_rows has_valid_columns and has_valid_subgrids are misleading: they imply that a board with any valid row/column/subgrid would return True.

validate_<region> would be a better fit.

Simplification

You can remove the 0 in <region> conditions in your validation methods, as the sets wouldn't be equal if this were True.

Redundancy 1

You define 3 function-level constants (VALID_ROW, VALID_COLUMN and VALID_SUBGRID) to have the same value. Define a single module-level constant instead. And since you ultimately don't need a list but a set, define that constant to be a set: VALID_SET = {1, 2, 3, 4, 5, 6, 7, 8, 9}.

Redundancy 2

has_valid_rows and has_valid_columns are logically identical, only variable names differ. has_valid_subgrids also has similar logic. They could be combined into a single function which could get passed different arguments.

Consistency

You split the board in rows and columns inside of the main function before passing them to the validating methods, but split the board in subgrids inside the has_valid_subgrids method. It would be better to have consistent calling conventions.

Use built-ins

The all built-in methods allows to check if a condition if True for all elements in an iterable, simplifying your various validation methods a bit, and possibly improving performance:

all(set(row) == VALID_SET for row in board)

Return a boolean directly

In your validate_sudoku function, the pattern:

if <condition>:
    return True
return False

can be simplified to:

return <condition>

Extracting subgrids

Hard-coding each subgrid individually is probably not the best way of getting them. Try to use a list comprehension or a loop instead.

\$\endgroup\$
1
  • \$\begingroup\$ Strictly we don't even need to define the constant VALID_ROW/COL/SUBGRID = [1, 2, 3, 4, 5, 6, 7, 8, 9] and compare each row/col/sg to it, at all. We only need to verify that a) the set of values in each row/col/sg has length 9, b) that there are no 0's in the board, and that the board only contains integers 1...9; can do b) in a first pass over board, then do a) and just check that len(set(values in each row/col/sg)) == 9 \$\endgroup\$
    – smci
    Commented Jun 25, 2023 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.