## Solving tic-tac-toe (Noughts and crosses)

The following is a simple recursive solver for tic-tac-toe games, which I used to answer a Quora question. It’s hardcoded to solve the board:

```OO_
___
XX_
```

Here’s the code:

```#include <vector>
#include <iostream>

using namespace std;

void dump_board(vector<vector<int> > &board) {

for(size_t y=0;y<board.size();y++) {
for(size_t x=0;x<board.size();x++) {
if(board[x][y] == 0) cout << "_";
if(board[x][y] == 1) cout << "O";
if(board[x][y] == 2) cout << "X";
}
cout << endl;
}
cout << endl;
}

class Move {

public:

Move() {}

Move(int x_in,int y_in) : x(x_in), y(y_in) {}

int x;
int y;
};

int check_win(vector<vector<int> > &board) {

// cols
for(int x=0;x<board.size();x++) {
bool win=true;
for(int y=0;y<board[x].size();y++) {
if(board[x][y] != board[x][0]) win = false;
}
if((board[x][0] != 0) && (win == true)) return board[x][0];
}

// rows
for(int y=0;y<board.size();y++) {
bool win=true;
for(int x=0;x<board.size();x++) {
if(board[x][y] != board[0][y]) win = false;
}
if((board[0][y] != 0) && (win == true)) return board[0][y];
}

// diags
if((board[0][0] == board[1][1]) && (board[0][0] == board[2][2])) return board[0][0];
if((board[0][2] == board[1][1]) && (board[0][2] == board[2][0])) return board[0][2];

return -1;
}

vector<Move> get_available_moves(vector<vector<int> > &board) {

vector<Move> moves;

for(size_t x=0;x<board.size();x++) {
for(size_t y=0;y<board[x].size();y++) {
if(board[x][y] == 0) moves.push_back(Move(x,y));
}
}

return moves;
}

int play(int player,vector<vector<int> > board) {
vector<Move> moves = get_available_moves(board);

for(size_t n=0;n<moves.size();n++) {
vector<vector<int> > n_board = board;
n_board[moves[n].x][moves[n].y] = player;
int win = check_win(n_board);
if(win == 2) dump_board(n_board);

if(win == -1) {

if(player == 1) player = 2; else player = 1;
play(player,n_board);
}
}
}

int main(int argc,char **argv) {

vector<vector<int> > board(3,vector<int>(3,0));

board[0][0] = 1;
board[1][0] = 1;
board[0][2] = 2;
board[1][2] = 2;

dump_board(board);

play(2,board);
}
```

And the solutions found were:

```OOX
XOO
XXX

OOX
XO_
XXX

OO_
XO_
XXX

OOX
XOX
XXX

OOX
X_X
XXX

OOX
XX_
XXO

OOX
XXO
XXO

OO_
X__
XXX

OO_
XO_
XXX

OO_
_O_
XXX

OOX
OX_
XX_

OOX
OOX
XXX

OOX
O_X
XXX

OOX
OX_
XXO

OOX
_X_
XX_

OOX
OXX
XX_

OOX
O_X
XXX

OOX
_XX
XX_

OOX
__X
XXX

OOX
XXO
XXO

OOX
XOO
XXX

OOX
X_O
XXX

OOX
OXO
XX_

OOX
O_O
XXX

OOX
_XO
XX_

OOX
__O
XXX

OO_
___
XXX
```