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