Loop through 2D array diagonally with random board size

Question

I was wondering how I can loop through a two dimentional array if the size of the array is random, e.g 6x6 or 10x10 etc. The idea is to search for four of the same kind of characters, 'x' or 'o'. This is typically needed for a board game.

    int main() {
            int array_size = 5; // Size of array
            int array_height = array_size;
            bool turn = true;           // true = player 1, false = player 2
            bool there_is_a_winner = false;
            char** p_connect_four = new char*[array_size];

            for (int i = 0; i < array_size; i++) // Initialise the 2D array
            { // At the same time set a value "_" as blank field
                 p_connect_four[i] = new char[array_size];
                 for (int j = 0; j < array_size; j++) {
                      p_connect_four[i][j] = '_';
                 }
            }
}

This is what I have so far, checking from [3][0] to [0][3]. But this requires me to add 2 more for loops to check [4][0] to [0][4] and [4][1] to [1][4] IF the size of the board was 5x5.

for (int i = 3, j = 0; i > 0 && j < array_size; i--, j++ ) {// CHECK DOWN up right from 3,0 -> 0,3
     if (p_connect_four[i][j] == p_connect_four[i - 1][j + 1] && p_connect_four[i][j] != '_' ) {
         check_diagonalRight++;
         if (check_diagonalRight == 3) {
             there_is_a_winner = true;
             break;
         }
     } 
     else {
             check_diagonalRight = 0;
     }
}
if (there_is_a_winner) { // Break while loop of game.
    break;
}

Obviously I want to check the whole board diagonally to the right regardless of the size of the board. Is there any other way than having 3 separate for loops for checking [3][0] -> [0][3] , [4][0] -> [0][4] and [4][1]-> [1][4] ?

Answer 1

for (i = array_size - 1, j = array_size - 2;
     i < array_size && i >= 0, j < array_size && j >= 0; j--)
{ // starts from [4][3] and loops to the left if arraysize = 5x5
      // but works on any size
     int k = i, l = j;

     for (k, l; k < array_size && k > 0, l < array_size && l > 0; k--, l++)
     {  // checks diagonally to the right
          if (check_diagonalRight == 3)
          {
              there_is_a_winner = true;
              break;
          }
          if (p_connect_four[k][l] == p_connect_four[k - 1][l + 1] &&
              p_connect_four[k][l] != '_')
          { //check up one square and right one square
              check_diagonalRight++;
          }
          else
          {
              check_diagonalRight = 0;
              // if its not equal, reset counter.
          }
     }
     if (there_is_a_winner) 
     {
         break; // break for loop
     }
}
if (there_is_a_winner)
{
    break; // break while loop of game
}

This checks up and right no matter the size, implement it for the other angles as well and it will work for any board size. You could potentially check right and left diagonal at once with nested loops.

Answer 2

I suggest to surround your board with extra special cases to avoid to check the bound.

To test each direction I suggest to use an array of offset to apply.

Following may help:

#include <vector>

using board_t = std::vector<std::vector<char>>;

constexpr const std::size_t MaxAlignment = 4;

enum Case {
    Empty = '_',
    X = 'X',
    O = 'O',
    Bound = '.'
};

enum class AlignmentResult { X, O, None };

// Create a new board, valid index would be [1; size] because of surrounding.
board_t new_board(std::size_t size)
{
    // Create an empty board
    board_t board(size + 2, std::vector<char>(size + 2, Case::Empty));

    // Add special surround.
    for (std::size_t i = 0; i != size + 2; ++i) {
        board[0][i] = Case::Bound;
        board[size + 1][i] = Case::Bound;
        board[i][0] = Case::Bound;
        board[i][size + 1] = Case::Bound;
    }
    return board_t;
}

// Test a winner from position in given direction.
AlignmentResult test(
    const board_t& board,
    std::size_t x, std::size_t y,
    int offset_x, int offset_y)
{
    if (board[x][y] == Case::Empty) {
        return AlignmentResult::None;
    }
    for (std::size_t i = 1; i != MaxAlignment; ++i) {
        // Following condition fails when going 'out of bound' thanks to Case::Bound, 
        // else you have also to check size...
        if (board[x][y] != board[x + i * offset_x][y + i * offset_y]) {
            return AlignmentResult::None;
        }
    }
    if (board[x][y] == Case::X) {
        return AlignmentResult::X;
    } else {
        return AlignmentResult::O;
    }
}

// Test a winner on all the board
AlignmentResult test(const board_t& board)
{
    // offset for direction. Use only 4 direction because of the symmetry.
    const int offsets_x[] = {1, 1, 1, 0};
    const int offsets_y[] = {-1, 0, 1, 1};
    const std::size_t size = board.size() - 1;

    for (std::size_t x = 1; x != size; ++x) {
        for (std::size_t y = 1; y != size; ++y) {
            for (std::size_t dir = 0; dir != 4; ++dir) { // for each directions
                auto res = test(board, x, y, offsets_x[dir], offsets_y[y]);
                if (res != AlignmentResult::None) {
                    return res;
                }
            }
        }
    }
    return AlignmentResult::None;
}

Answer 3

This will work perfectly fine for your program! I hope so!

int arraySize = 8;

for(int i=0, j=0; i<arraySize && j<arraySize; i++, j++)
{
    if((i == 0 && j == 0) || (i == arraySize - 1 && j == arraySize - 1))
    {
        continue;
    }
    else
    {
        int k = i;
        int l = j;
        //This Loop will check from central line (principal diagonal) to up right side (like slash sign / (representing direction))
        for(k, l; k>0 && l < arraySize - 1; k--, l++)
        {
            //Here check your condition and increment to your variable. like:
            if (p_connect_four[k][l] == p_connect_four[k - 1][l + 1] && p_connect_four[k][l] != '_' )
            {
                check_diagonalRight++;
            }
        }
        //You can break the loop here if check_diagonalRight != k then break
        k = i;
        l = j;
        //This Loop will check from central line (principal diagonal) to down left side (like slash sign / (representing direction))
        for(k, l; k<arraySize - 1 && l > 0; k++, l--)
        {
            //Here check your condition and increment to your variable. like:
            if (p_connect_four[k][l] == p_connect_four[k + 1][l - 1] && p_connect_four[k][l] != '_' )
            {
                check_diagonalRight++;
            }
        }
        if(check_diagonalRight == i+j+1)
        {
            there_is_a_winner = true;
            break;
        }
    }
}