L15. Sudoko Solver | Backtracking
Вставка
- Опубліковано 11 тра 2021
- Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- Pre-Requisites: Recursion Playlist Videos,
✅Coding Ninjas Discount Link: aff.codingninjas.com/click?o=...
Please Please SUBSKRIIIBEEEEE the new channel: / @striver_79
Problem Link: leetcode.com/problems/sudoku-...
C++/Java Code Efficient: takeuforward.org/data-structu...
---------------------------------------------------------------------------------------------------------------------------
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_cpCourse
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgCourse
---------------------------------------------------------------------------------------------------------------------------
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
✅Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: /
✅ Instagram: /
✅Connect with us: bit.ly/tuftelegram (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #striver #placements
![The moment we stopped understanding AI [AlexNet]](http://i.ytimg.com/vi/UZDiGooFs54/mqdefault.jpg)
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 ?
I heard u many times saying u r bad at drawing bt this suduko board is literally very artistic
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.
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
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.
bro, I salute your patience! I never have seen such an explanation for the problem! Thanks a lot.
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
Thanks a lot, haven't seen anyone explain so well and in such detail ! ^_^
thanks a lot, sir for boosting my confidence that i can do programming by just applying common sense
Appreciate the effort that you have put to explain this problem.
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.
Hella understood man. Ig the most tricky part of this question was to check for 3*3 matrix, that you explained really well.
Woah thanks for this bro :)
I literally never understood this problem and finally after watching your video I understood it completely.
Best explanation for sudoku solver on UA-cam 💯
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
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 UA-cam. Thanks a lot for making such complex things easier to understand.
Superb Explanation Bhaiya . I know how much efforts u put to come with a beautiful content .Hats off for u
Your videos made questions like this too much easier.
Great explanation!! Really appreciate your efforts
Thank you for this wonderful explanation!.
Brilliant explaination. Great video. Thank you!
Understood! Super amazing explanation as always, thank you very much!!
You are a true king in explaining logic!
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!
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
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)
What a simple solution to such a complex problem hats off to u sir
Understood the concept. Thanks for putting this much effort.
The BEST video on this topic in youtube...Thank you!
I understood very well, Thankyou for good explanation.
The best explanation on YT for this problem
UNDERSTOOD.....Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Into my list of greatest tutors.
Thank you so much for the explanation
Learnt alot
WHT A EXPLANATION !!!!
Killed it.....
Great explanation!.Thank you. Can you also please make a video on this backtracking leetcode question? "1240. Tiling a Rectangle with the Fewest Squares"
This guy makes it so easy!
Crystal clear explanation as 🙏
Great effort. Very informative. Thanks @Striver.
Beautifully explained!
amazing, really great explanation.
Amazing explaination!!
Thank you!
Bhaiya ap great ho..... #below tier3 ki inspiration ho ap.....
Thank you very nicely explained
If you know how to solve sudoku, you can start from 4:00
Exceptional explanation, Thanks a lot striver
really you made it very simeple.. Thanks for this video
Note: We don't need to write "Else". This is because in the if condition, we are anyways "return"ing
thank you🙏 for your work, if we send row number in every recursion that will improve the code execution time further
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 .
Thank you for the wonderful solution keep doing sir
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.
thank you so much bhaiya you made so many things in easy way
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
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
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
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
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.
iterating through 3x3 matrix was awesome
thank you so much bhaiya. :)
@striver best explaination in easy manner
Well explained!!
Great explanation as always. Can you please explain its time and space complexity...
Awesomeee!!
Thank you so much brother, please complete the sde sheet 🙏
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;
}
thank you :)
Very well explained sir
Thanks a lot striver :)
GREAT EXPLANATION :::::)))))
Thanks
Awesome explanation
thank you so much
what is the TC for this ques ? please explain , please help me , thanks..
Great explanation
Thank you sooo mcuh :)))) Awesome :}}
Bhaiya ji , OP explnation!
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.
understood!
so basically rec for (1 to 9)
check1 , check2 , check3 (for 3 different check function) if yes go with the recursion else i+1
This is what i needed
Thank you sir
Hare Krishna! Great🙏🙏
understood!!!!!!!!!
Genius!!
this guy is godddddd hatss off man
Great explanation Thank You😀
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
Much hard but beautifully described, understood:)
June'30, 2023 05:48pm
I am impressed .
awesome explanation
Understoooooood!
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
Understood.
Understood 💯💯💯
understood 😇
UNDERSTOOD ...
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.