You have my utmost appreciation for such a thorough explanation of this n queens problem - which has puzzled me for years since I first knew this problem. I truly believe that if I could understand the thoughts and technique of solving n queens problem, I would get the least sense of programming, and I might really have a chance to become a programmer. many thanks for this tutoring video. many many thanks
FYI to ALL: There is a mistake in the video. In the else statement under the backtrack call, you need to unmark your last answer. This is the very heart of backtracking (unmarking) if you're not unmarking you're likely doing it wrong unless it is hypothetical marks on a recursive system stack (you pretend to Mark and recursively go down)
Dear CS Breakdown..After searching for 2 days i landed to your channel. You have explained very well this problem. I had difficulty in the backtracking part of the logic. Thank you so much... Can you please make vids for the DP as well
Instead of storing the queens position in a matrix you can just use a list that stores each queens row and column, then your queensSafe function becomes much more efficient: forEach(q in placedQueens) { if (q.col == col || (abs(q.row - row) == abs(q.col-col)) { return false; } } return true;
Hey, Sir... your explanations are awesome and easily understood... plz add more videos on NP completeness, approximation algorithms, Largest Common Subsequence... etc.. It would be really helpful.... if you consider doing more videos on Design and Analysis of Algorithms.
Is there a mistake in 3:32 for the last for loop? As a counter example, (7,2) will only check 3 grids with the given code. I believe the last for loop should be like: for(i=row+reset, j=col-reset; i>0 && j
at 10:36,you said it is safe to place queen at (3,2) after checking with your original queensafe function(not the optimized one). according to it,there is no queen In the same row and column.then we move to the reset part,for checking the diagonals.here the reset is 1. therefore it will start it's diagonal check from (2,1) to (4,3).after that it will check the other diagonal from (2,3),why it is not supposed to start from (1,4)?
When you say optimal solution, what do you mean? Aren't all feasible solutions for the n-queen problem also optimal? There is no such thing as a non optimal solution for the n-queen problem. Nice video btw.
Renan Silva Hi Renan, thanks for watching. If you didn't employ backtracking, the algorithm would attempt every possible configuration, even bad ones, to completion, which is unnecessarily computationally expensive. With backtracking, it checks on every queen placement, and if it doesn't work, it stops, goes back a level, and tries again. You can think of it almost like tree branches with each branch from the root being one of 4 of the first queens possible placements. Not using backtracking would ensure that the branches are all 4 nodes deep (assuming a 4x4 board). With backtracking, only the "placements that work", aka the optimal placements are 4 nodes deep, other branches are not. This saves the computer a fair amount of computation time as it no longer needs to create trees that are 4 (or n) nodes deep. It also can save a significant amount of space as well. On a 4x4 board, the savings is trivial, but we're assuming a board of size n, and we must assume that n is as big as the number of all known atoms in the universe (really freaking big!). So the concept of backtracking helps us find 'placements that work' without attempting every permutation to completion.
This is probably one of the best explanations on N-Queens Problem.
Thank You. Have a great day.
You have my utmost appreciation for such a thorough explanation of this n queens problem - which has puzzled me for years since I first knew this problem. I truly believe that if I could understand the thoughts and technique of solving n queens problem, I would get the least sense of programming, and I might really have a chance to become a programmer.
many thanks for this tutoring video. many many thanks
FYI to ALL: There is a mistake in the video. In the else statement under the backtrack call, you need to unmark your last answer. This is the very heart of backtracking (unmarking) if you're not unmarking you're likely doing it wrong unless it is hypothetical marks on a recursive system stack (you pretend to Mark and recursively go down)
Anybody noticed that what the graphics show are not queens... but kings?
Dear CS Breakdown..After searching for 2 days i landed to your channel.
You have explained very well this problem. I had difficulty in the backtracking part of the logic.
Thank you so much...
Can you please make vids for the DP as well
i did not understand how this code goes back to previous row when all the columns in the current row is unsafe ??
Thanks for this tutoring video with clear explanations.
what you put in the video actually is the king
Thank you so much.Have a blessed day.
Instead of storing the queens position in a matrix you can just use a list that stores each queens row and column, then your queensSafe function becomes much more efficient:
forEach(q in placedQueens) {
if (q.col == col || (abs(q.row - row) == abs(q.col-col)) {
return false;
}
}
return true;
Hey, Sir... your explanations are awesome and easily understood... plz add more videos on NP completeness, approximation algorithms, Largest Common Subsequence... etc.. It would be really helpful.... if you consider doing more videos on Design and Analysis of Algorithms.
In your efficient QueenSafe function I think the for loop should be for(i=1 to row) not for(i=1 to col).
How does the algo remove the true value which has been been but are not there in the final solution?
Thanks for uploading such conceptual tutorials....
Is there a mistake in 3:32 for the last for loop? As a counter example, (7,2) will only check 3 grids with the given code. I believe the last for loop should be like: for(i=row+reset, j=col-reset; i>0 && j
Very well explained. Subscribed!
at 10:36,you said it is safe to place queen at (3,2) after checking with your original queensafe function(not the optimized one). according to it,there is no queen In the same row and column.then we move to the reset part,for checking the diagonals.here the reset is 1. therefore it will start it's diagonal check from (2,1) to (4,3).after that it will check the other diagonal from (2,3),why it is not supposed to start from (1,4)?
Hey man. My algorithm backtracks but the previous queen is still stored in its location. Im not sure how to remove it. I stopped at time: 10:03
Sir there might be some error in your program...bcoz when the program backtracks.. It automatically discards the unnecessary values
is backtracking the same as hill climbing? if different, what would the
algorithm look like if hill climbing was used instead of backtracking?
where can i find the whole program?
Are backtracking algorithms a NFA?
can anyone explain to me how did he made it more efficient?
sir pls show it for 4*4 chess board
you guys are great!!!
Why are you using Kings instead of Queens? Unlike a Queen, a King can only attack what it is touching
When you say optimal solution, what do you mean? Aren't all feasible solutions for the n-queen problem also optimal? There is no such thing as a non optimal solution for the n-queen problem.
Nice video btw.
Renan Silva Hi Renan, thanks for watching. If you didn't employ backtracking, the algorithm would attempt every possible configuration, even bad ones, to completion, which is unnecessarily computationally expensive.
With backtracking, it checks on every queen placement, and if it doesn't work, it stops, goes back a level, and tries again. You can think of it almost like tree branches with each branch from the root being one of 4 of the first queens possible placements. Not using backtracking would ensure that the branches are all 4 nodes deep (assuming a 4x4 board).
With backtracking, only the "placements that work", aka the optimal placements are 4 nodes deep, other branches are not. This saves the computer a fair amount of computation time as it no longer needs to create trees that are 4 (or n) nodes deep. It also can save a significant amount of space as well.
On a 4x4 board, the savings is trivial, but we're assuming a board of size n, and we must assume that n is as big as the number of all known atoms in the universe (really freaking big!).
So the concept of backtracking helps us find 'placements that work' without attempting every permutation to completion.
how it backtracks?
there is no code satisfying about backtracking
thanks
bravo !!
thanks :)
CSBreakdown Awesome!
those are kings not queens noob