Thread: Nested For Loops

Hi. I'm not very good at these. I'm working on it. Right now I'm stuck on the following problem. I am trying to figure out how to check the diagonals of an n x n chess board. I don't think I have to do more than figure out a 3 x 3, 4 x 4, or a 5 x 5. I am doing the n-Queens problem. I've been told that my problem can be solved using a nested for loop. I've been trying for a while to figure it out, but can't. This is what I have for the two "main" diagonals:

Code:

int left = 0; int right = 0;
for(int i = 0; i < N; i++)
{
    if (data->ary[i][i] == 'Q') left++;
    if (data->ary[i][(N-1)-i] == 'Q') right++;
}

if (left > 1 || right > 1) return false;

This works. When I try to figure out one of the other diagonals, I get stuck. I'm not using a nested for loop, and I guess I should be. For instance:
In a 3 x 3 board, I need to check diagonals 1, 2 and 2, 1. I can't even come up with code that will accomplish this:

Code:

int left2 = 0, right2 = 0;
for(int i = 1; i < N; i++) // changed i to 1
{
    if (data->ary[i][i-1] == 'Q') left2++;  // changed i+1 to i-1
    if (data->ary[i][N-(i+1)] == 'Q') right2++; // no
}

if(left2 > 1 || right2 > 1) return false;

I'm trying different things. I hate to be reduced to "trial and error" when trying to figure something out. Any ideas? Thanks, Steve

> nested for loop
You're too late - the nesting season for loops finished at the end of September. They've migrated and won't be back until next year

Get (or draw on paper) a chess board
Put a queen on the board, at some random spot on the board (not an edge for the moment)
Notice that there are 4 diagonals on which the queen can attack on

So, for a queen at position [x][y], we need to check

Code:

[x-i][y-i]  // towards top left
[x+i][y-i]  // towards bottom left
[x+i][y-i]  // towards top right
[x+i][y+i]  // towards bottom right

You increment i until one of the coordinates steps off the edge of the board, at which point you're done checking that diagonal.

Notice that if the queen is on an edge (or corner) already, that some of these loops will execute zero times.

Thanks again Salem. I figured it out after sweating over it for a long time:

Code:

for(int i = 0; i < N; i++)
{
    int rowCount = 0, colCount = 0;

    for(int j = 0; j < N; j++)
    {
        if (data->ary[i][j] == 'Q') rowCount++;
        if (data->ary[j][i] == 'Q') colCount++;
    }

    if (rowCount != 1 || colCount != 1) return false;

}

for(int i = 0; i < N-1; i++)
{
    int downwardRightUpper = 0, downwardRightLower = 0,
    downwardLeftUpper = 0, downwardLeftLower = 0;

    for(int j = 0, k = i; k < N; j++, k++)
    {
        if(data->ary[j][k] == 'Q') downwardRightUpper++;
        if(data->ary[k][j] == 'Q') downwardRightLower++;
        if(data->ary[j][N-1-k] == 'Q') downwardLeftUpper++;
        if(data->ary[k][N-1-j] == 'Q') downwardLeftLower++;
    }

    if(downwardRightUpper > 1 || downwardRightLower > 1
       downwardLeftUpper > 1 || downwardLeftLower > 1) return false;
}
    return true;
}

All the best,
Steve