Bhaiya you are just a mastermind not only by your skills but you know the every bit of doubts that arise in a student's mind. Hats off to your explanation skills. 🔥🔥🔥❤️
Those who can't understand the logic for subgrid part of sudoku can think of like - There are 3 sized rows and columns so we have to do row/3 and column/3 to get what specific subgrid we are in !!! But this will not be enough as we have to traverse whole subgrid also, so we have to add various coordinates like - offset is nothing but first element of subgrid offset(which we can get by row//3 and col//3) + for each of given below (0,0) (0,1),(0,2), (1,0) (1,1),(1,2), (2,0) (2,1),(2,2) offset + (0,0) offset + (0,1) offset + (0,2) offset + (1,0) offset + (1,1) offset + (1,2) offset + (2,0) offset + (2,1) offset + (2,2) For example if we talk about what striver talks about at 19:24 (5,7) position we can get subgrid offset by row offset = 5//3 ==>1 col offset = 7//3 ==> 2 which is second rowth and third column subgrid - | 0,0 | 0,1 | 0,2 | | 1,0 | 1,1 | 1,2 | | 2,0 | 2,1 | 2,2 | The above is all 9 subgrid of sudoku Again back with example we get 1,2 grid and now we have to add all coordinates to traverse that block like (0,0) (0,1),(0,2), (1,0) (1,1),(1,2), (2,0) (2,1),(2,2) for x= 0,0,0,1,1,1,2,2,2 ( extracting all x of above ) for y = 0,1,2,0,1,2,0,1,2 (extracting all y of above ) so basically x = i//3 and y = i%3 for i ranging from 0 to 9 so finally formula is for i=0 to 9- row = 3 * (x//3) + i//3 ==> (offset + 0,0,0,1,1,1,2,2,2 ) col = 3*(y//3) + i % 3 ==> (offset + 0,1,2,0,1,2,0,1,2 )
My suggestion would be to pass on the row number along with the board to solve function, because say you're calling solve(board) [recent insertion done at 6,7], the function again starts from the start(0) row to find an empty cell, but if you'd passed solve(board,row=6) the search starts from the same row as you're sure that there wouldn't be any free cells left in prior rows.
Yes definitely, It will save the iteration of the rows where values are already set. Now you just need to switch to the next row for which you will simply increment the value of row in the function call. I have applied this method, Below the python Implementation of the problem: class Solution: def isValid(self,board,row,col,val): for i in range(9): if (board[row][i] == val): return False if (board[i][col] == val): return False if(board[3*(row//3)+(i//3)][3*(col//3)+(i%3)] == val): return False return True def solve(self,board,row): if (row == 9):return True for col in range(9): if(board[row][col] == '.'): for val in map(str,range(1,10)): if self.isValid(board,row,col,val): board[row][col] = val if self.solve(board,row): return True else: board[row][col] = "." return False return self.solve(board,row+1)
def solveSudoku(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ self.solve(board,0)
It would have mattered more if number of rows/columns was huge. In this question, we only have to do it for 9, so won't really make more than a very very slight difference at all.
I was initially stucked at the place where we have to check whether the sub-matrix is filled from 1-9 or not but the way you have explained it by diving the rows and colums by 3 and adding them to check the all the numbers made me Mind blown ..this is the far best Explanation ,loved it
@@ka_ka3141it is possible python code:class Solution: def isValid(self,k,r,c,board): for i in range(9): if board[i][c]==k: return False if board[r][i]==k: return False if board[3*(r//3)+i//3][3*(c//3)+i%3]==k: return False return True
def func(self,board,r): for i in range(r,9): for j in range(9): if board[i][j]=='.': for k in "123456789": if self.isValid(k,i,j,board): board[i][j]=k if self.func(board,i): return True else: board[i][j]='.' return False return True def solveSudoku(self, board: List[List[str]]) -> None: self.func(board,0)
N queens problem and sudoku solve were not as easy as it seems now after going through your videos. Best thing I have found on TH-cam. Thanks a lot for making such complex things easier to understand.
There are 6,670,903,752,021,072,936,960 possible solvable Sudoku 😅 grids that yield a unique result (that's 6 sextillion, 670 quintillion, 903 quadrillion, 752 trillion, 21 billion, 72 million, 936 thousand, 960 in case you were wondering). That's way more than the number of stars in the universe
I am getting this error when i am submitting my soln in leetcode can anyone please help? AddressSanitizer:DEADLYSIGNAL ================================================================= ==30==ERROR: AddressSanitizer: stack-overflow on address 0x7ffef164fff8 (pc 0x000000345d18 bp 0x7ffef1650010 sp 0x7ffef1650000 T0) ==30==ABORTING
Great Explanation as always! In the formula to check for the subgrid, I was thinking (3*(row/3) + i/3) can be simplified to (row + i/3), but then i figured we cant do this becuase the (row/3) operation will take the floor value. for e.g. if row = 5 row/3 = 5/3 = 1 so now, 3 * (row/3) = 3 But if we directly take row it will be 5 which is wrong!
I am getting this error when i am submitting my soln in leetcode can anyone please help? AddressSanitizer:DEADLYSIGNAL ================================================================= ==30==ERROR: AddressSanitizer: stack-overflow on address 0x7ffef164fff8 (pc 0x000000345d18 bp 0x7ffef1650010 sp 0x7ffef1650000 T0) ==30==ABORTING
Great explanation! but it will only work for board size 9. A separate loop on ' board[3*(row/3) +i/3][3*(col/3) +i%3]==c ' can make it generic for all board size. Python Code: class Solution: def solveSudoku(self, board: List[List[str]]) -> None: N=len(board) for row in range(N): for col in range(N): if board[row][col]==".": for num in range(1,N+1): if(self.isValid(num,row,col,board,N)): board[row][col]=str(num) if(self.solveSudoku(board)): return True else: board[row][col]="." return False return True def isValid(self,num,row,col,board,N): for i in range(N): if str(num) == board[row][i]: return False if str(num) == board[i][col]: return False for i in range(9): if str(num) == board[3*(row//3) +i//3][3*(col//3) +i%3]: return False return True
I really liked this approach. I was thinking how many N can we logically use? i think just 2(4*4 suduko),4(16*16 suduko) because total possible squares and time complexity will not support much beyond that without really intense computational powers.
Great explanation!.Thank you. Can you also please make a video on this backtracking leetcode question? "1240. Tiling a Rectangle with the Fewest Squares"
The above solution Time complexity is about N**2 * 9**(n*n) Python solution : O(N) : 9**(n*n) See only if you find difficulty in building the code m, n = 9, 9 res = [] def possible(x, y, c): x, y = int(x), int(y) for i in range(9): if arr[i][y] == c: return False if arr[x][i] == c: return False if arr[3*(x//3) + i//3][3*(y//3) + i%3] == c: return False return True def solve(row, col): if row == n: return True if col == n: return solve(row+1, 0) if arr[row][col] == ".": for i in range(1, 10): if possible(row, col, str(i)): arr[row][col] = str(i) if solve(row, col + 1): return True else: arr[row][col] = "." return False else: return solve(row, col + 1)
Bhaiya before I was feeling recursion a tough topic but seeing your video now i am enjoying doing recursion thanks lot bahiya for providing such contents.
if self.checkvalid(board,i,j,str(c))==True: board[i][j]=str(c)
if self.solve(board)==True: return True else: board[i][j]='.'
return False
return True
def checkvalid(self,board,row,column,c):
for i in range(9): if board[i][column]==c: return False if board[row][i]==c: return False if board[3*(row//3)+i//3][3*(column//3)+i%3]==c: return False return True
Like I've seen Some other videos of Sudoku solver, and they all just used that formula, and said you can use this, but striver you really helped me understand the formula, And I just wanted to say Thank you!
Approach: 1. traverse the matrix and find the empty place. 2. once we find the empty place than we tried all the numbers from 1 to 9 and check that it is a valid number or not by checking the rules. 3. and we find the correct number for that place than we find for the second empty place in 9 X 9 matrix. 4. for second empty place we repeat the same process and if we doesn't get any number, so we return false. 5. after getting the false from solve(board) function we make all the places empty that we have filled . than try for other member for first empty place. 6. and after all recursive calls we got true, than we have to stop over there only and no need to search for other solutions.
**Addition to this approach**: Adding these optimizations will increase the efficiency much more. 1. We can use hashing to optimize the isValid function. Just 3 hash arrays, of 9x9. One for row, col and boxes. Just put the element to be 1 if its already been added, and a number is valid of its not marked in any of these 3 hashes. So, the iteration reduces to single operation. 2. In the solve function, we are always starting from 0,0 index. Why not call it always from the index from where the next operations should begin. We can pass the index for next calls in the solve function to reduce repeated iterations over filled indexes. here's my accepted leetcode solution: bool recur(int r, int c, vector& row, vector& col, vector& box, vector& board) { // if the col overflows, move to 0th col of next row if(c == 9) { r++; c = 0; } // if the row overflows, this means sudoku is full // this means we have solved the sudoku if(r >= 9) return true; if(board[r][c] != '.') { if(recur(r, c+1, row, col, box, board) == true) return true; } else { for(int i=1; i
the shear amount of effort that must have gone while making this video is certainly commendable... some of the best DSA channel for a reason... gg @takeUforward
Bhaiiii sahabbb vo Box ka idea toh matlab bilkul *Kamal* tha bhai..... I'm just like you not only achieved your dream but helping others also to achieve theirs. *We must protect you at all cost brother* Such amazing explanation... Thankyou so much 🙏🙏🙏 You are indeed a blessing for us man
Nice explanation. Thanks However I looped through the 3x3 matrix and checked the row and column using another variable. I think the time complexity is still same as I'm only looping 9 times. here is the code: bool isSafe(int r, int c, int val, int grid[n][n]) { int idx = 0; int row = 3 * (r/3); int col = 3 * (c/3); for(int i = 0; i < 3; i++) { for(int j = 0; j < 3; j++) { if(grid[idx][c] == val) return false; if(grid[r][idx] == val) return false; if(grid[row+i][col+j] == val) return false; idx++; } } return true; }
for the 3x3 box checking I am still preferring the nested for loop rather than that formula, I know its not efficient but common we only have 9 values to check, so don't think it will make significant difference in runtime
Bhaiya I just love your videos . I have been following u since many months . Can u make videos about different projects and what should we learn while we work on our Ds algo .
I am getting this error when i am submitting my soln in leetcode can anyone please help? AddressSanitizer:DEADLYSIGNAL ================================================================= ==30==ERROR: AddressSanitizer: stack-overflow on address 0x7ffef164fff8 (pc 0x000000345d18 bp 0x7ffef1650010 sp 0x7ffef1650000 T0) ==30==ABORTING
Striver, I am supremely grateful for your content. You're the best! Btw, a given Sudoku puzzle can have only one valid solution unlike what you said at 12:23. But again this video is great just like all your other videos. You are the best!!! I have immense gratitude for your efforts.
I am getting this error when i am submitting my soln in leetcode can anyone please help? AddressSanitizer:DEADLYSIGNAL ================================================================= ==30==ERROR: AddressSanitizer: stack-overflow on address 0x7ffef164fff8 (pc 0x000000345d18 bp 0x7ffef1650010 sp 0x7ffef1650000 T0) ==30==ABORTING
Getting timeout when board.size() & board[0].size() are replaced with 9. I thought it will be faster with hardcoded 9. Any idea why is it timing out with hardcoded value? Isn't it supposed to be faster with hardcoded value? Board length is given as 9 in constraints board.length == 9. BTW, amazing explanation.
Aaapki videos dekhkr smjh aajata hai par 5-10 din baad lagao to phir bhoole bhatke se lgte hai Sir iska bataiye kuch.. Aise to kitne swaaal kitni baari practse krenge ...Bhaiya please any suggestion this is happening with me all a bit difficult ques which i wasn't able to solve myself did by watchng your video.. Like for exampple I did Flatteing question of LL .. I can't solve now w/o any help but at that time when i didi by learning from it stood like its cleared .. i have learned.. PLS REPLYYYYY SIRR
Hey striver I have a question. In a book I read that by studying a topic with a gap makes it stick better in brain ex- Studying Graph today and taking a gap of 2 days and again studying graph. Should I follow it or just take a topic and continue everyday on same topic
yes it definitely happens. For example in my case I take 1 month gap and after again revising the topic I find them easy to code and I feel my thinking skills gets better for that topic after taking that break
If we are not able to understand then see this u will get idea def is_safe(row,colm,desire_number,board): #staraight colm. for i in range(len(board)): if board[i][colm]==desire_number: return False #straight row. for i in range(len(board[0])): if board[row][i]==desire_number: return False #that particular grid. for i in range(row-row%3,((row-row%3)+3)): for j in range(colm-colm%3,((colm-colm%3)+3)): if board[i][j]==desire_number: return False return True def sudoko_solver(board): for row in range(len(board)): for colm in range(len(board[0])): if board[row][colm]==0: for random_value in range(1,10): if is_safe(row,colm,random_value,board): board[row][colm]=random_value if sudoko_solver(board): #this is because suppose u filled all left cells and for current single cell u were not able to fill any value then in that case obviously u did some mistake in past, now in else block that error will resolved by assigning 0 to that most recent cell then its update and call for next, suppose if sudoko was not solvable then it will go to the cell where all the values were not possible from there it will return and your function call will be end by returning false. return True else: board[row][colm]=0 return False # i tried all the possible but didnt get any ans. return True #all rows and cols are get filled. l1=[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] for i in range(len(l1)): for j in range(len(l1[i])): if l1[i][j]!=".": l1[i][j]=int(l1[i][j]) else: l1[i][j]=0 sudoko_solver(l1) for i in l1: print(i)
@UC0VKgG09oGGMBR3D9YhILqw In each probe of the 9^n possibilities, time to check if it is valid to place in the board is O(c). So in total the time complexity is 9^n*O(c) ~ O(9^n). The recurrence relation is: T(n) = 9*T(n-1) + O(1), which evaluates to 9^n
@@7akon I think it should be 81^(n+1). Reason: for every blank space, we are checking all the digits (1-9) and for every digit, we are checking whether it will be valid or not which is again a loop of 9. So Logically the number of iterations per blank space would be 81. But since we are going through the entire board of characters (i.e a matrix of 9x9 = 81) thus the total TC should be O(81*(81^n)) = O(81^(n+1))
@@sparshsharma6068 Let's get one thing right off the bat, in isValid(), the steps to check if a cell is valid is not going to be just 9, but rather more than 9, because you're checking both vertically, horizontally and in a 3x3 grid. This amounts to some constant 'c'. This is the key point in calculating the time complexity. For a particular cell where we have 9 choices, each of these 9 choices will be looped in with our constant O(c). In time complexity analysis, we don't factor in the steps to our isValid() but analyze its asymptotic behavior, and asymptotically speaking, it will always perform in constant time, hence satisfying the recurrence relation T(n) = 9*T(n-1) + O(1). If the recurrence relation is not intuitive enough, for each cell, we have 9 possibilities and in each of these possibilities we're invoking isValid() which takes 'c' (We don't say 9 because as I said, we're analyzing the asymptotic behavior). Thus for a cell, the TC is O(9*c). For n cells it is (9*c)^n which is 9^n * c^n which is asymptotically equivalent to 9^n
@@sourabhchoudhary7289 😆hii tumko kese bhul sakte he Kitne no. Video pe ho me segment tree tak agaya hu abhi pher se pura series ko dekhunga And I recommend luv ka competitive coding series dekho sare doubts clear ho jaenge😉
Instagram for live updates about channel and live sessions: striver_79
Bhaiya you are just a mastermind not only by your skills but you know the every bit of doubts that arise in a student's mind.
Hats off to your explanation skills. 🔥🔥🔥❤️
Wo sare sudoku boards bharte bharte dimag kharab ho gaya hoga XD
You are doing one revolutionary work. Word will change and remember your contribution.
@@democratcobra Er....Which *word* will change?
Lol ! Am i the only one who learnt sudoku games just to solve this problem. 😂
Those who can't understand the logic for subgrid part of sudoku can think of like -
There are 3 sized rows and columns so we have to do row/3 and column/3 to get what specific subgrid we are in !!! But this will not be enough as we have to traverse whole subgrid also, so we have to add various coordinates like -
offset is nothing but first element of subgrid
offset(which we can get by row//3 and col//3)
+ for each of given below
(0,0) (0,1),(0,2),
(1,0) (1,1),(1,2),
(2,0) (2,1),(2,2)
offset + (0,0)
offset + (0,1)
offset + (0,2)
offset + (1,0)
offset + (1,1)
offset + (1,2)
offset + (2,0)
offset + (2,1)
offset + (2,2)
For example if we talk about what striver talks about at 19:24 (5,7) position
we can get subgrid offset by
row offset = 5//3 ==>1
col offset = 7//3 ==> 2
which is second rowth and third column subgrid -
| 0,0 | 0,1 | 0,2 |
| 1,0 | 1,1 | 1,2 |
| 2,0 | 2,1 | 2,2 |
The above is all 9 subgrid of sudoku
Again back with example we get 1,2 grid and now we have to add all coordinates to traverse that block
like
(0,0) (0,1),(0,2),
(1,0) (1,1),(1,2),
(2,0) (2,1),(2,2)
for x= 0,0,0,1,1,1,2,2,2 ( extracting all x of above )
for y = 0,1,2,0,1,2,0,1,2 (extracting all y of above )
so basically x = i//3
and y = i%3 for i ranging from 0 to 9
so finally formula is
for i=0 to 9-
row = 3 * (x//3) + i//3 ==> (offset + 0,0,0,1,1,1,2,2,2 )
col = 3*(y//3) + i % 3 ==> (offset + 0,1,2,0,1,2,0,1,2 )
from where can i get the same deciphering technique ?? some resources ?
good job, well explained.. intuition behing 3*offset?
this really helps thanks
I heard u many times saying u r bad at drawing bt this suduko board is literally very artistic
Yesterday I was trying to understand Sudoku for this problem. And here you come with perfect explanation. Thank you 🙂
what is the TC for this ques ? please explain , please help me , thanks..
@@freshcontent3729 for each empty box, we have 9 choices (1-9), therefore maximum tc is 9^N*N, where N is dimension of grid.
My suggestion would be to pass on the row number along with the board to solve function, because say you're calling solve(board) [recent insertion done at 6,7], the function again starts from the start(0) row to find an empty cell, but if you'd passed solve(board,row=6) the search starts from the same row as you're sure that there wouldn't be any free cells left in prior rows.
Yes definitely, It will save the iteration of the rows where values are already set. Now you just need to switch to the next row for which you will simply increment the value of row in the function call. I have applied this method, Below the python Implementation of the problem:
class Solution:
def isValid(self,board,row,col,val):
for i in range(9):
if (board[row][i] == val):
return False
if (board[i][col] == val):
return False
if(board[3*(row//3)+(i//3)][3*(col//3)+(i%3)] == val):
return False
return True
def solve(self,board,row):
if (row == 9):return True
for col in range(9):
if(board[row][col] == '.'):
for val in map(str,range(1,10)):
if self.isValid(board,row,col,val):
board[row][col] = val
if self.solve(board,row):
return True
else:
board[row][col] = "."
return False
return self.solve(board,row+1)
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
self.solve(board,0)
Very true. That is an important point
It would have mattered more if number of rows/columns was huge. In this question, we only have to do it for 9, so won't really make more than a very very slight difference at all.
yes@@chirags2711
Hey King take this 👑, it belongs to you now.
@@shambhavisrivastava2340 Not for you
I was initially stucked at the place where we have to check whether the sub-matrix is filled from 1-9 or not but the way you have explained it by diving the rows and colums by 3 and adding them to check the all the numbers made me Mind blown ..this is the far best Explanation ,loved it
Best Explanation and consistent logic over all recursion backtracking question in the series. Great work
The best explanation on YT for this problem. I can never forget the logic ever :) Thank you
Great work, We can also solve this problem with out nested loops by passing row number as parameters to reduce the complexity.
No for iterations it's not possible
@@ka_ka3141it is possible python code:class Solution:
def isValid(self,k,r,c,board):
for i in range(9):
if board[i][c]==k:
return False
if board[r][i]==k:
return False
if board[3*(r//3)+i//3][3*(c//3)+i%3]==k:
return False
return True
def func(self,board,r):
for i in range(r,9):
for j in range(9):
if board[i][j]=='.':
for k in "123456789":
if self.isValid(k,i,j,board):
board[i][j]=k
if self.func(board,i):
return True
else:
board[i][j]='.'
return False
return True
def solveSudoku(self, board: List[List[str]]) -> None:
self.func(board,0)
N queens problem and sudoku solve were not as easy as it seems now after going through your videos. Best thing I have found on TH-cam. Thanks a lot for making such complex things easier to understand.
thanks a lot, sir for boosting my confidence that i can do programming by just applying common sense
Hella understood man. Ig the most tricky part of this question was to check for 3*3 matrix, that you explained really well.
There are 6,670,903,752,021,072,936,960 possible solvable Sudoku 😅 grids that yield a unique result (that's 6 sextillion, 670 quintillion, 903 quadrillion, 752 trillion, 21 billion, 72 million, 936 thousand, 960 in case you were wondering). That's way more than the number of stars in the universe
in the observable universe*
Really appreciate your efforts brother, took time but really happy to solve the question just by watching intuition.
I am getting this error when i am submitting my soln in leetcode
can anyone please help?
AddressSanitizer:DEADLYSIGNAL
=================================================================
==30==ERROR: AddressSanitizer: stack-overflow on address 0x7ffef164fff8 (pc 0x000000345d18 bp 0x7ffef1650010 sp 0x7ffef1650000 T0)
==30==ABORTING
Appreciate the effort that you have put to explain this problem.
Great Explanation as always!
In the formula to check for the subgrid, I was thinking (3*(row/3) + i/3) can be simplified to (row + i/3), but then i figured we cant do this becuase the (row/3) operation will take the floor value.
for e.g.
if row = 5
row/3 = 5/3 = 1
so now, 3 * (row/3) = 3
But if we directly take row it will be 5 which is wrong!
I am getting this error when i am submitting my soln in leetcode
can anyone please help?
AddressSanitizer:DEADLYSIGNAL
=================================================================
==30==ERROR: AddressSanitizer: stack-overflow on address 0x7ffef164fff8 (pc 0x000000345d18 bp 0x7ffef1650010 sp 0x7ffef1650000 T0)
==30==ABORTING
good note. I was thinking about this as well. Thanks for clearing it up.
Best explanation for sudoku solver on TH-cam 💯
man your please is very polite and your content has depth, you are genius and good. hope to meet you up.
Great explanation! but it will only work for board size 9. A separate loop on ' board[3*(row/3) +i/3][3*(col/3) +i%3]==c ' can make it generic for all board size.
Python Code:
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
N=len(board)
for row in range(N):
for col in range(N):
if board[row][col]==".":
for num in range(1,N+1):
if(self.isValid(num,row,col,board,N)):
board[row][col]=str(num)
if(self.solveSudoku(board)):
return True
else:
board[row][col]="."
return False
return True
def isValid(self,num,row,col,board,N):
for i in range(N):
if str(num) == board[row][i]: return False
if str(num) == board[i][col]: return False
for i in range(9):
if str(num) == board[3*(row//3) +i//3][3*(col//3) +i%3]: return False
return True
I really liked this approach. I was thinking how many N can we logically use? i think just 2(4*4 suduko),4(16*16 suduko) because total possible squares and time complexity will not support much beyond that without really intense computational powers.
What a simple solution to such a complex problem hats off to u sir
The best explanation on YT for this problem
bro, I salute your patience! I never have seen such an explanation for the problem! Thanks a lot.
Great explanation!.Thank you. Can you also please make a video on this backtracking leetcode question? "1240. Tiling a Rectangle with the Fewest Squares"
The above solution Time complexity is about N**2 * 9**(n*n)
Python solution : O(N) : 9**(n*n)
See only if you find difficulty in building the code
m, n = 9, 9
res = []
def possible(x, y, c):
x, y = int(x), int(y)
for i in range(9):
if arr[i][y] == c: return False
if arr[x][i] == c: return False
if arr[3*(x//3) + i//3][3*(y//3) + i%3] == c: return False
return True
def solve(row, col):
if row == n: return True
if col == n: return solve(row+1, 0)
if arr[row][col] == ".":
for i in range(1, 10):
if possible(row, col, str(i)):
arr[row][col] = str(i)
if solve(row, col + 1):
return True
else:
arr[row][col] = "."
return False
else: return solve(row, col + 1)
solve(0, 0)
yes , n^2 is unnecessary increase in complexity.
Bhaiya before I was feeling recursion a tough topic but seeing your video now i am enjoying doing recursion thanks lot bahiya for providing such contents.
Superb Explanation Bhaiya . I know how much efforts u put to come with a beautiful content .Hats off for u
UNDERSTOOD.....Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
If anyone's looking for [ python ] solution, then here it is
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
self.solve(board)
def solve(self,board):
for i in range(9):
for j in range(9):
if board[i][j]=='.':
for c in range(1,10):
if self.checkvalid(board,i,j,str(c))==True:
board[i][j]=str(c)
if self.solve(board)==True:
return True
else:
board[i][j]='.'
return False
return True
def checkvalid(self,board,row,column,c):
for i in range(9):
if board[i][column]==c:
return False
if board[row][i]==c:
return False
if board[3*(row//3)+i//3][3*(column//3)+i%3]==c:
return False
return True
Your videos made questions like this too much easier.
You are a true king in explaining logic!
Great explanation!! Really appreciate your efforts
I understood very well, Thankyou for good explanation.
Like I've seen Some other videos of Sudoku solver, and they all just used that formula, and said you can use this, but striver you really helped me understand the formula, And I just wanted to say Thank you!
Approach:
1. traverse the matrix and find the empty place.
2. once we find the empty place than we tried all the numbers from 1 to 9 and check that it is a valid number or not by checking the rules.
3. and we find the correct number for that place than we find for the second empty place in 9 X 9 matrix.
4. for second empty place we repeat the same process and if we doesn't get any number, so we return false.
5. after getting the false from solve(board) function we make all the places empty that we have filled . than try for other member for first empty place.
6. and after all recursive calls we got true, than we have to stop over there only and no need to search for other solutions.
Nice Work Bro
@@yashkhatwani3198 thanks
Bhaiya ap great ho..... #below tier3 ki inspiration ho ap.....
**Addition to this approach**:
Adding these optimizations will increase the efficiency much more.
1. We can use hashing to optimize the isValid function.
Just 3 hash arrays, of 9x9.
One for row, col and boxes.
Just put the element to be 1 if its already been added, and a number is valid of its not marked in any of these 3 hashes. So, the iteration reduces to single operation.
2. In the solve function, we are always starting from 0,0 index.
Why not call it always from the index from where the next operations should begin. We can pass the index for next calls in the solve function to reduce repeated iterations over filled indexes.
here's my accepted leetcode solution:
bool recur(int r, int c, vector& row, vector& col, vector& box, vector& board) {
// if the col overflows, move to 0th col of next row
if(c == 9) {
r++;
c = 0;
}
// if the row overflows, this means sudoku is full
// this means we have solved the sudoku
if(r >= 9) return true;
if(board[r][c] != '.') {
if(recur(r, c+1, row, col, box, board) == true)
return true;
}
else {
for(int i=1; i
Bhaishbbb "itna dimaag kaha se laate ho", Amazing approach and wo matrix check to bs gazab hi he . Lg rha he service se product switch ho jayega.
the shear amount of effort that must have gone while making this video is certainly commendable... some of the best DSA channel for a reason... gg @takeUforward
exactlyy
Bhaiiii sahabbb vo Box ka idea toh matlab bilkul *Kamal* tha bhai..... I'm just like you not only achieved your dream but helping others also to achieve theirs.
*We must protect you at all cost brother*
Such amazing explanation... Thankyou so much 🙏🙏🙏
You are indeed a blessing for us man
If you know how to solve sudoku, you can start from 4:00
Amazing explanation... But still I'll take 3 business days to completely absorb this concept
Great effort. Very informative. Thanks @Striver.
Nice explanation. Thanks
However I looped through the 3x3 matrix and checked the row and column using another variable. I think the time complexity is still same as I'm only looping 9 times.
here is the code:
bool isSafe(int r, int c, int val, int grid[n][n])
{
int idx = 0;
int row = 3 * (r/3);
int col = 3 * (c/3);
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
if(grid[idx][c] == val) return false;
if(grid[r][idx] == val) return false;
if(grid[row+i][col+j] == val) return false;
idx++;
}
}
return true;
}
for the 3x3 box checking I am still preferring the nested for loop rather than that formula, I know its not efficient but common we only have 9 values to check, so don't think it will make significant difference in runtime
@striver best explaination in easy manner
Great explanation as always. Can you please explain its time and space complexity...
Understood the concept. Thanks for putting this much effort.
Bhaiya I just love your videos . I have been following u since many months . Can u make videos about different projects and what should we learn while we work on our Ds algo .
understood, thanks for the great explanation
Thank you so much brother, please complete the sde sheet 🙏
WHT A EXPLANATION !!!!
Killed it.....
Into my list of greatest tutors.
Woah thanks for this bro :)
I literally never understood this problem and finally after watching your video I understood it completely.
Understood! Super amazing explanation as always, thank you very much!!
Just a beautiful explanation. You are legend striver
I am getting this error when i am submitting my soln in leetcode
can anyone please help?
AddressSanitizer:DEADLYSIGNAL
=================================================================
==30==ERROR: AddressSanitizer: stack-overflow on address 0x7ffef164fff8 (pc 0x000000345d18 bp 0x7ffef1650010 sp 0x7ffef1650000 T0)
==30==ABORTING
Striver, I am supremely grateful for your content. You're the best! Btw, a given Sudoku puzzle can have only one valid solution unlike what you said at 12:23. But again this video is great just like all your other videos. You are the best!!! I have immense gratitude for your efforts.
no ,it can have many as well but It is a bad puzzle.
@@asutoshghanto3419 Yes, your point is valid but I was talking about a valid Sudoku puzzle
I am getting this error when i am submitting my soln in leetcode
can anyone please help?
AddressSanitizer:DEADLYSIGNAL
=================================================================
==30==ERROR: AddressSanitizer: stack-overflow on address 0x7ffef164fff8 (pc 0x000000345d18 bp 0x7ffef1650010 sp 0x7ffef1650000 T0)
==30==ABORTING
amazing, really great explanation.
Tere bhai bhai jaisa koi hardich nai h
Note: We don't need to write "Else". This is because in the if condition, we are anyways "return"ing
Beautifully explained!
thank you🙏 for your work, if we send row number in every recursion that will improve the code execution time further
Amazing explanation!!
You should be teacher full time. Sadly teachers don't earn as much. Hope you do this full time after earning enough money in your job.
Crystal clear explanation as 🙏
Thank you for the wonderful solution keep doing sir
Getting timeout when board.size() & board[0].size() are replaced with 9. I thought it will be faster with hardcoded 9. Any idea why is it timing out with hardcoded value? Isn't it supposed to be faster with hardcoded value? Board length is given as 9 in constraints board.length == 9. BTW, amazing explanation.
paste your solution here, and then we can discuss
maybe instead of < 9 you may be doing
Mine worked properly
Thank you so much for the explanation
Learnt alot
Brilliant explaination. Great video. Thank you!
Thanks a lot, haven't seen anyone explain so well and in such detail ! ^_^
Exceptional explanation, Thanks a lot striver
iterating through 3x3 matrix was awesome
so basically rec for (1 to 9)
check1 , check2 , check3 (for 3 different check function) if yes go with the recursion else i+1
Aaapki videos dekhkr smjh aajata hai par 5-10 din baad lagao to phir bhoole bhatke se lgte hai Sir iska bataiye kuch.. Aise to kitne swaaal kitni baari practse krenge ...Bhaiya please any suggestion this is happening with me all a bit difficult ques which i wasn't able to solve myself did by watchng your video.. Like for exampple I did Flatteing question of LL .. I can't solve now w/o any help but at that time when i didi by learning from it stood like its cleared .. i have learned.. PLS REPLYYYYY SIRR
This guy makes it so easy!
Present Sir !
Much hard but beautifully described, understood:)
June'30, 2023 05:48pm
Thank you sir
Hare Krishna! Great🙏🙏
thank u so much striver !
thank you so much bhaiya you made so many things in easy way
idk why this solution is able to pass only 4 testcases in leetcode ?but great explanation!!
please discuss time complexity
Great explanation
Hey striver I have a question.
In a book I read that by studying a topic with a gap makes it stick better in brain ex- Studying Graph today and taking a gap of 2 days and again studying graph.
Should I follow it or just take a topic and continue everyday on same topic
yes it definitely happens. For example in my case I take 1 month gap and after again revising the topic I find them easy to code and I feel my thinking skills gets better for that topic after taking that break
It does.
thank you so much bhaiya. :)
For isValid(), can't we just use a hashmap for O(1) lookup?
At max it will have n^3 elems
Thank you for this wonderful explanation!.
Continue from: 7:35
Very well explained sir
If we are not able to understand then see this u will get idea
def is_safe(row,colm,desire_number,board):
#staraight colm.
for i in range(len(board)):
if board[i][colm]==desire_number:
return False
#straight row.
for i in range(len(board[0])):
if board[row][i]==desire_number:
return False
#that particular grid.
for i in range(row-row%3,((row-row%3)+3)):
for j in range(colm-colm%3,((colm-colm%3)+3)):
if board[i][j]==desire_number:
return False
return True
def sudoko_solver(board):
for row in range(len(board)):
for colm in range(len(board[0])):
if board[row][colm]==0:
for random_value in range(1,10):
if is_safe(row,colm,random_value,board):
board[row][colm]=random_value
if sudoko_solver(board): #this is because suppose u filled all left cells and for current single cell u were not able to fill any value then in that case obviously u did some mistake in past, now in else block that error will resolved by assigning 0 to that most recent cell then its update and call for next, suppose if sudoko was not solvable then it will go to the cell where all the values were not possible from there it will return and your function call will be end by returning false.
return True
else:
board[row][colm]=0
return False # i tried all the possible but didnt get any ans.
return True #all rows and cols are get filled.
l1=[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
for i in range(len(l1)):
for j in range(len(l1[i])):
if l1[i][j]!=".":
l1[i][j]=int(l1[i][j])
else:
l1[i][j]=0
sudoko_solver(l1)
for i in l1:
print(i)
Excellent brother , please complete sde sheet fast.
what is the TC for this ques ? please explain , please help me , thanks
@@freshcontent3729 9^n where n is the blank spaces.
@UC0VKgG09oGGMBR3D9YhILqw In each probe of the 9^n possibilities, time to check if it is valid to place in the board is O(c). So in total the time complexity is 9^n*O(c) ~ O(9^n).
The recurrence relation is: T(n) = 9*T(n-1) + O(1), which evaluates to 9^n
@@7akon I think it should be 81^(n+1). Reason: for every blank space, we are checking all the digits (1-9) and for every digit, we are checking whether it will be valid or not which is again a loop of 9. So Logically the number of iterations per blank space would be 81. But since we are going through the entire board of characters (i.e a matrix of 9x9 = 81) thus the total TC should be O(81*(81^n)) = O(81^(n+1))
@@sparshsharma6068 Let's get one thing right off the bat, in isValid(), the steps to check if a cell is valid is not going to be just 9, but rather more than 9, because you're checking both vertically, horizontally and in a 3x3 grid. This amounts to some constant 'c'. This is the key point in calculating the time complexity. For a particular cell where we have 9 choices, each of these 9 choices will be looped in with our constant O(c). In time complexity analysis, we don't factor in the steps to our isValid() but analyze its asymptotic behavior, and asymptotically speaking, it will always perform in constant time, hence satisfying the recurrence relation T(n) = 9*T(n-1) + O(1).
If the recurrence relation is not intuitive enough, for each cell, we have 9 possibilities and in each of these possibilities we're invoking isValid() which takes 'c' (We don't say 9 because as I said, we're analyzing the asymptotic behavior). Thus for a cell, the TC is O(9*c). For n cells it is (9*c)^n which is 9^n * c^n which is asymptotically equivalent to 9^n
Bhaiya ji , OP explnation!
Thanks bro 🧡 you deserve 1M subs! backtracking has always been a nightmare. This explanation was epic and it helped me a lot🔥
what is the TC for this ques ? please explain , please help me , thanks
@@freshcontent3729 It's exponential since recursion is involved
You Are My Inspiration Striver
this guy is godddddd hatss off man
I am impressed .
Thank you very nicely explained
23:00 logic impp maths
U can make anyone fall in love with coding😁🙏
hey remember me?
😁
@@sourabhchoudhary7289 😆hii tumko kese bhul sakte he
Kitne no. Video pe ho me segment tree tak agaya hu abhi pher se pura series ko dekhunga
And I recommend luv ka competitive coding series dekho sare doubts clear ho jaenge😉
@@rahul_ji21 me abhi heaps p hu bro
Exam aagai yr....
Vese konse year m ho bro?
@@sourabhchoudhary7289 2yr 4th sem tum?
@@rahul_ji21 2nd SEM😄
Any suggestions for me
As you are senior