Leetcode Reflections: #36: Valid Sudoku
14 Nov 2023 -
TL;DR: Scroll to the bottom for the code
This one is fairly straightforward, but I always have trouble remembering the trick to it, so here’s a quick post going through it.
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according 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.
The deal here is you’re given a list of lists and you need to check for uniqueness. You need to check that values in each list are unique, excepting the placeholder “.”, and that the values at the same index of each sublist are unique. Rephrased again, values need to be unique in each column and row of the input matrix (list of lists). Checking which square values are in is the real trick here, which I’ll explain later. A brute force approach is totally acceptable here because we’re dealing with a finite input N value. If we were dealing with some kind of meta sudoku of NxN values, we’d have to be a bit more concerned. So, we’re clear to use a nested loop.
To check for uniqueness we can use a dict for each row and column. If we cared to optimize for space we could use one dict for this (by concatentating the index with the column, row, or square prefix for the hash key) but it’s easier to read with three and again we’re dealing with very finite values, so I’m not overly concerned with optimization.
On each cycle of the loop we check if the value is present in the row, column, or square dicts, meaning we’ve seen it before and it is not unique. If we have, the board is invalid and we can return False. If we haven’t, we want to add the value to our dict(s) to represent that the value was seen. But how do we know where the value is in the board? The row and column are easily identified, with i representing the column and j representing the row (or vice versa, keep in mind these are abstractions). Finding the square is trickier: you need to perform floor division on the indices (i.e. i//3, j//3).
The board itself might be a 9x9 grid, but the squares represent a 3x3 grid (i.e. a matrix). Performing floor division divides and rounds down, which conveniently produces a value that could be used to access values in this theoretical matrix. For example (2//3, 5//3) would be (0,1), which would be the first row, second column in our square matrix. We don’t actually need to create this matrix though, we can just represent it through these pair values in our seen dict(s). This is the trick that I always forget: the tuple is necessary to represent the square that a value is a member of. Keeping the “meta-matrix” in mind helps me to remember this. Hopefully writing this post will too.
Solution in Code:
from collections import defaultdict
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
square_seen = defaultdict(list)
col_seen = defaultdict(list)
row_seen = defaultdict(list)
for i in range(9):
for j in range(9):
num = board[i][j]
if num == ".":
continue
if (num in col_seen[i] or
num in row_seen[j] or
num in square_seen[(i//3, j//3)]):
return False
else:
col_seen[i].append(num)
row_seen[j].append(num)
square_seen[(i//3, j//3)].append(num)
return True