Tushar, these videos are phenomenal. It's very apparent that you have spent a lot of time preparing this material - your explanations and examples are incredibly clear. Thanks!!!
I have never written comment on any video whether it is good or not, But your videos force me to write comment, By heart you are Genius man !!! Legend of Computer Science!!!!!
I can't put into words how much these videos help me and my friends understand the subject you cover! No way in a million years that my professor will go that deep into the explanation of the all the little (but very important) details you do explain. Please, please cover more topics in the future! :)
just my opinion: 95% of Indian engineering students waste average 6 hours per day in colleges learning shit. We can easily understand actual concepts on youtube in 2 hours and through books for extra. Shit and lazy ass professors and money making colleges. Don't want to hurt anyone's sentiments but IT's THE F TRUTH. Thanks Tushar bhai. I am grateful to you.
I give you thumbs up because the same can be said for any field of study. But no employer is going to hire you to an engineering position without a degree. So the paper degree has its value.
I agree with you at some point. But college its also important because there professors guide students threw the most important subjects. If many people didnt go to college, this videos wouldnt be watched by the same amount of people.
I have seen most of your videos and just wants to say a big thanks. you are a role model for many young people coming out and wants to achieve something big in their life....
Thank you Tushar! Your explanation is really clear and makes sense. It saves me tons of time and makes my day! I hope you can continue to upload more videos.
For the diagonal condition there is an alternate. Given two cells with the coordinates (i1, j1) and (i2, j2) , you can say they are on the same diagonal if | i1 - i2 | = | j1 - j2 | . You can validate this by calculating with values, or you can deduce it from the two formulas you have stated. This way you only need a single formula to validate if the queens attack on diagonal.
You can deduce this with the slope of the line formula Y2 - Y1/X2-X1 = +1 or - 1 implies that the angle is either 45 or 135 degrees and hence is a diagonal
Thanks a lot Tushar. Your Backtracking videos are really awesome. And I really appreciate you explaining things on a whiteboard rather that PPTs. Your code examples are also really clean and simple to understand which is very hard to find to algorithms videos. I hope you keep creating these videos and help us achieve our goals of working in bigger companies. Thanks a lot once again.
Thank you for making me understand Recursion.....What I have got from your explanations is something very valuable....I got to learn the concept of Recursion, Back Tracking and Dynamic programming. After understanding the concept, I am able to code it myself. Thank you
The tree visual was fantastic. It allowed me to visualize how the algorithm was eliminating possibilities and backtracking to the first level to start over.
Thanks.. A Suggestion- You could simply check if mod(row1-row2)== mod(col1-col2) to check for the diagonal attacking position rather than using 2 separate formulas for 2 diagonals.
Great job. Generally to find the attack in diagnal position abs(r1-r2)==abs(c1-c2) is used, now I got a new formula. No need of two dimensional array, single dimension is enough with index represents rows, values represents the columns.
Thanks for the videos, they are great! Keep up the good work!! I went through this code which says it is of Time: O(n*n) but actually, it's of Time: O(n*n*n) because you fix rows (Time: O(n)), increment col for every row (Time: O(n)) and check for positions for every col which again is another Time: O(n). All of this adds up to Time: O(n*n*n). Please check and correct it.
hey i don't know about of number of views people have got in their video for explaining N queens problem. But i tell you people this is the best explanation. NOBODY by far can teach in such a simpler way as he has done. You have any tutorials for all this Tushar, i would love to join it.
There are a lot of obviously unnecessary check that could be avoided: the four squares around each queen are for sure not safe so why even try it? I would create N square object with a queen property that holds the queen id if attacking it. After each queen position iteration I would jump to a square that is not already attacked by a queen and place the queen and register her id to all squares it attacks. So after each iteration the number of available unattacked squares will reduce and makes the the algorithm finish much faster.
Thanks sir..Its very good explaination. One problem : when we are backtracking we should delete element from position array. if(solveutil) return true; else delete pos; ...... return false;
Awesome video, thank you so much. If I may suggest, it might be better if you can also use a mic for the white board explanation since the sound quality will be much better.
This is an awesome explanation. Helped me understand backtracking. And all the people telling you that your english is horrible do not deserve your attention. Fuck 'em
Awesome video, very well explained. I think that I would now be able to solve this exercise even a little later in the future, as I have understood the principle and the rules to determine a valid placement for a queen. One question regarding the backtracking step though: If a callee function return false to the caller, that's to say a deeper level of recursion can't find a valid place for a queen, the calling function continues to look for a valid place one column ahead where it stopped before. However, the previously placed queen in the array is never cleared and remains there. Doesn't that cause problems? On the right hand side you always remove the notes but you don't do it in the code. WOuldn't you have to add an else statement after the if(foundSafe) block to remove an falsly placed queen?
Hey Tushar, Thank you for all your videos. They have helped me a lot to understand the problem and the solution. The code you provide just makes it the best. Regarding this video, I am a little confused with the time complexity. Is it exponential as you say in the video or is it O(n*n) as mentioned in the code? Any clarification is appreciated. Thank you once again! :)
If they gave me a problem in real time I can solve it with the basic serial and according to the family that belongs to the board. This is only for cases of an empty board. For the case of a board with a queen on the board, I can solve all the prime boards in the position that the queen is indicated, be of the size that is from n = 5, 7,11,13,17,19,23. ........ 61, ..... etc
I noticed that in the code example you have the space complexity as O(n*n), however, isn't it O(n) where n represents the total number of queens we have?
Hi Tushar, Thanking you for nice article. I see a loop hole here. I may be wrong. Please correct me if so. When we are checking if this row and column is under attack from any previous queen. When it comes to check diagonally, we are checking only next row from previous queen. There can be possibility that a queen placed in 1st row, attacking a position in 4th row, placed diagonally. It looks like we have missed this check. Yours response awaited.
Very clear cut explanation of n Queen problem. Thanx a lot Sir. Please upload the videos on bellman ford with directed graph with algorithm. Sir it is very hard to understand. Please Sir help me In this.
Can you please make a video on "How to make recursion tree" and thinking of solving it recursively, i often confuses when i see two or more functions calling to same functions again and again.
Hey, which part of you code does backtrack? I think somewhere you have to remove the elements from position when its not safe. I can't get that part in your code. Can you explain
I got the same doubt and tried to understand that piece of logic. Looks like, the elements won't get removed as such from Positions, they rather get replaced/updated by a new element in the next iteration.
Great video! How do you derive the formula upwardDiagonal = i+j and downwardDiagonal = i-j ... is it just by observation or is there a way to find this from using line equations?
You can use the equation of a straight line to find the relation. Treating the row and column value as x y coordinates , and taking the slope as 1 and -1 for the 2 diagonals. :)
Tushar I know you must be familiar with the following approach too but just in case you are not then - Let the current queen to be placed = cur_q Let all the other queens that have been placed earlier = placed_q If( abs(cur_q.row - placed_q.row) - abs(cur_q.col - placed_row.col) == 0) then the queens are on the same diagonal
Awesome explanation. You inspired me to make my own version of this video for explanation.
And actually you made it!
Tushar, these videos are phenomenal. It's very apparent that you have spent a lot of time preparing this material - your explanations and examples are incredibly clear. Thanks!!!
I have never written comment on any video whether it is good or not, But your videos force me to write comment, By heart you are Genius man !!!
Legend of Computer Science!!!!!
thanks for writing the comment for the first time.Now i can die peacefully.
I can't put into words how much these videos help me and my friends understand the subject you cover!
No way in a million years that my professor will go that deep into the explanation of the all the little (but very important) details you do explain.
Please, please cover more topics in the future! :)
just my opinion: 95% of Indian engineering students waste average 6 hours per day in colleges learning shit. We can easily understand actual concepts on youtube in 2 hours and through books for extra. Shit and lazy ass professors and money making colleges. Don't want to hurt anyone's sentiments but IT's THE F TRUTH. Thanks Tushar bhai. I am grateful to you.
I give you thumbs up because the same can be said for any field of study. But no employer is going to hire you to an engineering position without a degree. So the paper degree has its value.
I agree with you at some point. But college its also important because there professors guide students threw the most important subjects. If many people didnt go to college, this videos wouldnt be watched by the same amount of people.
I have seen most of your videos and just wants to say a big thanks. you are a role model for many young people coming out and wants to achieve something big in their life....
The legend of Computer Science. Yesterday I had lots of problems regarding coding a solution for this problem, now I don't have any. Brilliant video!
I've watched 3 videos prior to yours' on this topic and so far you've done the best job explaining it. Thanks.
Thank you Tushar! Your explanation is really clear and makes sense. It saves me tons of time and makes my day! I hope you can continue to upload more videos.
Best explanation I have seen yet. Thank you!
For the diagonal condition there is an alternate. Given two cells with the coordinates (i1, j1) and (i2, j2) , you can say they are on the same diagonal if | i1 - i2 | = | j1 - j2 | . You can validate this by calculating with values, or you can deduce it from the two formulas you have stated. This way you only need a single formula to validate if the queens attack on diagonal.
Totally agreed. Taking absolute of " |X2 - X1| == |Y2 - Y1| " is better conditional statement for checking if the queen is safe or not.
You can deduce this with the slope of the line formula
Y2 - Y1/X2-X1 = +1 or - 1 implies that the angle is either 45 or 135 degrees and hence is a diagonal
Thanks a lot Tushar. Your Backtracking videos are really awesome. And I really appreciate you explaining things on a whiteboard rather that PPTs. Your code examples are also really clean and simple to understand which is very hard to find to algorithms videos. I hope you keep creating these videos and help us achieve our goals of working in bigger companies.
Thanks a lot once again.
I admire your visual presentation and clean code matching your flow of explaining the algorithm.
Thank you for making me understand Recursion.....What I have got from your explanations is something very valuable....I got to learn the concept of Recursion, Back Tracking and Dynamic programming. After understanding the concept, I am able to code it myself. Thank you
The tree visual was fantastic. It allowed me to visualize how the algorithm was eliminating possibilities and backtracking to the first level to start over.
These videos are incredibly helpful! Thank you for the clear step by step explanation of the algorithms!
every time a problem bothers me, I find video of you explaining it :) you are awesome .
Your explaination is always clear and easy to understand! Thanks for your videos!
this is a great video. Always helps me a ton to see stuff drawn out like this.
Great Explaination Tushar. Kindly consider doing the Graph Coloring problem using backtracking as well!
You are a hero at explaining things.WELL DONE SIR.THANK YOU SOOOOOO MUCH.
Thanks.. A Suggestion- You could simply check if mod(row1-row2)== mod(col1-col2) to check for the diagonal attacking position rather than using 2 separate formulas for 2 diagonals.
No bro
You will have to use two conditions in that case too
yeah
Great job. Generally to find the attack in diagnal position abs(r1-r2)==abs(c1-c2) is used, now I got a new formula. No need of two dimensional array, single dimension is enough with index represents rows, values represents the columns.
Ya. It is a single array. My mistake.
Thoroughly explained! I love this! Thank you for your video!
Thanks for the videos, they are great! Keep up the good work!!
I went through this code which says it is of Time: O(n*n) but actually, it's of Time: O(n*n*n) because you fix rows (Time: O(n)), increment col for every row (Time: O(n)) and check for positions for every col which again is another Time: O(n). All of this adds up to Time: O(n*n*n). Please check and correct it.
You are the best Tushar sir, can't wait to see your next video!
best video available for the N queen problem using backtracking .
very good by far the best explanation for this problem the explanation of index of attacks was very very helpful
I watched many backtracking videos, but this is so simple and understandable. thank you man
hey i don't know about of number of views people have got in their video for explaining N queens problem. But i tell you people this is the best explanation. NOBODY by far can teach in such a simpler way as he has done. You have any tutorials for all this Tushar, i would love to join it.
You are amazing. I code in python but the way you explain your code is so good. Thanks : )
thanks Tushar Roy, your videos are really helpful
Good Explanation. Helped me to understand the problem easily. Thank You.
Neat Explanation. Love your Dynamic Programming Series!
There are a lot of obviously unnecessary check that could be avoided: the four squares around each queen are for sure not safe so why even try it? I would create N square object with a queen property that holds the queen id if attacking it. After each queen position iteration I would jump to a square that is not already attacked by a queen and place the queen and register her id to all squares it attacks. So after each iteration the number of available unattacked squares will reduce and makes the the algorithm finish much faster.
Thanks sir..Its very good explaination. One problem : when we are backtracking we should delete element from position array.
if(solveutil)
return true;
else
delete pos;
......
return false;
You can keep a Map for the finding how many queens are attacking a row, column or diagonal and check if the current cell is under attack or not
concise explanation. understood the use of row + i, row - i .
Agree with others. Your explanation made so much sense. Great job.
Grear job man! So clear and vivid! Thanks!
Awesome video, thank you so much.
If I may suggest, it might be better if you can also use a mic for the white board explanation since the sound quality will be much better.
This is the best explanation I got yet.
Great Explanation. the best one on n-queen problem.
Finally an explanation that makes sense! THANK YOU!!!
If anyone's struggling with the indices for the diagnols think of straight line equations but this array is in the 4th quadrant
Thank you very much... I was searching for a algorithm like this to make a Sudoku solver. Thanks...
Appreciate your hard work. Very well explained.
you are doing an awesome job bro! keep up the good work
very very well explain. now i can do my college task. thank you.
you alright bro? you got the thousand algorithm stare goin
Best tutorial. Thanks for the clear explanation!!
Very good and clear explanation. Thank you for the video.
The best explanation for backtracking..........!!!!! thanks tushar... :D
Hi Tushar, In your N-queen video, you said the time complexity is exponential but your github comment has time complexity as n2.
I have learned a lot from your videos. thanks
Where are you Sir? It's been almost 7 years
Very helpful! Thanks for sharing
Greatest explanation (for me). Thank you so much
Simply superb explanation!!!
kaash aaise teacher hume padhane aaye hote
i saw your lots of videos which helps me a lot do as many as possibles plz...
thanks a lot for your clear and brief tutor and it insight me about this topic thanks again keep go on
Thanks man! You are an excellent teacher.
Awesome video, especially the code explanation.
This is an awesome explanation. Helped me understand backtracking. And all the people telling you that your english is horrible do not deserve your attention. Fuck 'em
Awesome video, very well explained. I think that I would now be able to solve this exercise even a little later in the future, as I have understood the principle and the rules to determine a valid placement for a queen.
One question regarding the backtracking step though: If a callee function return false to the caller, that's to say a deeper level of recursion can't find a valid place for a queen, the calling function continues to look for a valid place one column ahead where it stopped before. However, the previously placed queen in the array is never cleared and remains there. Doesn't that cause problems? On the right hand side you always remove the notes but you don't do it in the code.
WOuldn't you have to add an else statement after the if(foundSafe) block to remove an falsly placed queen?
nice work on explaining the recursion tree!!!
Thanks
Fabulous lecture Bro! Thank's a lot
was wondering if someone could elaborate on time complexity of algorithm
Hey Tushar, Thank you for all your videos. They have helped me a lot to understand the problem and the solution. The code you provide just makes it the best.
Regarding this video, I am a little confused with the time complexity. Is it exponential as you say in the video or is it O(n*n) as mentioned in the code? Any clarification is appreciated. Thank you once again! :)
Loved this solution!! Your solution is amazing.. would be better if you had explained time complexity, why it is exponential.
If they gave me a problem in real time I can solve it with the basic serial and according to the family that belongs to the board.
This is only for cases of an empty board. For the case of a board with a queen on the board, I can solve all the prime boards in the position that the queen is indicated, be of the size that is from n = 5, 7,11,13,17,19,23. ........ 61, ..... etc
Isn't the time complexity O(n!)??
Thanks Tushar for explaination.
I noticed that in the code example you have the space complexity as O(n*n), however, isn't it O(n) where n represents the total number of queens we have?
Hi Tushar,
Thanking you for nice article.
I see a loop hole here. I may be wrong. Please correct me if so.
When we are checking if this row and column is under attack from any previous queen. When it comes to check diagonally, we are checking only next row from previous queen. There can be possibility that a queen placed in 1st row, attacking a position in 4th row, placed diagonally. It looks like we have missed this check.
Yours response awaited.
We are checking whether the queen at particular level is under attack from all the previous levels
for(int queen=0; queen
Only if Engineering Colleges in India hired teachers like you, we would not have to watch this video.
Saved my day maan!! Thank you soo much!!!
You are awesome Tushar.
really clear, easy to understand, thanks a lot
Very clear cut explanation of n Queen problem. Thanx a lot Sir. Please upload the videos on bellman ford with directed graph with algorithm. Sir it is very hard to understand. Please Sir help me In this.
Great Job Tushar !
+Tushar Roy Keep up your good work ! You are doing a stupendous job and helping countless people ! :)
Well Explained!!! Also next time when you make DP videos. Please explain why its a DP? whether it satisfies optimality and subproblem?
Keep it man....It really helps a lot!
What is the time complexity of this problem?
What did you use to trace your program in the matrix? Looks like something that might come in handy for tracing programs.
Thanks for the great videos.
interview.io
Can you please make a video on "How to make recursion tree" and thinking of solving it recursively, i often confuses when i see two or more functions calling to same functions again and again.
excellent !! thank you for making this video .
Hey, which part of you code does backtrack? I think somewhere you have to remove the elements from position when its not safe. I can't get that part in your code. Can you explain
I got the same doubt and tried to understand that piece of logic. Looks like, the elements won't get removed as such from Positions, they rather get replaced/updated by a new element in the next iteration.
When we backtrack shouldnt we clear the previously set foundSafe position in the positions array?
Hey, Nice explaination. Just wanted to know about the codevisualization. How you did it??
+Tushar Roy thanks man. Is there any option for the following or you have coded it?
wow. clear as water.
Great Work, a neat and simple solution,
is there any other solution possible for Nqueen problem with lesser timeComplexity.
it is very helpful sir...can please explain global parallel genetic algorithm for solving n queen problem n also naive algorithm for n queen
great explanation! but where did u define n = 4?
Really well explained.
Is it easy or difficult to find one pattern (one solution) of 2500 or 5000 queens with Backtracking Algorithms?
but in the second row queen off diagonal is going to attack by first row queen!!
Can anyone tell me why Tushar has taken 1 box for row 0, 2 for row1, 3 for row 3 and again two for the last row?
Great video! How do you derive the formula upwardDiagonal = i+j and downwardDiagonal = i-j ... is it just by observation or is there a way to find this from using line equations?
You can use the equation of a straight line to find the relation.
Treating the row and column value as x y coordinates , and taking the slope as 1 and -1 for the 2 diagonals.
:)
Tushar I know you must be familiar with the following approach too but just in case you are not then -
Let the current queen to be placed = cur_q
Let all the other queens that have been placed earlier = placed_q
If( abs(cur_q.row - placed_q.row) - abs(cur_q.col - placed_row.col) == 0)
then the queens are on the same diagonal