The N Queens Problem using Backtracking/Recursion - Explained
ฝัง
- เผยแพร่เมื่อ 12 ธ.ค. 2018
- Code - backtobackswe.com/platform/co...
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Write a program which returns all distinct nonattacking placements of n queens on an nxn chessboard, where n is an input to the program.
A nonattacking placement of queens is one in which no two queens are in the same row, column, or diagonal.
We will use backtracking to solve this problem.
This can be one of the most confusing topics that you have to learn, expecially if you have shaky foundations in thinking recursively and calculating harder complexities.
Other Well Know Backtracking Problems:
-) Generate The Powerset of An Array (Subsets)
-) Generate All Permutations of A String
Backtracking/Recursion is about following a path to a base case...our target...our answer. If a certain path ends up not meeting our constraints we will backtrack to an earlier state and try something else from there.
The 3 Keys To Backtracking Problems:
Our Choice
-) What choice are we making at each call of the function
-) RECURSION REPRESENTS A DECISION.
-) RECURSION REPRESENTS A CHOICE & its associated state
-) Each function call represents a state. From that state decisions can be made.
Our Constraints
-) What tells us to stop following a certain path that we are searching on?
-) Have we exhausted all possibilities?
Our Goal
-) What is our target?
-) What are we trying to find?
-) These will craft our base cases.
Example: You lost your keys. Where do you go? The most recent place you were. Then the most recent place from there. And so on. Then you go to somewhere else...eventually you find your keys or give up the search.
So for this problem:
Our Choice - Where to place a queen
Our Constraints - The placement must non-attacking
Our Goal - Place n-queens on the chess board
Time and Space Complexities:
Complexity for this problem is tricky.
The time complexity is lower bounded by the number of non-attacking placements because we will be making at least the amount of function calls that it takes to find those placements (meaning we don't even include work done in each call).
No exact form is known for this lower bound as a function of n, but it is conjectured to tend towards n! / (c ^ n) (where c ≈ 2.54) which is super-exponential.
Super exponential growth forms a "J-curve" that grows much faster than exponential functions.
RECURSION REPRESENTS A DECISION.
RECURSION REPRESENTS A DECISION.
RECURSION REPRESENTS A DECISION.
Whether this is a tree or a linked list, etc. When thinking recursively, our function sets forth rules that allows the function to make decisions based on state passed into it
All backtracking is about is that we can return to previous decision points and explore another path that hasn't been taken yet to see if it yields an answer.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is question 16.2 in Elements of Programming Interviews (EPI). - วิทยาศาสตร์และเทคโนโลยี
Table of Contents: (and more info)
Video Setup 0:00 - 0:33
Introducing The N Queens Problem 0:33 - 1:05
What Is Backtracking? 1:05 - 2:15
Further Describing The Problem 2:15 - 3:21
The 3 Keys To Backtracking Problems 3:21 - 5:31
The Code 5:31 - 13:11
Wrap Up 13:11 - 14:09
The N Queens Problem Made Simple. Forgot to explain time complexities, that is in the description. Also, I wish I could've drawn a full diagram of the backtracking but ran out of room on the board. I may make a separate video for that since VISUALS are very key for understanding how these backtracking algorithms work.
you're by far the most enthusiastic person that i've ever seen in this field dude . keep it up !
I was mad lol, because online explanations sucked
@@BackToBackSWE Also, your code for this is the cleanest and clearest that I have seen. I have searched through github and no one has better code for this excersize.
I can tell this explanation is coming from someone who struggled a long time with the concept, because your explanation is so thorough yet accommodating that it is hard not to kind of get it as I follow along.. Thank you so much!
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
This is a brilliant example, and it's evident you care about what you are teaching - which is greatly appreciated and reflected in the quality of the video. Thanks a lot, it helped me get a little bit closer to understanding.
Great. That means a lot. My goal is to make this the premier channel (#1 on TH-cam) for programming interview prep. Teaching is hard and I'm slowly getting better at it.
If you are still not 100% give it a few months and come back. Concepts that are new like this take time to sink in, but once they are internalized they stay for a long time in understanding.
I really like the informalness that you bring while making videos on dense topics, trust me that really helps the viewers 😁
thx
I've never seen someone so excited about algorithms. Great content. Well done!
Hey man, I love the great quality of these videos and the depth to which you explain each topic. I am currently studying for a competitive programming competition and I'm finding your videos to be a great study aid. Keep up the good work!
Nice! Keep it up, you are a beast!
I really love the way you explain, your commitment to understand is amazing, a big thumbs up man!!
These videos have been super helpful for me during my interview prep. Thank you so much!
It is nothing. If you ever have any questions just comment on a video and I can answer them (I check these daily).
I am literally here for you. Although we may not know each other I know exactly what you are going through.
This is why the channel exists and why I do this.
Absolutely love the way this was explained. I've been ramming my head at the wall that is understanding recursion for a bit without much progress, yet this explanation completely changed the way I treat it!!!
great to hear
When you reach the end of this playlist... Backtrack :)
indeed
LOL
You should be proud man! Awesome explanation and passion for the code! Thanks!
thanks
You get the clearest explanation for backtracking I can find on youtube!
thx
Please keep doing more problems, only your video makes me understand N-Queens Problems. Appreciate it!
Amaze! Stay tuned for our upcoming interview prep module with new mentors!
Thank you so much for making this video. I was so confused about where to even start with my backtracking project for class but this helped me so much!
sure
I really feel your enthusiastic when you're making this video. This helps me continue Learning the video. Thank you so much.
haha, sure
These have got to be the only genuinely entertaining coding vids on the internet, love it
ye - i luv the internets
Have watched half a dozen of videos on this ...but only after watching this can I confidently say that I "get it" ..Thanks you so much, you are awesome!!
nice!
I'm watching this channel's video first time but I can say that this man has a passion for what he does, it can be seen in the first couple of minutes.
Welcome to da pardy
I bet there's no one who can explain backtracking problem better than you did. Your video helped me a lot. Thanks!
sure!
Thanks a lot. This was my first LeetCode HARD problem. Gave a much-needed confidence.
this is supper clear, thank you for making these videos
Thanks for this briliant insight to recursion, you explain like a big bro.😃
sure
Wow. You just boiled a hard problem down to 3 simple steps that we can always rely on. Thanks for the video and an awesome explanation.
sure, thanks for coming by
i love this man - he explains everything so well!
Thanks mann....Your explaination is really one of the best out there!!
thanks!
AWW THIS VIDEO WAS POSTED ON MY BIRTHDAY. THANKS FOR THE GIFT MY MAN
nice yo
This is Just Superb, thank you so much Biny for all effort & kindness, in demistyfying this involved problem.
thank u so much. i love how causal and inviting you are
Glad it was helpful! 😄 Also check out our FREE DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
As usual very nice explanation. And a big thanks to your buddy who films all videos religiously.
hahaha, it is a religion at this point
You simplified such a difficult problem to a clean and simplified solution....Amazing!!!
And the github code is commented so well, I didn't find any difficulty understanding it.
Keep up this good work bro...appreciate it!!!
ye, go flourish internet friend
Really good explanation to divide backtracking problems in goals, choice and constraint. Backtracking problems get really easy thinking in this way
yeah
amazingly explained ! Bravo !
Such a great explanation and your energy, it was amazing which really helps in understanding the concept better. GREAT WORK!!
thanks
Amazing video man , thank you so much !!!!!!!!
Great explanation. You guys are awesome. Keep up the good work. Subscribed.
thanks
Awesome explanation. Best video on this topic! Loved it!
thanks
It’s superb analysis ,I have gone through a lot of blogs sites but I couldn’t understand finally I understand thanks a lot ,keep rocking
sure
you are a skinny legend dude. love your videos pls keep it up!! would love to see a vid on strongly connected components/ tarjan algorithm from you
Brilliant explanation.
Hi, Ben. Starting watching your videos during new year holidays was a great idea for me. Before that I was watching different algorithm tutorials on youtube, but it can`t be compared with your effort and explanations. Hope to see more from you, my special wish to your channel is to make more videos of new and latest problems that come from different companies interviews.
It is important for learning because some problems are "classic" and despite of the fact that intuition behind them is still of crucial importance, that would be nice to have some "fresh" problems! Or maybe some variations of older problems...
One more time thank you, i am going to join your coding interview class and keep learning.
Best wishes from Russia,
Ilya
Thanks :)
I love the way you teach!! very helpful
thx
awesome explanation!
Good one! Explained really well!
thx
Awesome explanation. Easy to understand.
thanks
You are awesome!!. Such a lucid explanation!
thanks
You're nothing less than a hero, thank you!
Very clear explanation of backtracking at the beginning, thanks!
Thanks, much love.
Thank you Ben, great explanation!
sure
thanks for the video. thank you for drilling the principles! this helps tremendously. recursion can get pretty difficult. the longer you think about it the more confusing it gets lol...
back tracking is a real pain. but you made it look so easy . thank you man !... waiting for more interview problems like this........:-)
sure
Thank you so much for explaining this problem, vert easy to understand and very useful for my preparation of my whiteboard interview.
Hopeful it will goes will next week.
thanks and best of luck
The concept was tough enough that I had to rewind a few times, pause, and think. But the explanation, method of presentation, and such was amazing. Thanks a ton!
The dynamic with the camera man is fun too
if -> our goal
else -> loop (pick a choice, check constraints [if valid, go deeper], undo choice)
Sweet!!!
Excellent video as always, planning to join your class soon. Might join next month , a little busy this month unfortunately.
Yeah thx, and nice
Awesome work
Helped me A LOT
THANKS 🤍
Dude I have no idea how you don't have 1M subscribers by now.
The channel is young and niche. We do not have content that scales yet.
Agreed!!
Get a guy who does good video editing. your channel will surely sky rocket.
Appreciate your hard work.
thanks
Thanks, it was really helpful.
sure
Thank you!!!!
Love your teaching style bro
thx
I liked the tutorial series...I saw your subset and permutation videos and I somehow managed to come up with the solution to this problem all by myself...so thanks for the wonderful explanation of this topic...however, I couldn't come up with all the possible placements for the queen
Nice. And what do you mean by " I couldn't come up with all the possible placements for the queen". Like you coded it and it has a bug or you don't understand or...yeah...confused.
@@BackToBackSWE currently my solution gives me only 1 possible arrangements...but i was unable to modify it so that it returns me the total numbers of possible valid arrangements for a given nxn board...can you help me on that?
I was thinking of calling our helper function for each column in the first row i.e for each cell in the first row....that will ensure that we cover all possible cases and not just return trie when we find our first valid arrangement....but before calling helper function with a new column value in the first row, we will check if it has already not been peocessed as a valid position by one of our previous calls to the helper function... but i am.not sure if it would work
@@Paradise-kv7fn check other solutions on Leetcode, I'd love to help but I'm busy-ish today
Thanks a lot for such an amazing explanation, I have my coding round for Twitter this week, I hope I clear it. 🤞
ye
Really nice, thanks man
sure
Man these 3 points are really great... i am able to solve now various backtracking problems on my own
great to hear
Very clear, very well explained. Can you do a video on the use of DPLL algorithm and what types of problem to use it on?
You can subscribe to our DSA course with a flat 30% off for some amazing content b2bswe.co/3HhvIlV
Good job boy!
Appreciate the passion and efforts. Kudos to you two! ++Subscribers :)
hola mi amigo
Brilliant explanation
thanks
excellent vidoe.. want to understand the math behind IsValid? Any pointers?
THANK YOU
Very clear explanation.
thanks
@@BackToBackSWE Is the code shown working. What if the row results in no solution. For if row[0] = 0 , row[1] = 2 then row[2] has no solution. It should backtrack with remove but for some reason I do not reach the solution.
That is a damn good explanation and awesome energy bro :)
thx
Best video on Internet
ye
The way you explain details is very good. A small suggestion for code: you can keep both add and remove colPlacements inside if loop, it would avoid adding and removing current col to colplacements list if the valid Placement is false.
ok
First video of you i Watched and subscribed! DOT
welcome!
Amazing job man. Well done.
ye
@@BackToBackSWE It would have been great if you could make a video about the behavioral/phone screen part of the interview for SWE as well.
@@a_k__ ok
10:38 You don't know how much I needed to understand that part. Thank you!! I was so confused. I just didn't know "HOW TO BACTRACK" The most confusing part for me was : :how the heck making it equal to null(or zero - meaning removing it(our choice)) makes our function go back?? Yeah I can find one way or n way to place queens, but how to find all of them?? and that's where your video help me, I missed the point that the loop is always increasing, if my choice is removed next time it will choose for col+1 and (not the 'col' instead).
very helpful and as I always say.. I love ur way of teaching sir
hey
@@BackToBackSWE helo sir i sent u a msg request on ur fb page please check out
amazing, thank you
sure
I love your explanation for backtracking problems. Now I've got a good understanding of the frame of doing such kind of problem, thank you so much!!! But one more thing I want to make sure is that whenever a backtracking function call is exhausted,it returns to its higher layer stack, is undos the first thing that it will execute?
For example:
backtrack(...)
undos
let's say backtrack(1) return to backtrack(2) ,it will undo what it did to " 1 ",and then keep backtracking. Do I get it?
For more complicated backtracking problems:
backtrack 1
some orders
backtrack 2
these 2 backtracking calls are different. If backtrack 1 is exhausted. Does the process work like this: backtrack 1 returns to the previous stack, then execute these orders, and then do the backtrack 2 until it is also exhausted , and then return to the next previous stack of backtrack 1. If some orders are undos , will this process change?
can you consolidate your question, it is hard to parse this all
When he begins the video by saying he took three months to grasp the concept.. I felt that
yer
Bro your explanations are damn good !!!!!!!!!!!
thanks
the nqueens can also be solved by using a knight layout: queens can attack like every other unit except the knight, so if one finds out a combination exclusively for knights it solves the nqueens too
Your'e BackTracking Hero Man
thanks lol, always wanted to be that
naah i had 2 come back again and comment after i coded my own solution u r a legend
Thank You, Glad you liked it.
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends :)
hats off to you .. you are the first non Indian tutorial channel
uh
ayyy ur a boss, I was struggling on this shit man !
Thank You, Glad you liked it.
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends :)
Great explanation. I have a newbie question though. Why do we need to backtrack on every iteration of the for-loop. What if the last choice made was correct. What purpose does undoing the choice serve? You made a statement about the program continuing from the last point of the stack. How does undoing our choice serve that purpose?
because the alternative is keeping a complete board representation for each move which gobbles up your ram
Thanks
great job
thx
I get everything but can someone explain why in isValid method you compare every col placement against the last col placement? If two placements in the middle are wrong then your method will return true even though it is not valid. Am I missing something? If you run this method with arguments 2,4,4,3 it will return true where it's supposed to fail.
Do we undo our choice to get a new set of result? Or why do we do that?
nice explanation
Thank you!
Hey thank you so much for this amazing video. However, I tried your code on my IDE and I guess if you add a return after you add the colPlacements to your result, it will be better right?
I dont remember the code
Awesome video 👌.. thanks a lot .🔥. please upload more videos...
thanks sure and sure
Beautiful!
hola
Thank you.
sure
I think my problem with recursive problems is how to format my code if that makes sense,
like how many helper functions to make and what parameters are each going to take. Any tips for that?
Btw I forgot how I found your channel, but I love the vids!
Yes, this is the hardest part. Thinking recursively took me SEVERAL months to understand and become proficient at. Some just get it, some don't. I didn't.
1.) The more practice you do and the more problems you see, the better you will get at defining base and recursive cases. This is sadly true, a lot of work.
2.) Before even making a driver function, I scaffold out the signature of the recursive helper function. The biggest things that influence this are #1 and #3 of the "keys" I mentioned, your Choices & Goal. In this problem you see we pass in a "colPlacements" array to remember our CHOICES as well as the row # that we are working on and a "result" array to remember our answers, etc. It is not always this straightforward but the key is to ask.
"What subproblems am I solving and what do I need in each to make things work?" For this problem a subproblem is solving a row. When n rows are solved we are done. So that's definitely a param and will be used in the base case since it is our GOAL.
Otherwise it is just practice, trial and error, and eventually proficiency increases greatly.
ur epic bro thank you sm