# 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 });

}

Last modified 3yr ago