L15. Sudoko Solver | Backtracking

Подписаться 623 тыс.

Просмотров 253 тыс.

50% 1

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

Опубликовано:

11 май 2021

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 316

@takeUforward 3 года назад

Instagram for live updates about channel and live sessions: striver_79

@prithvijitbasak 3 года назад

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. 🔥🔥🔥❤️

@pranavgawade1546 3 года назад

Wo sare sudoku boards bharte bharte dimag kharab ho gaya hoga XD

@democratcobra 2 года назад

You are doing one revolutionary work. Word will change and remember your contribution.

@parthsalat 2 года назад

@@democratcobra Er....Which *word* will change?

@aeroabrar_31 Год назад

Lol ! Am i the only one who learnt sudoku games just to solve this problem. 😂

@bhargav1811 Год назад

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 )

@ankitpradhan2499 2 месяца назад

from where can i get the same deciphering technique ?? some resources ?

@swordofgrayskull1530 3 года назад

Hey King take this 👑, it belongs to you now.

@studyonline3236 Год назад

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.

@akku5529 Год назад

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)

@sudhirdharmadhikari1938 Год назад

Very true. That is an important point

@chirags2711 Год назад

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.

@parthhh3589 8 месяцев назад

yes@@chirags2711

@satyamsrivastava. 3 года назад

I heard u many times saying u r bad at drawing bt this suduko board is literally very artistic

@Abhishek-yy3xg 3 года назад

Yesterday I was trying to understand Sudoku for this problem. And here you come with perfect explanation. Thank you 🙂

@freshcontent3729 3 года назад

what is the TC for this ques ? please explain , please help me , thanks..

@TonyStark-ct8xd 2 года назад

@@freshcontent3729 for each empty box, we have 9 choices (1-9), therefore maximum tc is 9^N*N, where N is dimension of grid.

@sanketatmaram 2 года назад

Best Explanation and consistent logic over all recursion backtracking question in the series. Great work

@shastriamisha 2 года назад

The best explanation on YT for this problem. I can never forget the logic ever :) Thank you

@TheAditya-zt9pb 2 месяца назад

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

@ayanSaha13291 3 месяца назад

bro, I salute your patience! I never have seen such an explanation for the problem! Thanks a lot.

@RonitChattopadhyay 3 года назад

Appreciate the effort that you have put to explain this problem.

@shiwamsinha7076 2 года назад

thanks a lot, sir for boosting my confidence that i can do programming by just applying common sense

@SahilSharma-vl9rk 2 года назад

Woah thanks for this bro :) I literally never understood this problem and finally after watching your video I understood it completely.

@unibrow9384 2 года назад

Thanks a lot, haven't seen anyone explain so well and in such detail ! ^_^

@suyashmishra6946 Год назад

Hella understood man. Ig the most tricky part of this question was to check for 3*3 matrix, that you explained really well.

@sunnykumarpal9679 2 года назад

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.

@nitunsingh6986 2 года назад

Superb Explanation Bhaiya . I know how much efforts u put to come with a beautiful content .Hats off for u

@kirannagulakonda3443 2 года назад

Really appreciate your efforts brother, took time but really happy to solve the question just by watching intuition.

@shaleen9434 Год назад

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

@zaidmujahid3885 2 года назад

Best explanation for sudoku solver on RU-vid 💯

@preetamkumar838 2 года назад

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 RU-vid. Thanks a lot for making such complex things easier to understand.

@cinime Год назад

Understood! Super amazing explanation as always, thank you very much!!

@kashishshukla23 2 года назад

Great explanation!! Really appreciate your efforts

@trooperzooper6092 10 месяцев назад

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!

@naveentata 2 года назад

Great explanation!.Thank you. Can you also please make a video on this backtracking leetcode question? "1240. Tiling a Rectangle with the Fewest Squares"

@kalidass6531 3 года назад

Thank you for this wonderful explanation!.

@Tomharry910 Год назад

Brilliant explaination. Great video. Thank you!

@amanbhadani8840 2 года назад

Your videos made questions like this too much easier.

@nareshe2383 2 года назад

Great work, We can also solve this problem with out nested loops by passing row number as parameters to reduce the complexity.

@ka_ka3141 2 года назад

No for iterations it's not possible

@nasim3987 4 месяца назад

@@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)

@ashdeepsingh6785 2 года назад

Understood the concept. Thanks for putting this much effort.

@kritikatyagi4325 Год назад

What a simple solution to such a complex problem hats off to u sir

@prathamsagar5353 Год назад

You are a true king in explaining logic!

@akshaymondal1372 3 года назад

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 .

@fahmidayasmin4923 Месяц назад

The BEST video on this topic in youtube...Thank you!

@parambharti7095 Год назад

Great effort. Very informative. Thanks @Striver.

@studynewthings1727 10 месяцев назад

I understood very well, Thankyou for good explanation.

@samsmith3961 Год назад

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

@AryanSharma-dc4bj Год назад

exactlyy

@philosphize Год назад

Thank you so much for the explanation Learnt alot

@yashwantlalwani Год назад

amazing, really great explanation.

@stith_pragya 3 месяца назад

UNDERSTOOD.....Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

@skilz9525 Год назад

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

@debasishphukon5345 2 года назад

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!

@shaleen9434 Год назад

@mechros4460 Год назад

good note. I was thinking about this as well. Thanks for clearing it up.

@user-ot1rd8hd3d 7 месяцев назад

The best explanation on YT for this problem

@jatinkumar4410 Год назад

Great explanation as always. Can you please explain its time and space complexity...

@shrikkanthsuresh8971 2 года назад

Into my list of greatest tutors.

@harshith6245 3 года назад

Can we pass the indices row and col with matrix in solve() so that we check only the dots next to it?

@ramakrishnakcr4417 5 месяцев назад

thank you🙏 for your work, if we send row number in every recursion that will improve the code execution time further

@itz_me_imraan02 2 года назад

Crystal clear explanation as 🙏

@sanchitakasat 2 года назад

Amazing explaination!!

@cartidise Год назад

Beautifully explained!

@ritikashishodia675 2 года назад

Bhaiya ap great ho..... #below tier3 ki inspiration ho ap.....

@SuvradipDasPhotographyOfficial Год назад

Exceptional explanation, Thanks a lot striver

@sindhusiva4580 2 года назад

can anyoe please tell me...we have to write void function..but we are using boolean .. why we are considering return values??

@riteshadwani9084 Год назад

This guy makes it so easy!

@chinmaykulkarni8062 Год назад

WHT A EXPLANATION !!!! Killed it.....

@Jainam-17-18 Год назад

Can we optimize using a hashmap for row, col and box?

@sumitmaurya4032 2 года назад

really you made it very simeple.. Thanks for this video

@harshal07051995 2 года назад

Thank you very nicely explained

@anushkathakur6531 Год назад

Could you please tell the time and space complexities of both the approaches?

@satendra6200 11 месяцев назад

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

@sushantgupta4757 2 года назад

thank you so much bhaiya you made so many things in easy way

@nopecharon 2 года назад

Just a beautiful explanation. You are legend striver

@shaleen9434 Год назад

@vankshubansal6495 3 года назад

We can also use space to avoid the check right?

@SamPrakashM 5 месяцев назад

Thank you for the wonderful solution keep doing sir

@LearningYouth Год назад

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; }

@AnandBaburajan 2 года назад

Thank you!

@parthsalat Месяц назад

Note: We don't need to write "Else". This is because in the if condition, we are anyways "return"ing

@prikshit8 3 года назад

thank you so much bhaiya. :)

@yativishnoi5110 Год назад

Well explained!!

@shubhambhardwaj8894 3 года назад

Thank you so much brother, please complete the sde sheet 🙏

@thirumalpriyan3528 Месяц назад

awesome explanation

@vinothborn2win 2 года назад

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.

@atjhamit 2 года назад

paste your solution here, and then we can discuss maybe instead of < 9 you may be doing

@VinayKumar-ze2ww Год назад

Mine worked properly

@its_neel_ok Год назад

so basically rec for (1 to 9) check1 , check2 , check3 (for 3 different check function) if yes go with the recursion else i+1

@UttkarshJainmeb Год назад

one doubt i dont understand why cant we use three for loops to find the validity every for loop will do 9 checks and in total 27 checks , here your for loop is doing 3 checks at one iterations so it will also do 27 checks , so can u tell what am i missing here

@DhruvSharma-mh5vf 2 года назад

Very well explained sir

@harshahl6287 Год назад

else board[i][j] = '.'; Can someone explain why this line is needed. If filling the next cell returns a false, we anyway are inside a loop ,so we end up directly checking the next possible character that can be placed at board[I][j]. We don't re enter the if(board[I][j] == '.') condition at all once we enter it the first time

@madhurgusain723 2 года назад

can somebody tell me why is there a second false statement on line number 14. what is its purpose?

@hrushikeshkale68 3 года назад

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

@ishaanarora3279 3 года назад

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

@aaravarya4406 2 года назад

It does.

@thor1626 5 месяцев назад

can we use a hashset to optimize it??

@bhaveshkumar6842 2 года назад

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.

@asutoshghanto3419 2 года назад

no ,it can have many as well but It is a bad puzzle.

@bhaveshkumar6842 2 года назад

@@asutoshghanto3419 Yes, your point is valid but I was talking about a valid Sudoku puzzle

@shaleen9434 Год назад

@user-fl1km1jq1d 10 месяцев назад

Awesome explanation

@sbagul2 Год назад

iterating through 3x3 matrix was awesome

@mrpi230 2 года назад

Great explanation Thank You😀

@shaleen9434 Год назад

@your_name96 2 года назад

can the formula be generalised for any n x m matrix ? or is it valid for square matrices only? According to my calculation for n x m smaller square, for an index [row][col] , for the boxes it should be [k1 + row/m][k2 + col%n] and k1 = n * (row/n) and k2 =m*(col/m) idk .......

@shaleen9434 Год назад

@ronaksiddhpura07 Год назад

@striver best explaination in easy manner

@krribss 2 года назад

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

@anushkachakraborty8635 Год назад

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.

@srivastavkumar5497 Год назад

Great explanation

@varun1017 6 месяцев назад

can we use hashing to check isValid?

@harshjain4009 2 года назад

Anyone please help me with my doubt-- in the solve function, why arent we also passing the row and col on which the value has been filled so that in the next recursion call we can continue after that row and col? (in the solveSudoku() solve can be like this solve(board, 0,0) ).

@ayushidalal5488 Год назад

I have the same doubt

@ankitaakodiya6074 2 года назад

time complexity of this problem ?

@gowthamr6415 Год назад

What is the space and time complexity of this solution?

@abdussamad0348 Год назад

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.

@ravivarmachaluvadi9158 2 года назад

Hi bro can you please tell me what app you are using to write and draw?

@adityan5302 2 года назад

GREAT EXPLANATION :::::)))))

@abhigyansharma9108 2 года назад

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

@amanamanchhabra4157 11 месяцев назад

What is the time complexity for this problem

@Abhijeet-uk9cl 2 года назад

Can someone discuss time complexity of this solution.

@anmolverma075 Год назад

Bhaiya ji , OP explnation!

@feliwx4087 7 месяцев назад

Awesomeee!!

@nishchay_g 2 месяца назад

What will be time complexity for this?

@adityan5302 2 года назад

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)