Simple C++ program to check win in TicTacToe

Question

Given a string of size 9 that represents a tic tac toe board, determine if X or O has won, or if the board is in an invalid state. Any other character aside from x, X, o, O represents an empty spot on the board.

Input: 012345678

Board:

0 1 2
3 4 5
6 7 8

TicTacToe.cpp

#include "tictactoe.h"
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>

using std::string;
using std::vector;

const int kBoardSize = 9;
const int kBoardLength = std::sqrt(kBoardSize);

TicTacToeState CheckTicTacToeBoard(std::string board) {
  if (board.size() != kBoardSize) {
    return TicTacToeState::InvalidInput;
  }

  std::transform(board.begin(), board.end(), board.begin(), ::tolower);
  size_t numberOfO = std::count(board.begin(), board.end(), 'o');
  size_t numberOfX = std::count(board.begin(), board.end(), 'x');

  if (numberOfO > numberOfX || numberOfX > numberOfO + 1) {
    return TicTacToeState::UnreachableState;
  }

  bool xWon = winDetection(board, 'x');
  bool oWon = winDetection(board, 'o');

  if (xWon && oWon) {
    return TicTacToeState::UnreachableState;
  } else if (xWon) {
    return TicTacToeState::Xwins;
  } else if (oWon) {
    return TicTacToeState::Owins;
  }
  return TicTacToeState::NoWinner;
}

bool winDetection(string board, char marker) {
  bool rowWin = false, colWin = false, rightDiagWin = true, leftDiagWin = true;

  for (int i{0}, rightDiagIndex{0}, leftDiagIndex{kBoardLength - 1};
       i < kBoardLength; ++i, rightDiagIndex += (kBoardLength + 1),
                         leftDiagIndex += (kBoardLength - 1)) {
    bool row = true, col = true;

    int rowIndex = kBoardLength * i, colIndex = i;
    for (int j{0}; j < kBoardLength; ++j) {
      col &= (board[colIndex] == marker);
      row &= (board[rowIndex] == marker);

      rowIndex++;
      colIndex += kBoardLength;
    }

    colWin |= col;
    rowWin |= row;

    rightDiagWin &= board[rightDiagIndex] == marker;
    leftDiagWin &= board[leftDiagIndex] == marker;
  }

  return (rowWin || colWin || rightDiagWin || leftDiagWin);
}

TicTacToe.h

#pragma once

#include <string>

enum TicTacToeState { UnreachableState, Xwins, Owins, NoWinner, InvalidInput };

TicTacToeState CheckTicTacToeBoard(std::string board);

bool winDetection(std::string board, char marker);

Answer 1

1. Computing a square-root is unnecessary; further, it only works when kBoardSize is a perfect square. Prefer

   const int kBoardLength = 3;
   const int kBoardSize = kBoardLength * kBoardLength;
   

2. Your test for unreachability is not complete. You verify that O has made no more moves than X, but you really need to check that the winner made the last move. If X won, then should have numberOfX = numberOfO + 1; if O won then should have numberOfO = numberOfX. It should be clear how to add these checks to your CheckTicTacToeBoard method.

3. A more overarching tension in this code is: should the board size really be a constant? The code is written so abstractly as to support any board size. But then the board size is fixed to a constant. I would choose one of the following directions to proceed in:

   • Commit to a board size of 9. In this case, I would recommend hard-coding the win conditions in winDetection. There are only 8 ways to win, so the resulting code would be a lot cleaner.

   • Allow arbitrary board sizes. In this case, you should accept a boardLength argument. Further, you will have to refine the notion of an UnreachableState. For example, in 5-by-5 tic tac toe, the following state is unreachable, your code would return Xwins:

     x x x x x
     o . o . o
     x x x x x
     o . o . o
     o o x o o
     

Answer 2

Adding to the review of Benjamin Kuykendall, pay attention especially to const correctness to protect from unintended errors and to possible allow the compiler to optimize better.

• For winDetection, pass the board by const-ref. I see you didn't do this for CheckTicTacToeBoard because the function modifies the input by converting to lowercase.

• In CheckTicTacToeBoard, make numberOfO and numberOfX const. Similarly, make xWon and oWon const.

• In winDetection, since we are writing C++ and not C, there is no reason to declare variables at the beginning of the scope of the function unless they are not needed. In particular, rightDiagWin and leftDiagWin should be declared just before returning, and you can also make both of them const as well.

• In e.g., your for-loop, you use preincrement for the loop variable i, but inside the loop you do postincrement as rowIndex++. Prefer to always use the preincrement since it is not returning a copy of the variable (though I believe this should always be optimized away by the compiler if it's not needed, but it doesn't hurt to be safe).

Answer 3

Over all, it's not bad. Here are some things that may help you improve your program.

Use const references where practical

The board arguments for both the CheckTicTacToeBoard() and winDetection() functions could both actually be const std::string& instead of std::string with a small change to the code shown below.

Make a single pass through the data where practical

The current code makes three passes through the data just counting the number of X's and O's.

std::transform(board.begin(), board.end(), board.begin(), ::tolower);
size_t numberOfO = std::count(board.begin(), board.end(), 'o');
size_t numberOfX = std::count(board.begin(), board.end(), 'x');

I'd suggest instead that one can accomplish this in a single pass without needing to alter the passed board:

size_t numberOfO{0};
size_t numberOfX{0};
for (auto ch : board) {
    switch (ch) {
        case 'O':
        case 'o':
            ++numberOfO;
            break;
        case 'X':
        case 'x':
            ++numberOfX;
            break;
        default:
            break;
    }
}

Check the winning condition more thoroughly

Once the counts have both been obtained, we can determine which player must have most recently played. If numberOfO == numberOfX, then O just played, otherwise X did. If the game is in a valid state, only the player that just played could possibly be the winner, which suggests that if O just played and X is the winner, the board is actually in an invalid state.

Add a condition to the return

There is one more condition that it would be useful to check for, which is a tie game. Right now the routine just returns NoWinner which is technically correct, but if all the squares are filled and no further moves are possible, it would make more sense to specially identify and return that unique state.

Use only necessary #includes

The #include <vector> line is not necessary and can be safely removed.

Eliminate the need for <cmath>

The only reason that <cmath> is needed is the use of std::sqrt but I'd suggest that it would be better to instead define the constants like this:

static constexpr int kBoardLength = 3;
static constexpr int kBoardSize = kBoardLength * kBoardLength;

The use of constexpr can allow the compiler to make even better optimizations that would be available with const int and the use of static tells the compiler that the constant is local to this file. Also the way this is constructed, the board is always square which might not be the case otherwise.

Consider an alternate strategy

Another possible way to do this would be to minimize the number of iterations throught the data structure, keeping track of which wins are possible and which are not. Here's one way that might be written:

#include "TicTacToe.h"
#include <string>

static constexpr int kBoardLength = 3;
static constexpr int kBoardSize = kBoardLength * kBoardLength;

enum class Token { isX, isO, isEmpty };

static Token classify(char square) {
    switch (square) {
        case 'O':
        case 'o':
            return Token::isO;
            break;
        case 'X':
        case 'x':
            return Token::isX;
            break;
    }
    return Token::isEmpty;
}

TicTacToeState CheckTicTacToeBoard(const std::string& board) {
  if (board.size() != kBoardSize) {
    return TicTacToeState::InvalidInput;
  }
  auto state{TicTacToeState::NoWinner};
  size_t numberOfO{0};
  size_t numberOfX{0};
  for (std::size_t i{0}; i < kBoardLength; ++i) {
      bool orow{classify(board[i * kBoardLength]) == Token::isO};
      if (orow) {
          ++numberOfO;
      }
      bool ocol{classify(board[i]) == Token::isO};
      bool xrow{classify(board[i * kBoardLength]) == Token::isX};
      if (xrow) {
          ++numberOfX;
      }
      bool xcol{classify(board[i]) == Token::isX};
      bool odiag{i==0 && classify(board[0]) == Token::isO};
      bool orevdiag{i==0 && classify(board[kBoardLength - 1]) == Token::isO};
      bool xdiag{i==0 && classify(board[0]) == Token::isX};
      bool xrevdiag{i==0 && classify(board[kBoardLength - 1]) == Token::isX};
      for (std::size_t j{1}; j < kBoardLength; ++j) {
          switch(classify(board[i * kBoardLength + j])) {
              case Token::isO:
                  xrow = false;
                  ++numberOfO;
                  break;
              case Token::isX:
                  orow = false;
                  ++numberOfX;
                  break;
              default:
                  xrow = false;
                  orow = false;
          }
          switch(classify(board[i + j * kBoardLength])) {
              case Token::isO:
                  xcol = false;
                  break;
              case Token::isEmpty:
                  xcol = false;
              case Token::isX:
                  ocol = false;
                  break;
          }
          if (i==0) {
              switch(classify(board[j + j * kBoardLength])) {
                  case Token::isO:
                      xdiag = false;
                      break;
                  case Token::isEmpty:
                      xdiag = false;
                  case Token::isX:
                      odiag = false;
                      break;
              }
              switch(classify(board[j * kBoardLength + kBoardLength - j - 1])) {
                  case Token::isO:
                      xrevdiag = false;
                      break;
                  case Token::isEmpty:
                      xrevdiag = false;
                  case Token::isX:
                      orevdiag = false;
                      break;
              }
          }
      }
      if (orow || ocol || odiag || orevdiag) {
          if (state == TicTacToeState::Xwins) {
            return TicTacToeState::UnreachableState;
          }
          state = TicTacToeState::Owins;
      }
      if (xrow || xcol || xdiag || xrevdiag) {
          if (state == TicTacToeState::Owins) {
            return TicTacToeState::UnreachableState;
          }
          state = TicTacToeState::Xwins;
      }
  }
  if ((numberOfO == numberOfX && state == TicTacToeState::Xwins) ||
      (numberOfO + 1 == numberOfX && state == TicTacToeState::Owins) || 
      (numberOfX - numberOfO > 1) 
      ) {
    return TicTacToeState::UnreachableState;
  }
  if (numberOfX + numberOfO == kBoardSize && state == TicTacToeState::NoWinner) {
      state = TicTacToeState::TieGame;
  }
  return state;
}

Write a test harness

Writing a test harness is a good way to test the code and to provide for reviewers of your code because it shows which things you've considered and also provides an example of how you expect the code to be used. Here's the test harness I wrote for the version of the code shown above:

#include "TicTacToe.h"
#include <iostream>

std::ostream& operator<<(std::ostream &out, const TicTacToeState& state) {
    switch (state) {
        case UnreachableState:
            out << "Unreachable";
            break;
        case Xwins:
            out << "X wins";
            break;
        case Owins:
            out << "O wins";
            break;
        case NoWinner:
            out << "no winner";
            break;
        case InvalidInput:
            out << "invalid input";
            break;
        case TieGame:
            out << "Tie Game";
            break;
        default:
            out << "I don't even know what this is?!";
            break;
    }
    return out;
}

struct Test {
    const char *s;
    TicTacToeState result;
};

std::ostream& operator<<(std::ostream& out, const Test& t) {
    auto result{CheckTicTacToeBoard(t.s)};
    if (result == t.result) {
        return out << "OK  " << t.s << " ==> " << result;
    } 
    return out << "bad  " << t.s << " ==> " << result << ", expected " << t.result;
}

int main(int argc, char *argv[]) {
    Test tests[]{
        {"012345678", NoWinner},
        {"0123456789", InvalidInput},
        {"", InvalidInput},
        {"xXx345678", UnreachableState},
        {"xXxo4o67o", UnreachableState},
        {"ooox4x6xx", UnreachableState},
        {"xoxoxxoxo", TieGame},
        {"x...x...x", UnreachableState},
        {"xo..xo.ox", UnreachableState},  // diagonal
        {".ox.xoxo.", UnreachableState},  // reverse diagonal
        {"xo..xo..x", Xwins},  // diagonal
        {".ox.xox..", Xwins},  // reverse diagonal
        {"ox..ox.xo", Owins},  // diagonal
        {".xo.oxox.", Owins},  // reverse diagonal
        {"ox..ox..o", UnreachableState},  // diagonal
        {".xo.oxo..", UnreachableState},  // reverse diagonal
        {".o.......", UnreachableState}, 
        {".x.......", NoWinner}, 
        {"xxx...ooo", UnreachableState}, 
        {"xx....ooo", UnreachableState}, 
        {"xxx...oo.", Xwins}, // row
        {"..x..xoox", Xwins},  // col
    };
    for (const auto &t : tests) {
        std::cout << t << '\n';
    }
}