«
»

Solving tic-tac-toe (Noughts and crosses)

January 20, 2012, 11:10 pm

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:

1
2
3
OO_
___
XX_

Here’s the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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
Category: Uncategorized  |  Comment (RSS)  |  Trackback

Leave a Reply