N-Queens - Coding Interview Question (Backtracking Algorithm)

[@claytor920]

The commentary captions of the interviewer is appreciated. It's always hard to hear what is said yet it's important.

[@fra1285]

You forgot to discuss the time/space complexity of the problem, would be interesting hearing about it.

[@ankush363]

He is actually a story teller of programming questions.Respect!!!

[@Supersonicboom7]

Isn't this a trick question? You do now that there is a mathematical solution that predetermines one of the boards valid layout? For any NxN matrix the first queen will be placed in the N/2 column on the first row if N is even, and (N/2) + 1 if N is odd. The second queen is always placed on the second row in the first column. Then simply add a Queen one to the left and two down from the initial queens and repeat till you fill the board. If N is odd then the last queen will go in the bottom right hand corner. I know this is a coding question but really is the point of an algorithm simplistic fully predetermined solution?? Though if you had to generate all valid layouts then that is another issue...

[@vamsi54krishna]

thanks for basic idea, I improvised it. After 1st queen keep placing queens in incremental rows with alternating first and last available columns. Ex: N=7 0-index 2D, 1Q (3,3) 2Q(1,0) 3Q(2,6) 4Q(3,1) 5Q(4,5) 6Q( 5,2 ) 7Q(6,4)

[@guitarockdude]

This doesn't work for a 4X4 matrix. If you place the first queen in the first row on the (4/2) 2nd column, and the second queen on the second row on the first column, they intersect diagonally.

[@StochasticHorizons]

I think the video is also about showing how to speak in an interview, ask questions, etc.

[@nawabsonu]

Can we also add discussion on the complexity of the algorithms?

[@meenameiss]

Can't you have an hash table with size 4n-2 to recreate all possible diagonals (either with dy = -1 or dy = 1) and just notice that queens in the same dy=1 diagonal have (Value = x+y) equal. Therefore you can fill the first 2n-1 elements with 1 (queen in diagonal) for the diagonal with value "Value". The other diagonal (second 2n-1) can be calculated with an analogy to the second one by changing the axis and changing the coordinates to n-x. Would this make significant difference in verification speed for greater n's ?

[@ishanmistry1143]

Hey Irfan. Thanks for making these videos these are really helpful. I struggle a lot with string related questions like permutations, substring questions. I can get the solutions but most of the times they have worst case time complexity. It would be great to know how you approach these type of questions. This will help me to build my thought process :)

[@rafaelzamora6622]

There might be an issue in your isSafe( ) function where your check is overlapping with the current queen. At which point the queen will always collide with itself. A simple if queen is equal to current queen skip this check and continue with the loop would fix it.

[@bkim2]

Also, although I don't think this was part of the question, but in the event there are multiple iterations, this algorithm only returns the first set that comes true.

[@yurilsaps]

I struggled in the code until i realized this... a big mistake of the video

[@s8ulGoldy]

I guess your program will fail on 4x4 layout as you hard coded your first queen at 0,0. Your should have incremented it from 0 to n.

[@yurilsaps]

code in Javascript that computes all the possibilities github.com/yuriaps/code-training/blob/main/n_queen.js

[@_ityadi]

Time complexity for the solution would be O(n!) that is Big-O of n factorial

[@pascalfragnoud2846]

why would you output an array of tuples for the coordinates ? A simple array does the job, indices being the column or row number, and the values being the positions... like, [1, 3, 0, 2] : 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0

[@crothert]

thank you so much for this free content

[@mrchharus7315]

Can we do it by formulas??? Maybe that will be easy and short for any n×n order . Reply would be appreciated 😊

[@sarunhaunted]

The current solution will fail when the user tries to place only one queen in a one by one board as the issafe logic will return false since row and r will be zero. Just include a flag in your main while loop to prevent getting to the if (istrue && placequeen(col+1)) condition when the column is index is zero. Overall, i love your videos :) Thanks for sharing

[@chamnil8666]

Thank you so much sir,this is my first video of your chnnel,I am a new javascript learner,if you could please put the js code in your videos ,very much appreciated.Thank you so much.

[@CraftandDogs]

I am glad you added the caption. It is hard to hear her.

[@pabloruiz577]

What about doing BFS where each level is the new column you iterate through and all the the nodes at that level are the (non-threatened) [row][level] ? Then, if solution not found, increment the row and start BFS for new initial point [0,row++] and so on. If the BFS finds any node at level N = board_size, then you have found a solution

[@maxzriver]

In this case the board is empty and we can find many solutions depending on the focal point (PF), the basic series to which it belongs or the maximum principal series (SPM) + partitive series (SP), of the family to which it belongs said board considering the criteria of dps + dp (differences of overlap and position differences) With these same criteria a board with a queen within the

[@HarshPatel-kh9gz]

There is another easy solution, look for the pattern such that none of the exception or conditions matter! --> For example, take a 5*5 board. Now it doesn't matter if you take N-rows and put a queen on row[0], because you can only place one queen in that row no matter what position. Now from that position, the sequence is 0,2,4,1,3. You can start from whatever position in rows and columns, but you will get the same sequence. If there are N-columns, then this sequence repeats itself!

[@HarshPatel-kh9gz]

And by the way, this is only O(n) for time complexity.

[@yoyonel1808]

It seems that this code/algo return just 1 solution/queens placement (if exist) ... and not all ? That's right ? I don't see the a recursion or loop, to iterate/process on all possibilities ... maybe i'm wrong :p Anyway thx for your video !

[@bismeetsingh352]

Why the placequeen(col+1)??

[@maxzriver]

My calculator program that verifies if the Nreinas can be attacked uses my dps + dp method and manages to discover if the distribution is correct this for the castes where there is a queen on the board

[@ShortGiant1]

Great intuition at 5:05. That's was the part that had thrown me off earlier.

[@kajalchanchalani4165]

Can you please cover problems like least common ancestor in trees and also some typical graph problems?

[@prapulkrishna]

Excellent 👏🏻

[@helpingtechvideos]

Thanks for this explanation

[@heikki4359]

But how fast is this? O(n^n)? In that case you can solve very large boards!

[@DanHenriqueSC]

O(n!)

[@hiteshgaur3071]

How did you assume that place queen should be called for only 0th column, should we not try for all the columns until we get a solution? I am sorry, if I am unable to understand the problem.

[@abhayagarwal227]

think it in this way that ,for column 0 there should exist a row where queen is present ...so no need to call multiple time col 0 to n-1.....hope it helps.

[@rudra-thandavam]

I wrote his algorithm and it fails for n=4. it only assumes queen start at [0,0]. Right answer should be the first queen at [0,2].

[@jamesward2946]

This is just fantastic

[@vishalcbansal426]

REALLY GOOD...

[@dachep]

Great video, is it possible to make the interviewer a bit louder?

[@IrfanBaqui]

Jared Gilmore we'll try in future videos

[@therealmujtaba]

Irfan, stop blinking your right eye to the interviewer, its inappropriate lol . thanks for the great videos.

[@akarshrastogi3682]

2:15 vs 13:40 The interviewer stood up and moved !

[@mohammadizhan4960]

Sir please cover some graph theory problems and thanks for this amazing content it helping us a lot

[@mohycs]

The only good thing about this channel is the problem statements, not the solution or coding proficiency on the board lol.