# How to validate a Sudoku board

## Understanding the Efficiency of Sudoku Validation: A Deep Dive into the O(n^2) Time Complexity of Checking Sudoku Boards in Python.

## Table of contents

## 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 validatedaccording 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.

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
seen.add(row)
seen.add(column)
seen.add(block)
return True
```

### Solution Description

`seen = set()`

: Creates an empty set named`seen`

to keep track of numbers that have already appeared in rows, columns, and 3x3 blocks.Two nested loops

`for i in range(9)`

and`for j in range(9)`

iterate through each cell of the 9x9 board.`number = board[i][j]`

: Stores the current cell's value in the variable`number`

.`if number != ".":`

: Checks if the cell is not empty (a dot indicates an empty cell in this context).`row = str(number) + "row" + str(i)`

: Creates a string like`1row0`

to indicate that the number 1 is in row 0.`column = str(number) + "column" + str(j)`

: Creates a string like`1column0`

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

.`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.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)`

.