Tic Tac Win

16.4 Tic Tac Win: Design an algorithm to figure out if someone has won a game of tic-tac-toe.

• Brain storm:

  • My approach is just to brute force check (nested for loop) after a players turn. A 3x3 should be small enough to have the time it take to do this to be negligible. O(n^2). I would however treat a nxn board differently.

  • If we know a players move, then all that would be necessary to check is the appropriate row, column and diagonal it sits on. That is only 3 checks. This works, because we know all previous moves did not result in a win / loss. This method is efficient with no extra space. This is the approach is chose.

  • Another approach would be to maintain a could of each row,column and diagonal for each player. After a player makes a move, we check whether or not the dimension of the row / col / diag = the count. This is a lot of extra space though, an isn't any better than the previous.

  • Another interesting approach would be to use a hash table that maps the board (key) into a boolean value (win or lose). The goal here would be to represent each board uniquely with a key. Generating a key would be O(n^2) anyway though.

enum State {
    Empty, X, O
};

class Board {
public:
    Board(const unsigned int N) : N(N) {
        board = new vector<vector<State>>;
        board->resize(N, vector<State>(N));
        for (int i = 0; i < N; i++) {
            fill(board->at(i).begin(), board->at(i).end(), State::Empty);
        }
    }

    void makeMove(State move, pair<int, int> pos) {
        current_pos = pos;
        current_move = move;
        board->at(pos.second).at(pos.first) = move;
        if (hasWon()) { cout << "Player " << move << " Winner" << endl; }
    }

    // O(4N)
    bool hasWon() {
        // check for pair @ state [col][row]
        // 1) horizontal - change rows, constant column
        bool hor, vert, dia1, dia2;
        hor = vert = dia1 = dia2 = true;
        for (int i = 0; i < N; i++) {
            if (!(board->at(current_pos.second).at(i) == current_move)) {
                hor = false;
                break;
            }
        }

        // 2) vertical - change columns, constant row
        for (int i = 0; i < N; i++) {
            if (!(board->at(i).at(current_pos.first) == current_move)) {
                vert = false;
                break;
            }
        }

        // 3) diagonal /
        int j = 0;
        for (int i = N - 1; i >= 0; i--) {
            if (!(board->at(i).at(j) == current_move)) {
                ++j;
                dia1 = false;
                break;
            }
        }

        // 4) diagonal \'
        for (int i = 0; i < N; i++) {
            if (!(board->at(i).at(i) == current_move)) {
                dia2 = false;
                break;
            }
        }
        return (hor || vert || dia1 || dia2);
    }



private:
    State current_move;
    pair<int, int> current_pos;

    const unsigned int N;
    // I would use std::array, but I dont know size statically at compile time
    vector<vector<State>> *board;


};


int main() 
{
    Board board(3);
    board.makeMove(State::X, { 0,0 });
    board.makeMove(State::X, { 1,1 });
    board.makeMove(State::X, { 2,2 });

    Board board2(3);
    board2.makeMove(State::X, { 0,0 });
    board2.makeMove(State::O, { 1,1 });
    board2.makeMove(State::X, { 2,2 });
    board2.makeMove(State::O, { 0,2 });
    board2.makeMove(State::X, { 2,0 });
    board2.makeMove(State::O, { 1,0 });
    board2.makeMove(State::X, { 2,1 });
}