The N Queens Problem using Backtracking/Recursion - Explained

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

++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++

This question is question 16.2 in Elements of Programming Interviews (EPI).

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

[alihaghighipour]

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

[naydernn]

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!

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

[some_s_guy]

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

[jiadar]

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

[lilaiyang]

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

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

[finncummins]

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!

[manasasusirla]

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

[takharamazanpolat]

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.

[vinithapalani]

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

[karankanchetty]

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.

[vraih]

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

[satyadeeproat]

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

[danielg]

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

[ameerkaras]

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

[NithinMWarrier]

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

[xinyuyou]

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

[Ayushkumar-xjvl]

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