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
RSS