Problem
Design an algorithm to figure out if someone has won in a game of tic-tac-toe.
Solution
I've written a game of tic-tac-toe in Java, and my current method of determining the end of the game accounts for the following possible scenarios for the game being over:- The board is full, and no winner has yet been declared: Game is a draw.
- Cross has won.
- Circle has won.
We know a winning move can only happen after X or O has made their most recent move, so you can only search row/column with optional diag that are contained in that move to limit your search space when trying to determine a winning board. Also since there are a fixed number of moves in a draw tic-tac-toe game once the last move is made if it wasn't a winning move it's by default a draw game.
public class TicTacToe {
enum State{Blank, X, O};
int n = 3;
State[][] board = new State[n][n];
int moveCount;
void Move(int x, int y, State s){
if(board[x][y] == State.Blank){
board[x][y] = s;
}
moveCount++;
//check end conditions
//check col
for(int i = 0; i < n; i++){
if(board[x][i] != s)
break;
if(i == n-1){
//report win for s
}
}
//check row
for(int i = 0; i < n; i++){
if(board[i][y] != s)
break;
if(i == n-1){
//report win for s
}
}
//check diag
if(x == y){
//we're on a diagonal
for(int i = 0; i < n; i++){
if(board[i][i] != s)
break;
if(i == n-1){
//report win for s
}
}
}
//check anti diag (thanks rampion)
for(int i = 0;i<n;i++){
if(board[i][(n-1)-i] != s)
break;
if(i == n-1){
//report win for s
}
}
//check draw
if(moveCount == (n^2 - 1)){
//report draw
}
}
}
References
- http://tianrunhe.wordpress.com/2012/05/14/check-if-someone-has-won-tic-tac-toe/
- http://stackoverflow.com/questions/1056316/algorithm-for-determining-tic-tac-toe-game-over
- http://codereview.stackexchange.com/questions/40676/tic-tac-toe-get-winner-algorithm
- http://stackoverflow.com/questions/6952607/ai-strategy-for-gomoku-a-variation-of-tic-tac-toe?rq=1







0 comments:
Post a Comment