Checking the winning condition using arrays with for loops

[philip1999]

I want to create a game (connect four) in c++ using arrays and loops.

1) First I created a 8x5 board.

2) Second I am prompting the user to select the columns from 1 to 6.

3) My program is working fine. But, I am trouble in writing a winning statement.
Either 'X' or 'O' has 5 consecutive 'X' or 'O' in a line, then I need to
print the winning statement and exit the program.

Can anyone please help me how to check the winning condition.

#include <iostream>
#include <iomanip>
using namespace std;

const int rows = 8;
const int columns = 5;

//This function creates a 8x5 board
char matrix[rows][columns] = { '.','.','.','.','.',
								'.','.','.','.','.',
								'.','.','.','.','.',
								'.','.','.','.','.',
								'.','.','.','.','.',
								'.','.','.','.','.',
								'.','.','.','.','.',
								'.','.','.','.','.' };

//This function displays the board
void display()
{
	int width = 3;
	cout <<  setw(width) << "1" << setw(width) << "2" << setw(width) << "3" << setw(width) << "4" << setw(width) << "5" << setw(width) << '\n';
	for (int i = 0; i < rows; i++)
	{
		for (int j = 0; j < columns; j++)
		{
			cout << setw(3) << matrix[i][j] << setw(3);
		}
		cout << endl;
	}
	cout << setw(width) << "1" << setw(width) << "2" << setw(width) << "3" << setw(width) << "4" << setw(width) << "5" << setw(width) << '\n';
}


//This the main function that executes the player's selected column
void input(char player)
{
	int a;
	cout << "Enter the column" << endl;
	cin >> a;
	if (a > 0 && a < 6)
	{
		for (int i = 7; i >= 0; i--)
		{
			if (matrix[i][a - 1] == '.')
			{
				matrix[i][a - 1] = player;
				break;
			}
		}
	}
}



//This function changes the players between 'X' or 'O'
void togglePlayer(char &player)
{
	if (player == 'O')
	{
		player = 'X';
	}
	else player = 'O';
}



char win(char matrix[8][5])              //This is the function which I am trying to check the winning conditions
{
	for (int i = 0; i < 6; i++)
	{
		for (int j = 0; j < 6; j++)
		{
			matrix[i][j];
		}
	}
}


int main()
{
	char player = 'X';
	
	char declare;

	while (true)
	{
		display();
	
		input(player);
		
		togglePlayer(player);
		
		declare = win(matrix);
	}
	system("pause");
	
	return 0;
}

[nuderobmonkey]

You have these win conditions:

//1         | 2         | 3 | 4
//------------------------------------
//o o o o o | o         | o |         o
//              o         o         o
//                o       o       o
//                  o     o     o
//                    o | o | o 

You have to check for each position in matrix if any win condition is satisfied.

Example for win condition 4:

if ( (y >= 4) && (x < size_x-4) )
{
    if ( matrix[x][y] == player
      && matrix[x+1][y-1] == player
      && matrix[x+2][y-2] == player
      && matrix[x+3][y-3] == player
      && matrix[x+4][y-4] == player
    ) {
        std::cout << "Player " << player << " has won.\n";
    }
}

[philip1999]

Can you please elaborate more.

[poteto]

Might be more straight forward to check the surrounding pieces immediately after input, so instead of win() returning round end, input() would do that (and there are other ways to signal win conditions out there).

I would probably have it set up so that I have an array of of points called direction_states (just make a struct called point with x and y ints), I would make this have a size of 4, and I would make this switch signs by multiplying by -1 for 8 directions, starting from the top going clock wise:
{0,-1},{1,-1},{1,0},{1,1}
(this is using positive x as right, and positive y is down, it doesn't matter which 4 directions you choose as long as they are not on opposite sides)

Then in the input after you lay a piece (you can put this in a function) I would have an array of bools with the size of 4, all set to true (if you want a challenge you could try bit setting), then there will be 2 loops, the outside checks if any of the directions are true and if the counter if equal or over 4 (this loop does not manage the counter, this probably should be a while loop), the inside is going through the 4 direction states (technically 8 using 2 if statements).

What is going on here is you are checking both directions by first checking the index normally, and with another if statement checking the opposite side by multiplying the return of the direction state by -1 (and don't use an else if, if both sides have checkers you will increment by 2 in one pass). You need to check if the bool in the array is already false so you skip it, and check if the direction is not out of bounds, and then you check if the checker is your checker, if anything else you set the array index to false. If true you increment the counter.

I do feel like nuderobmonkey's way is probably more simpler, but my way is not as brute force as his, and my way is pretty close to O(1), but that's not something that matters when you only have a 8x5 grid :p

edit: I made a little flub, that, it turns out you need to turn the bool for the direction to false only if both the directions are false. That my be the crux to my solution since it ain't pretty to fix. Either have a temp bool that is false and set to true of either are true, or make the bool array into an int and make 0=false, 1=forward, 2=backward, and 3=both, and 3 as default... Maybe you should just google if there is a better way?

[nuderobmonkey]

If, as you said, a win is having five player's pieces in a line, then you could have four arrangements of some pieces by the same player result to a 'winning'. These arrangements I have drawn in the above table of my previous post.

I showed an example how to check for a win with an arrangement of column 4 from my table:

//
// Win arrangement 4:
// [0][0]
//    +----------------------------------->x
//    |
//    |
//    |               o ( == [x+4][y-4])
//    |             o ( == [x+3][y-3])
//    |           o ( == [x+2][y-2])
//    |         o ( == [x+1][y-1])
//    |       o ( == [x][y]) 
//    |
//    |
//    v y

// Checks any position of the matrix for a win with arrangement 4.
//
bool check_for_win_arrangement_4( char player, char matrix[8][5] )
{
    for (int x = 0; x < 8; ++x)   // for each column:
    {
        for (int y = 0; y < 5; ++y)  // for each row in column:
        {
        
            if (   // this is a real big condition header :)
              y>=4  &&  x < 8-4    // needed for not getting out of range
              && matrix[x][y]      == player  
              && matrix[x+1][y-1] == player
              && matrix[x+2][y-2] == player
              && matrix[x+3][y-3] == player
              && matrix[x+4][y-4] == player
            ) {
               return true;  
            }
        }
    }
    return false;  // All positions of the matrix where looped through and there was no winning collocation.
}

Feel free to ask if still something is unclear to you :-)

[nuderobmonkey]

@poteto: I' read your post but its unclear to me what you mean. If you want, post a piece of code here, hopefully that it clears something. Beside this, I believe at my example that It could made O(1) by considering and evaluating only a frame of these positions which could be influenced by player's choice. If Player's piece lays at [x][y], then we have to check only from [x-4][y-4] to [x+4][y+4].

[philip1999]

@nuderobmonkey Thank you very much for the excellent explanation.

[poteto]

The reason why I say my example is O(1) is because your example is exponentially more expensive the bigger the board is, and why I stepped back to say why would you care if the board is 8x5. And yea you are right that you could do [x-4][y-4] to [x+4][y+4] and maybe that may lead to an even simpler example but I'm not really good at figuring out the most elegant way of making that work in 1 single loop without much setup like bresenham's line.

This is a mock up, some spots have lazy psudo code.

struct point{
  int x;
  int y;
};

//up, upright, right, down right
point direction_state[4] = {{0,-1},{1,-1},{1,0},{1,1}};

const int connect_count = 4;

bool internal_win(char player, point new_checker)
{
  bool direction_flags[4] = {false};
  int counter = 0; //how many checkers are in line
  int j = 1; //I added this after because I forgot to mention this, this is the distance away from the new_checker
  while( counter < connect_count && (direction_flag[0] == true || .. || direction_flag[3] == true) )
  {
    for( i = 0 -> 3)
    {
      if(!direction_flag[i]) continue;

      bool dirty_flag = false; //this will check if this approach chokes

      //I skipped the bounds check, and yea it woundn't be much different than nukeerobmonkey's example but notably more uglier. I would recommend writing a simple collision check function
      if (*check if inside bounds* && 
          matrix[ new_checker.x + (j * direction_state[i].x) ][ new_checker.y + (j * direction_state[i].y) ] == player ){
        ++counter;
        dirty_flag = true;
      }
      
      //do the same as above, but note the negative, I kinda deviate away from my original explanation because I forgot x*-1 is equal to -x... 
      //This is pretty much just going in the opposite direction away from the new_checker.
      if (*check if inside bounds* && 
          matrix[ new_checker.x + (j * -direction_state[i].x) ][ new_checker.y + (j * -direction_state[i].y) ] == player ){
        ++counter;
        dirty_flag = true;
      }
        
      if(dirty_flag == false)
        direction_flags[i] = false;
    }
    ++j;
  }
  return (counter >= 4);
}

The great thing about my style is that you can extend the game by making the connection count higher or lower with a change of a int, and have an almost infinitely big board with minimal expense. (but, why tho... 🤔)