Nested For Loops

This is a discussion on Nested For Loops within the C++ Programming forums, part of the General Programming Boards category; Hi. I'm not very good at these. I'm working on it. Right now I'm stuck on the following problem. I ...

  1. #1
    diligentStudent()
    Join Date
    Apr 2002
    Posts
    79

    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

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,497
    > 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.

  3. #3
    diligentStudent()
    Join Date
    Apr 2002
    Posts
    79

    Thumbs up

    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Nested array vs. tree
    By KONI in forum Tech Board
    Replies: 1
    Last Post: 06-07-2007, 04:43 AM
  2. deriving classes
    By l2u in forum C++ Programming
    Replies: 12
    Last Post: 01-15-2007, 04:01 PM
  3. nested switch issue
    By fsu_altek in forum C Programming
    Replies: 3
    Last Post: 02-15-2006, 09:29 PM
  4. Displaying Data from a Nested Structure
    By shazg2000 in forum C++ Programming
    Replies: 1
    Last Post: 01-09-2005, 09:16 AM
  5. Nested Classes
    By manofsteel972 in forum C++ Programming
    Replies: 4
    Last Post: 11-21-2004, 10:57 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21