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

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>