The N Queens Problem using Backtracking/Recursion - Explained

[@BackToBackSWE]

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.

[@alihaghighipour7371]

you're by far the most enthusiastic person that i've ever seen in this field dude . keep it up !

[@BackToBackSWE]

I was mad lol, because online explanations sucked

[@qwarlockz8017]

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

[@naydernn4725]

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!

[@BackToBackSWE]

Thank you, glad you liked it 😀 Do check out backtobackswe.com/platform/content and please recommend us to your family and friends 😀

[@BarnezGFX]

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.

[@BackToBackSWE]

Great. That means a lot. My goal is to make this the premier channel (#1 on KZbin) 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.

[@some_20s_guy]

I really like the informalness that you bring while making videos on dense topics, trust me that really helps the viewers 😁

[@BackToBackSWE]

thx

[@jiadar]

I've never seen someone so excited about algorithms. Great content. Well done!

[@ameerkaras4580]

These have got to be the only genuinely entertaining coding vids on the internet, love it

[@BackToBackSWE]

ye - i luv the internets

[@takharamazanpolat7610]

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.

[@BackToBackSWE]

Welcome to da pardy

[@lilaiyang5745]

Please keep doing more problems, only your video makes me understand N-Queens Problems. Appreciate it!

[@BackToBackSWE]

Amaze! Stay tuned for our upcoming interview prep module with new mentors!

[@finncummins6230]

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!

[@BackToBackSWE]

Nice! Keep it up, you are a beast!

[@manasasusirla6451]

I bet there's no one who can explain backtracking problem better than you did. Your video helped me a lot. Thanks!

[@BackToBackSWE]

sure!

[@ericlugo-dev]

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!!!

[@BackToBackSWE]

great to hear

[@vinithapalani3385]

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!!

[@BackToBackSWE]

nice!

[@vraih4847]

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!!!

[@BackToBackSWE]

ye, go flourish internet friend

[@karankanchetty105]

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.

[@BackToBackSWE]

sure, thanks for coming by

[@danielg012]

These videos have been super helpful for me during my interview prep. Thank you so much!

[@BackToBackSWE]

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.

[@sanjivmadhavan5705]

AWW THIS VIDEO WAS POSTED ON MY BIRTHDAY. THANKS FOR THE GIFT MY MAN

[@BackToBackSWE]

nice yo

[@NithinMWarrier]

I really love the way you explain, your commitment to understand is amazing, a big thumbs up man!!

[@satyadeeproat2012]

Really good explanation to divide backtracking problems in goals, choice and constraint. Backtracking problems get really easy thinking in this way

[@BackToBackSWE]

yeah

[@prashant211087]

When you reach the end of this playlist... Backtrack :)

[@BackToBackSWE]

indeed

[@user-wc1sm8cj8s]

LOL

[@rajrajeshwarsinghrathore]

Thanks a lot. This was my first LeetCode HARD problem. Gave a much-needed confidence.

[@AdtecBarema]

This is Just Superb, thank you so much Biny for all effort & kindness, in demistyfying this involved problem.

[@bokams3385]

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

[@BackToBackSWE]

sure

[@xinyuyou7512]

I really feel your enthusiastic when you're making this video. This helps me continue Learning the video. Thank you so much.

[@BackToBackSWE]

haha, sure

[@Ayushkumar-xj9vl]

Thanks for this briliant insight to recursion, you explain like a big bro.😃

[@BackToBackSWE]

sure

[@jayliang5737]

You get the clearest explanation for backtracking I can find on youtube!

[@BackToBackSWE]

thx

[@IlyaBoytsov-dt8lt]

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

[@BackToBackSWE]

Thanks :)

[@adipratapsinghaps]

if -> our goal else -> loop (pick a choice, check constraints [if valid, go deeper], undo choice) Sweet!!!

[@siddhantsharma6747]

Dude I have no idea how you don't have 1M subscribers by now.

[@BackToBackSWE]

The channel is young and niche. We do not have content that scales yet.

[@hezekiahbranch5461]

Agreed!!

[@vigneshkrishnan3192]

Get a guy who does good video editing. your channel will surely sky rocket.

[@ipals1234]

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.

[@BackToBackSWE]

ok

[@gmstabloid]

You should be proud man! Awesome explanation and passion for the code! Thanks!

[@BackToBackSWE]

thanks

[@NaveenKumar-os8dv]

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

[@svdfxd]

As usual very nice explanation. And a big thanks to your buddy who films all videos religiously.

[@BackToBackSWE]

hahaha, it is a religion at this point

[@ismailahmad9597]

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!

[@ismailahmad9597]

The dynamic with the camera man is fun too

[@sarthakbhatia7888]

Thanks mann....Your explaination is really one of the best out there!!

[@BackToBackSWE]

thanks!

[@rozzero9664]

hats off to you .. you are the first non Indian tutorial channel

[@BackToBackSWE]

uh

[@marisawong644]

i love this man - he explains everything so well!

[@0x1h0b]

back tracking is a real pain. but you made it look so easy . thank you man !... waiting for more interview problems like this........:-)

[@BackToBackSWE]

sure

[@eggsaladstuckcrafts4653]

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!

[@BackToBackSWE]

sure

[@Paradise-kv7fn]

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

[@BackToBackSWE]

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.

[@Paradise-kv7fn]

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

[@BackToBackSWE]

@@Paradise-kv7fn check other solutions on Leetcode, I'd love to help but I'm busy-ish today

[@RK-nw1nq]

Such a great explanation and your energy, it was amazing which really helps in understanding the concept better. GREAT WORK!!

[@BackToBackSWE]

thanks

[@hackerandpainter]

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

[@jjlovekdw]

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.

[@BackToBackSWE]

thanks and best of luck

[@soymaxxing]

Excellent video as always, planning to join your class soon. Might join next month , a little busy this month unfortunately.

[@BackToBackSWE]

Yeah thx, and nice

[@TanujMishra077]

Great explanation. You guys are awesome. Keep up the good work. Subscribed.

[@BackToBackSWE]

thanks

[@pablogalindo2089]

I love the way you teach!! very helpful

[@BackToBackSWE]

thx

[@nishantjain2128]

Man these 3 points are really great... i am able to solve now various backtracking problems on my own

[@BackToBackSWE]

great to hear

[@josephwong2832]

Love your teaching style bro

[@BackToBackSWE]

thx

[@陪着糖宝宝长大]

this is supper clear, thank you for making these videos

[@ogbonnakingsley9908]

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?

[@IkethRacing]

because the alternative is keeping a complete board representation for each move which gobbles up your ram

[@joshwahnon854]

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?

[@BackToBackSWE]

You can subscribe to our DSA course with a flat 30% off for some amazing content b2bswe.co/3HhvIlV

[@mathavraj9378]

When he begins the video by saying he took three months to grasp the concept.. I felt that

[@BackToBackSWE]

yer

[@nocode659]

First video of you i Watched and subscribed! DOT

[@BackToBackSWE]

welcome!

[@jacksonsouza5232]

Very clear explanation of backtracking at the beginning, thanks!

[@BackToBackSWE]

Thanks, much love.

[@rahulsaxena9103]

You are awesome!!. Such a lucid explanation!

[@BackToBackSWE]

thanks

[@shriyadas925]

Awesome explanation. Best video on this topic! Loved it!

[@BackToBackSWE]

thanks

[@F.R.A.N.K.I.E]

You're nothing less than a hero, thank you!

[@nico-bf8ql]

thank u so much. i love how causal and inviting you are

[@BackToBackSWE]

Glad it was helpful! 😄 Also check out our FREE DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉

[@SlowMister112]

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

[@jomosis9234]

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?

[@BackToBackSWE]

can you consolidate your question, it is hard to parse this all

[@rohitkishore12]

10:07 did'nt understand the concept of "remove our choice" or "undo our choice"....can anyone explain??

[@BackToBackSWE]

Consider where our "choice" of queen placement is kept. It is persisted in memory and this memory is accessed through out our recursive calls. We must make a placement -> exhaust choice -> return back to where we are and then keep chosing. Visualize the recursion in your head and how memory is accessed. This takes time, let it sink in.

[@rohitkishore12]

@@BackToBackSWE yes it is taking time but i think i started understanding it....thanx for your quick reply :-)

[@BackToBackSWE]

@@rohitkishore12 nice

[@l_tonz]

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...

[@sumandas829]

Best video on Internet

[@BackToBackSWE]

ye

[@lokeshs9449]

Your'e BackTracking Hero Man

[@BackToBackSWE]

thanks lol, always wanted to be that

[@guptabhi123]

I am learning the concepts of backtracking - This is what I understood. We remove the placement at the end in the for loop so as to try for other possibilities. However, what if the placement is correct, we still end up removing it right? Why does that work? Also, if we add the row to the result list, and if filling those numbers in that row was not correct, then how do we undo the choices that are already added to the result? Can someone please help with the core idea behind the above 2 points?

[@BackToBackSWE]

"However, what if the placement is correct, we still end up removing it right? Why does that work?" Trace the recursion in your head. It will become apparent. "Also, if we add the row to the result list, and if filling those numbers in that row was not correct, then how do we undo the choices that are already added to the result?" Trace the code. It will be clear. Print things out.

[@mayankdandwani9951]

Bro your explanations are damn good !!!!!!!!!!!

[@BackToBackSWE]

thanks

[@krishnapathi572]

That is a damn good explanation and awesome energy bro :)

[@BackToBackSWE]

thx

[@anjurawat9274]

very helpful and as I always say.. I love ur way of teaching sir

[@BackToBackSWE]

hey

[@anjurawat9274]

@@BackToBackSWE helo sir i sent u a msg request on ur fb page please check out

[@subujekupadupa]

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.

[@UECDishaKhattri]

you explain concepts very well. Please code in c++.

[@BackToBackSWE]

Thanks and we have C++ solutions at backtobackswe.com

[@anmolmishra1914]

I do have weak roots in recursion, I am an undergrad, How did you improve your recursion? (What to do while practicing?) i don't use FB else I would have asked the same on the group, I don't see any other to ask a question. Sorry for trouble like this.

[@BackToBackSWE]

Do a ton of problems until it is seared into your soul. And no, this is the best place to ask questions.

[@jonathandaniel7321]

what did the trick for me is trusting the recursive calls, put the base case above it and it will always work, just trust it

[@ramansb1008]

naah i had 2 come back again and comment after i coded my own solution u r a legend

[@BackToBackSWE]

Thank You, Glad you liked it. Do check out backtobackswe.com/platform/content and please recommend us to your family and friends :)

[@tandonneeraj]

Very clear explanation.

[@BackToBackSWE]

thanks

[@tandonneeraj]

​@@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.

[@shikharsaxena4432]

Thanks a lot for such an amazing explanation, I have my coding round for Twitter this week, I hope I clear it. 🤞

[@BackToBackSWE]

ye

[@HarshSingh-zf7tw]

Ben I know its too much to ask but it would be very helpful for beginners if u would dry run your code on a small test case , so that that your theory can be seen how it is implemented in practicality .

[@BackToBackSWE]

How so? Elaborate, I kinda get what u mean

[@muralivenuthyagarajan5767]

Awesome explanation. Easy to understand.

[@BackToBackSWE]

thanks

[@naveen3192]

Do we undo our choice to get a new set of result? Or why do we do that?

[@ruchikasalwan1285]

Good one! Explained really well!

[@BackToBackSWE]

thx

[@prince26902690]

excellent vidoe.. want to understand the math behind IsValid? Any pointers?

[@teki9845]

Amazing video man , thank you so much !!!!!!!!

[@a_k__]

Amazing job man. Well done.

[@BackToBackSWE]

ye

[@a_k__]

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

[@BackToBackSWE]

@@a_k__ ok

[@kickass91210]

What does results return? A list of lists representing the board as 1's and 0's. Where 1 is a queen?

[@BackToBackSWE]

I don't remember this video - it is really old

[@geetusharma3923]

Awesome video 👌.. thanks a lot .🔥. please upload more videos...

[@BackToBackSWE]

thanks sure and sure

[@srikantsharma6430]

Appreciate your hard work.

[@BackToBackSWE]

thanks

[@jayram.deshpande]

amazingly explained ! Bravo !

[@Palmoghe]

Appreciate the passion and efforts. Kudos to you two! ++Subscribers :)

[@BackToBackSWE]

hola mi amigo

[@testshar2117]

The better title for this video is "How to prepare yourselves for solving N-Queen problem"

[@narihanellaithy7726]

We could however, instead of backtracking, check before we add the column and don't add it if it doesn't meet the constraints. Used an array index:rows and value:columns. It passed. My question is, is there always a solution that doesn't involve backtracking? Also, is there a particular reason where backtracking is better? or does it perform better?

[@BackToBackSWE]

It definitely doesn't perform the best since backtracking is basically a brute force and unintelligent in this case. Is there always a solution that doesn't involve backtracking? Possibly? Not sure on this one but that goes into the realm for proving lower bounds then finding what algorithms can do better than this to meet that lower bound

[@narihanellaithy7726]

Back To Back SWE makes sense! Thank you! 🙋🏼‍♀️

[@BackToBackSWE]

@@narihanellaithy7726 sure

[@JuanGonzalez-cl2fy]

You said that it took you a few months to understand backtracking. Could you elaborate a bit more on how you learned it? Did you spend that time trying out different backtracking problems? Awesome video, by the way.

[@BackToBackSWE]

I just coded and thought on it a lot. It will become effortless. Yes I did a good amount of problems. and thanks

[@mikes.1978]

In the isValid() func, why are you only running from 0 to rowId - 1?

[@BackToBackSWE]

Checking each row before the row we are trying to place into

[@mikes.1978]

So when we check for “diff == rowId - i”, we’re checking if vertical and horizontal placement distances are equivalent for 2 pieces, which indicates a diagonal intersection?

[@vivek4490]

awesome explanation!

[@batman_1st]

Thank you Ben, great explanation!

[@BackToBackSWE]

sure

[@airysm]

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!

[@BackToBackSWE]

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.

[@shivanktripathi4661]

where can I get the code you just explained

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@Paradise-kv7fn]

I just got an interview call for amazon sde through hackerearth hiring challege...however, the interview is scheduled on 1st June :/ Now I have been preparing for interviews since around 20-25 days but I dont think that I am ready for all rounds of amazon level interviews...they are not reimbursing for the travel as well...so I am in a dilemma whether I should even go or not :/ are there any important topics that I should completely focus on for the next 2 3 days?

[@BackToBackSWE]

everything you are weak at

[@stephencheng8450]

Hi Ben, why did you remove all the accompanying github links? I thought the code example went well with your video.

[@BackToBackSWE]

We keep our solutions privately now on backtobackswe.com

[@saadmansakib6612]

You said the "previous video quality" are bad. Well I think it's pretty good xD

[@BackToBackSWE]

the mic and video are ok

[@ElvinAkhundzadeh]

Thanks a lot, Lewis Hamilton!

[@BackToBackSWE]

what

[@ElvinAkhundzadeh]

@@BackToBackSWE Just kidding :) I thought it's Lews Hamiltonn explaining backtracking. You did it very well and in easily understandable way!

[@BackToBackSWE]

@@ElvinAkhundzadeh Haha no I wasn't offended, I was just really really confused

[@jibxjib]

He's right you kinda look like Lewis Hamilton

[@PhoMaiZF]

Chris Paul*

[@Tatseryu27]

My gosh, this is exactly what I was looking for. I'm gonna use it for my presentation tomorrow.

[@BackToBackSWE]

nice

[@tlj77]

Really nice, thanks man

[@BackToBackSWE]

sure