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