Hi everybody,
Today I am gonna solve a validator about Sudoku. Sudoku is a very common game all over the world. Sometimes some candidates get Sudoku validation or about the other Sudoku versions questions in their interviews.
Sudoku Rules
If we have like this Sudoku, we need to rule some rules.
grid = [ [8, 3, 5, 4, 1, 6, 9, 2, 7],
[2, 9, 6, 8, 5, 7, 4, 3, 1],
[4, 1, 7, 2, 9, 3, 6, 5, 8], [5, 6, 9, 1, 3, 4, 7, 8, 2],
[1, 2, 3, 6, 7, 8, 5, 4, 9],
[7, 4, 8, 5, 2, 9, 1, 6, 3], [6, 5, 2, 7, 8, 1, 3, 9, 4],
[9, 8, 1, 3, 4, 5, 2, 7, 6],
[3, 7, 4, 9, 6, 2, 8, 1, 5]]
Every row shouldn’t be non-repeatable
- Every column shouldn’t be non-repeatable
- Every 3 part in the Sudoku grid shouldn’t be repeatable
We can solve this question by starting the first rule checking row by row :
First, we have every time 9–9 cells. We can iterate every time as a top row and column 9.
Second how to understand non-repeatable numbers in one row. We can use a Set() to solve this problem and for every row and column, we can reset our Set().
Row base checking
hset = set()
for i in range(9):
for j in range(9):
if grid[i][j] in hset:
return False
else:
hset.add(grid[i][j])
hset = set()Column base checking
hset = set()
for i in range(9):
for j in range(9):
if grid[j][i] in hset:
return False
else:
hset.add(grid[j][i])
hset = set()3–3 parts checking
This part is the most difficult part to checking 3 by 3.
First, we need pre generated data range to understand which ranges we will iterate.
grid = [
0 1 2 3 4 5 6 7 80 [8, 3, 5, 4, 1, 6, 9, 2, 7],1 [2, 9, 6, 8, 5, 7, 4, 3, 1],2 [4, 1, 7, 2, 9, 3, 6, 5, 8],3 [5, 6, 9, 1, 3, 4, 7, 8, 2],4 [1, 2, 3, 6, 7, 8, 5, 4, 9],5 [7, 4, 8, 5, 2, 9, 1, 6, 3],6 [6, 5, 2, 7, 8, 1, 3, 9, 4],7 [9, 8, 1, 3, 4, 5, 2, 7, 6],8 [3, 7, 4, 9, 6, 2, 8, 1, 5]]
As seen as in the grid, we need to iterate the first range:
range(0,0) > range(0,3) like a log iterate :
row_range : range(0, 3)
column_range : range(0, 3) i - j : 0 - 0
i - j : 0 - 1
i - j : 0 - 2
i - j : 1 - 0
i - j : 1 - 1
i - j : 1 - 2
i - j : 2 - 0
i - j : 2 - 1
i - j : 2 - 2
After we need to iterate :
row_range : range(0, 3)
column_range : range(3, 6)
i - j : 0 - 3
i - j : 0 - 4
i - j : 0 - 5
i - j : 1 - 3
i - j : 1 - 4
i - j : 1 - 5
i - j : 2 - 3
i - j : 2 - 4
i - j : 2 - 5and 3.
row_range : range(0, 3)
column_range : range(6, 9)
i - j : 0 - 6
i - j : 0 - 7
i - j : 0 - 8
i - j : 1 - 6
i - j : 1 - 7
i - j : 1 - 8
i - j : 2 - 6
i - j : 2 - 7
i - j : 2 - 8and we can continue to iterate this way. If you have seen row_range and column range, you can realize that how we need a pre-generated data range.
We need this data range and we need to iterate every possible case in this range. We will generate a sublist by using these ranges.
[range(0,3), range(3,6), range(6,9)](0,3) > (0,3), (0,3) > (3,6) , (0,3) > (6,9)(3,6) > (0,3), (3,6) > (3,6) , (3,6) > (6,9)(6,9) > (0,3), (6,9) > (3,6) , (6,9) > (6,9)
and our code will be this way :
subs = [range(0,3), range(3,6), range(6,9)]subgrids = []
for x in subs:
for y in subs:
subgrids.append([x,y])for (row_range, column_range) in subgrids:
hset = set()
for i in row_range:
for j in column_range:
if grid[i][j] in hset:
return False
else:
hset.add(grid[i][j])
All code
def sudokuCheck(grid): #edge cases
if not grid:
return False
#rows by rows checking
hset = set()
for i in range(9):
for j in range(9):
if grid[i][j] in hset:
return False
else:
hset.add(grid[i][j])
hset = set()
#cols by cols checking
hset = set()
for i in range(9):
for j in range(9):
if grid[j][i] in hset:
return False
else:
hset.add(grid[j][i])
hset = set()
#3 by 3 check subs = [range(0,3), range(3,6), range(6,9)] subgrids = []
for x in subs:
for y in subs:
subgrids.append([x,y]) for (row_range, column_range) in subgrids:
hset = set()
for i in row_range:
for j in column_range:
if grid[i][j] in hset:
return False
else:
hset.add(grid[i][j])
return True
Thanks
