N-Queens - Leetcode 51 #shorts

#coding #neetcode #python

[ShortFilmVD]

Having attempted to write a chess engine, I'd instinctively opt for a bitboard based solution. Using bitboards, we know that the diagonals are periodic, so shifting m(n+/-1) cells left or right where n is the board width and m is the number of shifts (moves along the diagonal), will traverse the diagonals. We can precompute diagonal masks in this fashion and use xors between piece board states to see if there's an interception. This probably isn't the optimum solution for this isolated problem, but it's flexible and scalable if you know that you may need to solve more chess/similar problems.

[merichinwo]

For a second I thought this was another Gotham chess video 😭

[k_gold]

All fun and games till the interviewer asks the N- knights problem

[austinnar]

x_delta = x0-x1
y_delta = y0-y1

can_attack = (
(x_delta == 0) |
(y_delta == 0) |
(abs(x_delta) == abs(y_delta))
)

[sandro-offq]

This is how my lecturer taught me to deal with this : if abs(r1 -r2) == abs(c1-c2) then they are on a diagonal. I have no clue how it works though lmao.

[tysonchicken]

If the slope between the two points is 1 or -1 they are on the same diagonal. Simple.

[asagiai]

I have a technique. I won't show it, cause it is quite long.
But the idea is diagonals can make square or something. This property of diagonal is useful for this technique.

Edits and Updates. (Sorry if my original comment is confusing)
For the technique to work, you need to have a reference point, and the special function.

The reference point is kind of hard to explain. But it's like in the intersection of pointA and pointB. I think it is the easiest way I can explain that.

Then you have the special function, which takes 2 arguments, (point, referencePoint)
Let just call it Special_Function. (Idk the proper name of that function yet)
The Special_Function will return a number (which will be useful)

So example you want to know if pointA(3, 5) and pointB(5, 7) is diagonal?
Let' use the reference point (5, 5) *intersection of pointA and pointB
So if we use the Special_Function like these

If Special_Function(pointA, (5, 5)) == Special_Function(pointB, (5, 5))
Return True //true means they are diagonal.
Else
Return False //not diagonal.

Btw the answer to that is true. So it's diagonal.
But if pointB is 6, 6 it will be false because the Special_Function will return different numbers.

I think I give a clear explanation, how the technique works. It's up to the reader to figure out the other details.

Note:
Just to be clear technically this technique is constant time.
It doesn't matter where you put the queens.

[ajaynarvare]

If for both queens x and y is equal or one greater or lesser then other queen then true

[venkatinator]

For diagonal isn’t it simply computing if the slope between the points == 1?

Deal with negative numbers with abs() etc.

[WoWUndad]

This is like the mark matrix rows o's problem but includes diagonal instead of just vertical and horizontal, right? And a condition instead of modifying the array

[balazsferencz]

This is not a complete solution. You also have to check if the figures have different colours. Otherwise they cannot attack each other.

[morchellemusic]

Hey do you teach all of this on Neetcode ? Thinking to go pro but it’s a bit expensive, you should make some discount for Spanish devs 😂

[kitanowitsch]

-If someone passes this coding problem in the interview does it guarantees he or she will be good as an engineer?
-No.

[thibauldnuyten]

The fuck kind of nonsense is that last statement?

"Here, I thought you how addition works, now you should be able to prove this calculus theorem"

[mpk]

I have written such a code. It was pure horror coming up with this logic.

[saurabhshrigadi]

Damn. i am too early to understand. Lets wait for people to comment

[sure]

Just imagine them as if they are knights and if they can attack. If yes, then as queens they cannot attack