The Problem

With this article, I will be covering thevalid sudoku Leetcode problem.

Leetcode describes the problem with the following:

Determine if a9 x 9 Sudoku board is valid. Only the filled cells need to be validatedaccording to the following rules :

1. Each row must contain the digits1-9 without repetition.

2. Each column must contain the digits1-9 without repetition.

3. Each of the nine3 x 3 sub-boxes of the grid must contain the digits1-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.

Leetcode ranks this problem as a medium. I think that is an appropriate rating. The solution is feasible but does require some out-of-the-box reasoning.

The Solution

defisValidSudoku(self,board):seen=set()foriinrange(9):forjinrange(9):number=board[i][j]ifnumber!=".":row=str(number)+"row"+str(i)column=str(number)+"column"+str(j)block=str(number)+"block"+str(i/3)+"/"+str(j/3)ifrowinseenorcolumninseenorblockinseen:returnFalseseen.add(row)seen.add(column)seen.add(block)returnTrue

Solution Description

1. seen = set(): Creates an empty set namedseen to keep track of numbers that have already appeared in rows, columns, and 3x3 blocks.

2. Two nested loopsfor i in range(9) andfor j in range(9) iterate through each cell of the 9x9 board.

3. number = board[i][j]: Stores the current cell's value in the variablenumber.

4. if number != ".":: Checks if the cell is not empty (a dot indicates an empty cell in this context).

5. row = str(number) + "row" + str(i): Creates a string like1row0 to indicate that the number 1 is in row 0.

6. column = str(number) + "column" + str(j): Creates a string like1column0 to indicate that the number 1 is in column 0.

7. block = str(number) + "block" + str(i / 3) + "/" + str(j/3): Creates a string like1block0/0 to indicate that the number 1 is in the top-left 3x3 block.

8. if row in seen or column in seen or block in seen:: Checks if any of these strings already exist in theseen set. If so, the board is not valid and the function returnsFalse.

9. seen.add(row),seen.add(column),seen.add(block): Adds the newly created strings to theseen set so that they can be checked against future cells.

10. If all cells are valid, the function returnsTrue, indicating a valid Sudoku board.

Big O Analysis

Assumingn is the side length. We have a double for-loop so that is at leastO(n^2). Inside the nested loops, the operations (like adding to a set, creating strings, and checking for membership in a set) areO(1) operations. Therefore, the overall runtime isO(n^2).

Originally published athttps://blog.seancoughlin.me.