Check if an element of a 2D grid shares a diagonal, horizontal, or vertical with another element

Question

I'm working on the n-queens problem and part of it is checking whether a queen is threatened by another to determine a good board state.

I have a 2D array filled with 0s, in this example a 4x4:

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

I randomly populate each row with one queen, in this case represented by a 1:

0 0 1 0
1 0 0 0 
1 0 0 0
0 0 0 1

I need to check how many other pieces threaten a given piece. A queen is threatened if it shares a horizontal, diagonal, or vertical with another queen.

I'm not entirely sure how to traverse the array diagonally, however.

int checkThreats(vector<vector<int> > board, int r, int c) {
    int threats = 0;
    // checks vertical and horizontal
    for (int i = 0; i < board.size(); i++) {
        if (board[i][c] == 1 || board[r][i] == 1) {
            threats++;
        }
    }
    // it will count itself as a threat, so less one
    threats--;
    return threats;
}

This is the algorithm to check horizontally and vertically. Given a position on the board r, c, it checks how many queens exist in positions to the left, right, up, and down (in a cross + shape).

Take a co-ordinate r, c of 1, 0, the positions checked are marked with an x, with an o if a threat exists:

x 0 1 0
o x x x
o 0 0 0
x 0 0 1

In this case, threats == 1 as we don't count the original position.

My problem is trying to find pieces in an x shape, along the diagonals.

Answer 1

Through some trial and error, I was able to get an algorithm working. Here's the loops for traversing in all directions:

function check(arr, row, col) {
    for (i = 0; i < arr.size(); i++) {} // left/right can be iterated as normal
    for (i = 0; i < arr.size(); i++) {} // top/down can be the same
    // lower-right diagonal from (row, col)
    for (i = row+1, j = col+1; i < arr.size() && i < arr.size(); i++, j++) {}
    // upper-left diagonal from (row, col)
    for (i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {}
    // lower-left diagonal from (row, col)
    for (i = row-1, j = col+1; i >= 0 && j < arr.size(); i--, j++) {}
    // upper-right diagonal from (row, col)
    for (i = row+1, j = col-1; i < arr.size() && j >= 0; i++, j--) {}
}

This only works for square arrays of course.