/ tusharroy25 github.com/mis... github.com/mis... Given nxn board and n queens. Place these queens on this board so that they do not attack each other.
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!!!!!
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.
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 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! :)
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 tree visual was fantastic. It allowed me to visualize how the algorithm was eliminating possibilities and backtracking to the first level to start over.
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
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.
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
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 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.
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.
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.
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;
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, 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.
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.
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.
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! :)
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.
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?
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.
Here's a more elegant explenation: czcams.com/video/R8bM6pxlrLY/video.html&feature=share&fbclid=IwAR3Sl96wOacXpuifjl3syZJv8foyH4z_TENM-Q6k75SPTSvEybSb6n9KrG8
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.
Awesome explanation. You inspired me to make my own version of this video for explanation.
And actually you made it!
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.
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.
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 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! :)
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!
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.
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
Great Explaination Tushar. Kindly consider doing the Graph Coloring problem using backtracking as well!
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.
I've watched 3 videos prior to yours' on this topic and so far you've done the best job explaining it. Thanks.
Best explanation I have seen yet. Thank you!
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
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.
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.
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.
every time a problem bothers me, I find video of you explaining it :) you are awesome .
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.
Thoroughly explained! I love this! Thank you for your video!
You are a hero at explaining things.WELL DONE SIR.THANK YOU SOOOOOO MUCH.
These videos are incredibly helpful! Thank you for the clear step by step explanation of the algorithms!
best video available for the N queen problem using backtracking .
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.
very good by far the best explanation for this problem the explanation of index of attacks was very very helpful
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
I watched many backtracking videos, but this is so simple and understandable. thank you man
concise explanation. understood the use of row + i, row - i .
Good Explanation. Helped me to understand the problem easily. Thank You.
Great Explanation. the best one on n-queen problem.
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;
This is the best explanation I got yet.
Greatest explanation (for me). Thank you so much
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
You are the best Tushar sir, can't wait to see your next video!
thanks Tushar Roy, your videos are really helpful
If anyone's struggling with the indices for the diagnols think of straight line equations but this array is in the 4th quadrant
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.
You are amazing. I code in python but the way you explain your code is so good. Thanks : )
Agree with others. Your explanation made so much sense. Great job.
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
very very well explain. now i can do my college task. thank you.
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.
Finally an explanation that makes sense! THANK YOU!!!
Neat Explanation. Love your Dynamic Programming Series!
thanks a lot for your clear and brief tutor and it insight me about this topic thanks again keep go on
Grear job man! So clear and vivid! Thanks!
Very good and clear explanation. Thank you for the 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.
Thank you very much... I was searching for a algorithm like this to make a Sudoku solver. Thanks...
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! :)
you alright bro? you got the thousand algorithm stare goin
kaash aaise teacher hume padhane aaye hote
Loved this solution!! Your solution is amazing.. would be better if you had explained time complexity, why it is exponential.
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.
i saw your lots of videos which helps me a lot do as many as possibles plz...
Appreciate your hard work. Very well explained.
was wondering if someone could elaborate on time complexity of algorithm
Very helpful! Thanks for sharing
I have learned a lot from your videos. thanks
Best tutorial. Thanks for the clear explanation!!
Hi Tushar, In your N-queen video, you said the time complexity is exponential but your github comment has time complexity as n2.
Isn't the time complexity O(n!)??
you are doing an awesome job bro! keep up the good work
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?
Tushar roy : How Does a Queen Attack?
Me : By Marriage
😂😂😂😂
Hope your wife doesnt read this
@@adhishmalviya2408 i am single
😁😁😁
Thanks man! You are an excellent teacher.
Only if Engineering Colleges in India hired teachers like you, we would not have to watch this video.
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
The best explanation for backtracking..........!!!!! thanks tushar... :D
You are awesome Tushar.
wow. clear as water.
Is it easy or difficult to find one pattern (one solution) of 2500 or 5000 queens with Backtracking Algorithms?
Awesome video, especially the code explanation.
really clear, easy to understand, thanks a lot
Well Explained!!! Also next time when you make DP videos. Please explain why its a DP? whether it satisfies optimality and subproblem?
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
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?
Simply superb explanation!!!
Great Job Tushar !
+Tushar Roy Keep up your good work ! You are doing a stupendous job and helping countless people ! :)
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
Thanks Tushar for explaination.
nice work on explaining the recursion tree!!!
Thanks
Keep it man....It really helps a lot!
Excellent explaination!
Fabulous lecture Bro! Thank's a lot
When we backtrack shouldnt we clear the previously set foundSafe position in the positions array?
Great video , again !
What is the time complexity of this problem?
it is very helpful sir...can please explain global parallel genetic algorithm for solving n queen problem n also naive algorithm for n queen
Amazing explanation 🙏
Here's a more elegant explenation:
czcams.com/video/R8bM6pxlrLY/video.html&feature=share&fbclid=IwAR3Sl96wOacXpuifjl3syZJv8foyH4z_TENM-Q6k75SPTSvEybSb6n9KrG8
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.
Saved my day maan!! Thank you soo much!!!
Really well explained.
A big thaanks dude!!!!!!
excellent !! thank you for making this video .
Great Work, a neat and simple solution,
is there any other solution possible for Nqueen problem with lesser timeComplexity.