# How to validate a Sudoku board

## The Problem

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

Leetcode describes the problem with the following:

Determine if a `9 x 9` Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits `1-9` without repetition.

2. Each column must contain the digits `1-9` without repetition.

3. 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.

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

``````    def isValidSudoku(self, board):
seen = set()
for i in range(9):
for j in range(9):
number = board[i][j]
if number != ".":
row = str(number) + "row" + str(i)
column = str(number) + "column" + str(j)
block = str(number) + "block" + str(i / 3) + "/" + str(j/3)
if row in seen or column in seen or block in seen:
return False
return True
``````

### Solution Description

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

2. Two nested loops `for i in range(9)` and `for 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 variable `number`.

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 like `1row0` to indicate that the number 1 is in row 0.

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

7. `block = str(number) + "block" + str(i / 3) + "/" + str(j/3)`: Creates a string like `1block0/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 the `seen` set. If so, the board is not valid and the function returns `False`.

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

10. If all cells are valid, the function returns `True`, indicating a valid Sudoku board.

### Big O Analysis

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