N-Queens, N-Knights, Sudoku Solver (LeetCode) - Backtracking Questions
VloĆŸit
- Äas pĆidĂĄn 21. 07. 2024
- Here we cover some important #backtracking questions such as N-Queens, N-Knights, Sudoku Solver (LeetCode), including theory + code + tips on how to solve such problems in various ways.
Take part in the learning in public initiative! Share your learnings on LinkedIn and Twitter with #DSAwithKunal & don't forget to tag us!
đ Resources
- Join Replit: join.replit.com/kunal-kushwaha
- Complete Java DSA playlist: âą Java + DSA + Interview...
- Code, Assignments, & Notes: github.com/kunal-kushwaha/DSA...
âĄïž Connect with me: kunalkushwaha.com
=========================================
Timestamps:
0:00:00 Introduction
0:00:57 Q1 : N-Queens Problem
0:02:13 How to determine if a problem is of recursion and backtracking?
0:20:12 Code for N-Queens Problem
0:32:05 Complexity Analysis (Correction: Linear Recurrence Relation Method*)
0:37:48 How to eliminate for loops?
0:39:01 Q2 : N-Knights Problem
0:44:05 Code for N-Knights Problem
0:52:51 Q3 : Sudoku Solver Problem (LeetCode)
1:06:47 Code for Sudoku Solver Problem
1:07:38 Correction: board[row][i] == num
1:10:47 Code for Sudoku Solver Problem
1:17:03 Complexity Analysis for Sudoku Solver Problem
1:18:20 Outro
#recursion #placement #dsa #interviews
Kunal, your series helped me with motivation. I got selected in Morgan Stanley as QA. Thanks brother. đ
That's amazing, congratulations and thank you!
Hi Kunal, first of all a very big thank you. I have started watching your CZcams videos of Data structures #DSAwithKunal. I am an experienced guy with 4 years of Automation Testing experience. I started leetcode when you solved that recursion problem. Your Strings video helped me with clearing concepts. Every QUALITY ASSURANCE guy/girl must also watch this series. #Dsforall
Currently completing Recursion series.
Thanks man. A big thank you đ
Bro when will we get all the video..
@@Anic10 but bro how is DSA helping in field of QA ?
@@pythonenthusiast9292 Yes bro.. Big tech companies like Arcesium, Browserstack have coding rounds prior to interviews. In interviews they ask easy to medium problems on linked list,stacks ,queue and time complexities. So to become SDET DSA is necessary.
In the isSafe method in the If condition you have written "board[row][col] == num" which is only checking that element for 9 times instead of checking all the forward elements, it is not giving error but the sudoku is not properly solved, instead there should be
"board[row][i] = num" which will check other elements in the row as well and then the sudoku will be solved properly.
Yeah I also noticed that đ ...
Yeah, you are right, bro!
You are right i was not able to solve sudoku and this took me 1 hour to find this issue . thanx bro
I saw that too, like in the first row 6 & 2 are getting repeated, and same issue with other rows
Wow . The best Recursion playlist ever made (according to me) . As you said I have drawn Recursive tree for each and every problem. Yes it was time consuming and it was really tough in the beginning but later on I started enjoying it. So I will suggest whoever thinking to follow this DSA playlist can follow it blindly.
Wow, thank you!
I am a beginner in coding can I watch it for good jobs?
I think it is in Java.
@@rahuls8613 yes
We can't thank this guy enough. Such an amazing course so far.
Don't know how people can dislike this kind of content. This is the finest and most premium course I have found not only youtube even the paid contents. And this DSA course is not just a course its like we are feeling the DSA. Making my imagination strong and new thought process starts growing. THANK. YOU KUNAL BHAI YOU ARE LIT!!
Kudos to you, man. I genuinely found a mentor I can follow. I can certainly see light on the other end of the road, and you're helping me to walk each step - carefully guiding me through every obstacle upfront. Thank you, Kunal. I sincerely mean it.
Just completed the Recursion playlist ( July 10th, 2023 ). Going to complete a few "Assignments" from your GitHub repo and dive deep into the DSA playlist afterwards.
I'll keep you updated with that playlist too xD Thanks again, man. If I could, I would've given you the warmest hug (with a box of biriyani of course XD )
The way you broke down the ideas and made them so simple to understand and apply is "very next level" :)
I have now watched all the 11 videos in your recursion series playlist. I am now able to understand how recursion functions - how the recursion calls go onto the stack and how it comes out. I feel more confident with recursion which I used to dread earlier and was a nightmare for me. I now feel happier when I learn to code. Your videos has helped hundreds of thousands of struggling students like me and in the coming time hopefully will help millions of students learning to code around the world. Thank you for sharing your knowledge and wisdom so generously and freely with us without even charging a penny. Hope the seeds of learning that you have sowed in our lives, abounds and brings much happiness and success in your life as well. Wishing you the very best life has to offer. Thank you so much, Sensei đđđ
Youâre welcome
@@KunalKushwaha Hey Kunal, We need the content of Dynamic Programming, Tree and Graph algorithms from you. Please do it as soon as possible.
Hi Kunal,
Your recursion playlist on CZcams has been a game-changer for me! I have learned so much and have been able to apply the concepts in my coding projects. I would love to see a new lecture series on dynamic programming. I know it's a challenging topic, but I trust your teaching style and explanations to make it more approachable. Keep up the great work!
its been more than 3 months since i completed the serie and i still rwatch again , thank youuuu !!!!!
This is by far the best playlist on youtube. Your teaching is truly amazing. Are you planning on making any videos explaining dynamic programming?
Yes, the best Recursion Playlist with progression to Backtracking concept so Far . Thanks Kunal, Keep up the good work .
This is literally the best recursion playlist I ever laid my eyes on. You made sure to cover all the doubts that could arise in one's mind. Your explanations were just amazing and you made these problems look so simple. Thanks for all your hard work and dedication. đ
hi bro can you help me
thankyou you made coding so interesting its approx. one month following your dsa series i purchased some courses but i never got intuitions then i skipped coding now i am getting intuitions as well
The best I have ever seen... Felt happy from depths of my heartđđ
Just minor correction, while checking the row for the number instead of board[row][col]== num, just replace col with [i] . It will fix the duplication issue.
I always feared of recursion and data structures even after started this bootcamp..i gave up at recursion videos at first but later i thought of giving a shot and now im here and can say that i really loved learning recursion and the way you are teaching is awesome. Looking forward for more videos on this playlist.
complete this playlist and dynamic programming as soon as possible brother you are worth for every student iam loving your content so much
Thank you soo much for this awesome content, bro ! I learned a lot from in these series !!!
Thank you so much for this amazing recursion series!
By far the best recursion playlist i've ever seen
I just eagerly wait for your video kunal â€ïž
Great job man, you make it look so easy
Watching this video after completing the previous videos, Just makes it so easy to understand ! Thank you so much for teaching this for FREE!
Glad it was helpful!
I was feeling sleepy but This video is refreshing
Never tried to solve a sudoku in my entire life. Now just writing a program for sudoku to solve itself đ....
Came a long way đ
Thanks @Kunal Kushwaha
Best of luck!
@@KunalKushwaha Thank you Bro !!!
it took me 2 days ,but i didn't give up, I SOLVED it, Revised everything I was struggling with
awesome
kunal, waiting for your sliding window concepts badly. Thank you so much for this playlist.
Thank you soo much for this awesome content, bro ! I learned a lot from in these series !! please make series of dynamic programming
Once again best quality teaching as always. Thankyou Kunal â€ïž
Thanks for sharing! More to come!
@KunalKushwaha +1 mistake, which no one spotted for suprise.
In nKnights , the loop goes on stops at the last row and last col of matrix , instead of running through it .
Your code -
row
For 3 x 3 there should be 36 ans instead we have 25 ans since last box is missed in output.
Check output there will be no knight in last box in any of those ans
I was waiting for this!! When is dp lecture will be out
i dont know why i am not getting this backtracking questions .but still thank you kunal you created the base of recursion .
U made it very easy to me tqq kunalâ€â
Thank you bhiya you are a gem
Is this a Java + DSA course or a Netflix series? đ€ Honestly, it's been so captivating from start to finish with such thorough explanations. Thank you for making learning so enjoyable! Can't wait for more!
â€ïžâ€ïž amazing content
never thought i could literally understand these concepts thankyou for teachingđđ
u are insane, ty for the content!
Soon you will receive silver play button âđ
@kunal i cound not get the time complexity of n queens with akra bazi , but i was able to get it through substitution method , request you to made one video where there are functions like T(n) = N*T(N-1) + g(n) like this
100k supersoon đ
Damn this course is lit đ„đ„đ„
Hi Kunal, Where can I find the Dynamic Programing videos..??
Great explanation đ
Thank you !!
Excellent video kunal thanks for explaining in such great way .
I think there is a small mistake in the N knight problem a knight can move in 8 different direction instead of four so I think 8 checks will be required .
Thanks again for the awesome content.
If I am placing a knight at (r, c), where will the previous knight could be present? (keep in mind that we are travelling one row after another)
Will the previously placed knights be present on the same row as ours and on the rows before it?
OR
Can a previously placed knight be found on the rows below our current (r, c)? If not, then do we really have to check for r+1 and r+2 rows?? THINK ABOUT IT.....
â@@shubhamrawat3984 thanks for the explanation
No brother your concern is legit, I also had same question but think about it deeply we are starting from first row to bottom and while doing down we have to only check for upwards as there's no any knight placed already in the end rows whereas in upper rows we placed and came down.
15:50 Simple way to find diagonal left and diagonal right
// diagonal left
int r = row;
for(int c = col;c>=0&&r>=0;c--,r--){
if(board[r][c]){
return false;
}
}
// diagonal right
r = row;
for(int c = col;c=0;c++,r--){
if(board[r][c]){
return false;
}
}
i wrote the same thing in my rough before he explained other approach
Recursion done !
Thank You â€
Tanmay how was this playlist? Is this playlist good as compared to Striver's playlist??
Kunal, we cannot solve backtracking problems by Akra-Bazzi method as the coefficient of T(N-1) is not constant (it's N). I searched for it on the internet and found no solution with Akra-Bazzi method.
Thank You:)
For SUDOKU Solver : Is the if condition under //row check correct? I think it should be if(board[row][i] == num) return false. What is your opinion Kunal?
I guess it is row, i, where it should remove duplicates.
That's exactly i am thinking about... @ 1:07:51 - there is no dependency of if condition on the loop... so how it check row's element..... it should be if ( board [row] [i] == num)
and the output was also incorrect .... there were a repeating elements is the row....
Yes u r right karan....there should be board[row][i]
Thanks a lot for solution, i just stuck there. And thought where was the actual problem. Thank u.
The backtracking is not correctly applied in Sudoku solver. Everytime return true in solve(board) hits and since if waa running before that else condition gets untouched making it no application of backtracking. Am I thinking right if anyone can tell??
hey kunal , can we start doing the hard section in your git hub assignment ( after completing recursion series) ?
Yes
36:35 Really i can assure the code kunal sir does...if you understand it then ... there's no shorter version you can find...
I think that for the isValid function if the N- Knights there should be 4 more conditions which are : (r+2,c+1) ,(r+2,c-1),(r+1,c+2) &(r+1,c-2) .
Yeah, total 8 conditions are there.
We are moving gradually downwards from each row. So while checking, we need to make sure that the new location doesn't have any knights positioned above that row, as the below rows will be empty at that stage. Hence, he didn't include all 8 conditions. Even if he did add the remaining 4 conditions, they'll always return true as they would contain false at that stage.. Hope you got the concept.
If I am placing a knight at (r, c), where will the previous knight could be present? (keep in mind that we are travelling one row after another)
Will the previously placed knights be present on the same row as ours and on the rows before it?
OR
Can a previously placed knight be found on the rows below our current (r, c)? If not, then do we really have to check for r+1 and r+2 rows?? THINK ABOUT IT.....
bro we only check for the above rows whle placing the knight because we are placing them from top to bottom
Its like we both have eye contact, if i can see you then you can definitely see me .
Same in knights we only check on top or above moves because there is no knights below . Both has same moves if they intercepted
Hey can someone explain me the emptyLeft thing in the sudoku solver question
can anyone explain why is it O(n^2) in recurrance relation ofr NQueens
Ki Kunal, There should be 8 - cases for N Knights Problem under "isValid" Method or I'm doing something wrong ?
we check for the previous rows only, so I guess 4 cases is all
Can u PLZZ tell when will this course will be finished â€ïžâ€ïžâ€ïž
this video deservs million of views by the by
when dp lectures coming in your channel
can anyone please tell me how much of this course is left ?
Hi kunnal, I watched all videos in recursion is too good. I like your way of approaching the problem.
In this video "Sudo solver" output is "incorrect". Because of minor mistake in "isSafe method -> Checking the row".
It's correct I just did a typo with variable in hurry which is mentioned in timestamps
@@KunalKushwaha Yes noticed đ
mind blowing.......
ek ek line of code kya kar raha hai har question me , sab samajh aa gaya đđđđ
that was the plan
how your sudoko code is correct bro.
look at your answer in the very first row 2 is coming twice at 4 and 6 index
can someone help me out, why do we "return" at line 16 in the N Knights problem (timestamp: 46:12), would be highly appreciated
here col=n(board length) if you dont return the code will go aheaa and run issafe function for c=n which will return true and obv u cant place knight there because its not the part of the board also then col will keep on increasing and we dont have any base case for c>n resulting in infinite loop.
HOPE U UNDERSTAND :)
Sir, understanding videos very very well but coming to assignment facing lot of difficulty
check leetcode video i made
that count method only work in java ..in c++ you have to pass it in the argument by reference.
can anybody tell me what is n in 9^n*n in Sudoku solver complexity analysis ?
sure, because we have n*n cells, also we can have 1 to 9 nums in each of cell, so 1st cell --> 9, 2nd cell--> 9, ... so on till n^2 cell --> 9, hence 9^(n*n)
in sudoku output, in first row 2 and 6 are repeating and in second row 9 is repeating and many more
39:39 knight is respectable
good lecture
at 1:16:57 the value 6 and 2 are repeated ??
Let Go!!!
small error in checking if the number is in the row. The condition should be if(board[row][i] == num)
yes because of which 2 is getting repeated in the output..have u seen that?? đ
Right!!
Hey, This is great but in some row same digits are repeated in sudoko solver.
Ho could have earn lacks thru this ...
Thaxxx bruu
Always free for all.
Sir ji plz ye course band mat karna or delete bhi nahi karna đ„șđđ€©
@KunalKushwaha
34:14 i believe this isn't linear recurrence relation with constant coefficient to use method you taught us in time complexity lecture,
ig this could be solved using substitution method, but i could not end up with precise answer like that of yours as O(N! + N^3) = O(N!)
i solved it in the following way
T(n) = n*T(n-1) + O(n^2)
=> T(n) - n*T(n-1) = O(n^2)
=> (T(n))/n! - (T(n-1))/(n-1)! = O(n^2)/n!
=> (T(n))/n! = â x from 2 to n (x/(x-1)!)]
== â x from 2 to n (1/(x-2)!)]
by Maclaurin's expansion for e,
=> (T(n))/n! = O(e)
=> T(n) = O(n!*e)
ignoring constant terms, we get
T(n) = O(n!)
can you please help me with elaborating more on your approach to solve this and get O(N! + N^3) as solution?
else if someone who know kunal's approach please reply here, I'd really appreciate
Thanks!
I code in JavaScript and Python, will watching the lectures from the beginning be beneficial?
Will the Theory be beneficial?
yes
100k soon
Hey kunal just wanted to ask by when will this course be completed?
By the end of this month ig
@@muneebahmed3993 This is only the limitation of this course . It's already 6 months sep-feb but still we have covered only one data structure linked list
@@muneebahmed3993 This is only the limitation of this course . It's already 6 months sep-feb but still we have covered only one data structure linked list
Sir please make a video on Gsoc and its guidelines and how prepare for it.. whats skills and roadmap required.. pleaseđđâš.... Please sir...make a guideline...
You dsa bootcamp isâ€ïžđ„
Sure I will
Bro do some videos on Linkedlist,stacks
coming very soon after OOP
@@KunalKushwaha thanks bro đ
in the out 2 row -- 9 come 2 times, is this true
You r the bestđ„đ„
static int queens(boolean[][] board,int row){
if (row==board.length){
display(board);
System.out.println();
return 1;
}
int count=0;
for (int col=0;col=0;c--,r--){
if (board[r][c]){
return false;
}
}
r=row; //right
for (int c=col;c=0;c++,r--){
if (board[r][c]){
return false;
}
}
return true;
}
hi bro, actually i am stuck, my program doesnt print ans in matrix, instead it print this in one single vertical line, can you help
Can someone tell me how to code N-knight using 2 variable as done in N-queen one.
using for loop
Tq sir
Kindly check soduko solver output again ....that is giving wrong output . first line has repeated 2,row 6 has 1 repeated, 9th row has 6 repeated and so no...
Bro opps concepts
next
it feels u were looking answer for sudoku solver problem and then explaining.
great video bhai, but at 1:16:52 the sudoku was not solved correctly.
Edit : Solved vertically but not horizantally, what a coincidence
đ„Č
Great eye man. I think the first check should be board(row)(i) == num, isn't it?
@@serveshchaturvedi2034 yes that's correct,lđđ»
52:50 bookmark
at 1:07:47 i think board[i][col] should be there i am confused how he solve that using that only
I think you're right, cuz if we put board[row][col] everytime then how will it work...
The answer of sudoku solver that you're getting is wrong.
đ
cant queen do the steps of knight?
The code for sudoku solver is giving wrong answer in video itself please provide the correct solution and code for it
Sudoku is not solved in the final printed answer
Enjoyed all your recursion videos except for this one, it seemed like u didn't really prepare before making this important video, it felt u were not really explaining but reading, but the other recursion videos helped me a lot so I am really grateful to u for making this series