I am trying to solve the N-Queens problem using backtracking. The link to the N-Queens problem can be found here, https://leetcode.com/problems/n-queens/ please visit that link for a better understanding of the problem. However, I just want to share a portion of the code I am finding hard to understand. Please can someone explain to me how the //check top, //check top - left, // check-top right works. I am finding it hard to wrap my head around this particular section of the code.
var isValid = function(board, row, col) {
const n = board.length;
// check top
for (let i = 0; i < row; i++) {
if (board[i][col] === 'Q') return false;
}
// check top-left
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] === 'Q') return false;
}
// check top-right
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] === 'Q') return false;
}
return true;
}
As far as I understand, we need to check whether the current position is "safe". So there are no Queens on the field which can hit the position. To do so, we need to check Vertical, Horizontal, and Diagonals (both). This code probably checks only rows above the current one.
The top-left code block does the following: Imagine, that the current position is x=4, y=3. So to check the left-top diagonal we need to look at the positions:
To do so we initially select the position let i = row - 1, j = col - 1 (one left and one top step from the current).
And then for every next step, move top-and-left: i--, j--
Repeat it until the border is hit: i >= 0 && j >= 0
The top-right block performs same operation, except we should move to the right (increase the X).