C++ Tic-Tac-Toe – How to Check if 3 Elements in an Array are the Same Value

c++tic-tac-toe

I am making a TicTacToe game (fairly easy I know but I am a beginner) and I am almost done, my problem now is I am trying to have it check if a row, a column or a diagonal of the table have the same value, and recursively keep playing if it is not. My board looks like this :

char xToken = 'x';
char oToken = 'o';
char vertical = '|';
char horizontal = '-';

class Board {
public:
    const static int rows = 6;
    const static int cols = 6;
    char grid[rows][cols]{};

    Board() {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                grid[i][0] = '0' + i;
                grid[0][j] = '0' + j;

                if (j == 2 || j == 4) {
                    grid[i][j] = vertical;
                }

                if (i == 2 || i == 4) {
                    grid[i][j] = horizontal;
                }
            }
        }
    }

    void printBoard() {
        for (auto & i : grid) {
            for (char j : i) {
                cout << j << "\t";
            }
            cout << endl;
        }
    }
}

This is my play() function:

void play() {
        int i = 0;
        int j = 0;

        cout << "choose index you want to play in" << endl;
        cout << "Player 1" << endl;
        cout << "Row: " << endl;
        cin >> i;
        cout << "Column: " << endl;
        cin >> j;
        cout << i << ", " << j << endl;
        if (Board().grid[i][j] != vertical && Board().grid[i][j] != horizontal) {
            grid[i][j] = xToken;
            printBoard();
        }

        cout << "choose index you want to play in" << endl;
        cout << "Player 2" << endl;
        cout << "Row: " << endl;
        cin >> i;
        cout << "Column: " << endl;
        cin >> j;
        cout << i << ", " << j << endl;
        if (Board().grid[i][j] != vertical && Board().grid[i][j] != horizontal) {
            grid[i][j] = oToken;
            printBoard();
        }

        if(grid[i][j] == xToken) {
            cout << "You Win!" << endl;
        } else
            play();
    }

The idea is I am trying to recursively keep playing if we don't have 3 elements in a row, column or diagonal that are the same value. The very problem now is to find how to read the board so it can find the 3 in a row so the game stops

Best Answer

It is possible to perform a quadratic-time check by verifying whether there is a row, column or diagonal that contains only the same symbol.

Provided the matrix m, which represents the tic-tac-toe table, it is checked whether there is a combination of type m[i][j] for j∈[0, 3), which indicates the rows, and for i∈[0, 3), which indicates the columns, other than the two diagonals m[i][i] and m[i][3 - i] for each i∈[0, 3). If one of these combinations contain only the same symbol, which can be either a nought or a cross, it means that a player has won, otherwise not.

To make the algorithm simpler, it is possible to exploit the following trick: provided that a specific number is used to represent the nought or cross, all cells of a certain row, column or diagonal are summed depeand then the resulting number is compared to two constants. In this way, if the sum is the multiple of 6 and one of the specific nunbers, it is possible to conclude that the row, column or diagonal contain only the corresponding symbol, and therefore the player has won. For example, the nough can be represented by the number -1 and likewise the cross can be represented by the number 1.

Example:

std::pair<bool, bool> is_winner()
{
  int sumb = 0;
  int sumd = 0;
  for(int i = 0; i != 3; ++i){
    int sumr = 0;
    int sumc = 0;
    for(int j = 0; j != 3 ; ++j){
      sumr += m[3 * i + j];
      sumc += m[3 * j + i];
    }
    if(sumr == -3 || sumc == -3)
      return {true, false};
    if(sumr == 3 || sumc == 3)
      return {false, true};
    sumb += m[i][i];
    sumd += m[i][3 - i];
  }
  if(sumb == -3 || sumd == -3)
    return {true, false};
  if(sumb == 3 || sumd == 3)
    return {false, true};
  return {false, false};
}
Related Question