Valid sudoku

 I have never played sudoku before even though i like analyzing chess games and love to play chess, i couldnt convince myself that sudoku is interesting for one valid reason, to solve it you need to bruteforce :-) That means no logic or strategy involved. Anyway the leetcode problem i decided to solve is about validating sudoku, i already solved this before with the help of youtube video, now i am going to try to solve it by myself

Problem statement

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.

 

Let the brute forcing begin...

 

For each valid value, we need to check the entire row, entire column, and the adjacent 3 x 3 matrix

there is a pretty cool way to just do this by iterating from 0 to 8

something like 

```

def check(row, column):

     for i in range(9):

         grid[row][i] // this loops through the entire row

         grid[i][column] // this loops through entire column

```

 but i dont want to go this way, i did like this previous time, so i wanted to try something else, instead of looping through entire row and column, we could maintain a set for rows and a set for colums where each element is (row_index or col_index, value)

before iterating each valid value we check if it exists on the set, if it exists the board is invalid since the numer should not be duplicated.

 

This brings us to interesting next question, how do we know if the value exist on adjacent cells, the more interesting question would be how do you know if its an adjacent cell ?

we can maintain a hashset of (row/3, col/3) as the key  and use the value 

row/3 and col/3 is not magic, we are trying to normalize the row value and column value

so decided to create three hashsets

one to map row -> value

other to map col -> value

other to map (row/3, col/3) -> value

 lets jump in to the code

class Solution:

def isValidSudoku(self, board: List[List[str]]) -> bool:

row_set, col_set, square_set = set(), set(), set()

for r in range(9):

for c in range(9):

if board[r][c] != ".":

val = int(board[r][c])

if (r, val) in row_set or (c, val) in col_set or (r//3, c//3, val) in square_set:

return False

row_set.add((r, val))

col_set.add((c, val))

square_set.add((r//3, c//3, val))

return True