Algorithm for Determining Tic Tac Toe Game Over

Question

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    Unfortunately  to do so  it reads through a predefined set of these scenarios from a table  This isn t necessarily bad considering that there are only 9 spaces on a board  and thus the table is somewhat small  but is there a better algorithmic way of determining if the game is over  The determination of whether someone has won or not is the meat of the problem  since checking if 9 spaces are full is trivial    The table method might be the solution  but if not  what is  Also  what if the board were not size n 9  What if it were a much larger board  say n 16  n 25  and so on  causing the number of consecutively placed items to win to be x 4  x 5  etc  A general algorithm to use for all n     9  16  25  36

User · Accepted Answer

You 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.

edit: this code is for an n by n board with n in a row to win (3x3 board requries 3 in a row, etc)

edit: added code to check anti diag, I couldn't figure out a non loop way to determine if the point was on the anti diag so thats why that step is missing

public class TripleT {

    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)
        if(x + y == n - 1){
            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 == (Math.pow(n, 2) - 1)){
            //report draw
        }
    }
}

User · Answer

I like this algorithm as it uses a 1x9 vs 3x3 representation of the board   private int   board   new int 9   private static final int   START   new int     0  3  6  0  1  2  0  2    private static final int   INCR    new int     1  1  1  3  3  3  4  2    private static int SIZE   3         Determines if there is a winner in tic-tac-toe board      return   code 0  for draw    code 1  for  X     code -1  for  Y      public int hasWinner         for  int i   0  i  lt  START length  i              int sum   0          for  int j   0  j  lt  SIZE  j                  sum    board START i    j   INCR i                      if  Math abs sum     SIZE                return sum   SIZE                      return 0

User · Answer

Another option  generate your table with code  Up to symmetry  there are only three ways to win  edge row  middle row  or diagonal  Take those three and spin them around every way possible   def spin g   return set  g  turn g   turn turn g    turn turn turn g      def turn g   return tuple tuple g y  x  for y in  0 1 2   for x in  2 1 0    X s    X   XXX   X  X  X sss   s  s  s  ways to win      spin  XXX  sss  sss                    spin  sss  XXX  sss                    spin   X s s                           s X s                           s s X       These symmetries can have more uses in your game-playing code  if you get to a board you ve already seen a rotated version of  you can just take the cached value or cached best move from that one  and unrotate it back   This is usually much faster than evaluating the game subtree    Flipping left and right can help the same way  it wasn t needed here because the set of rotations of the winning patterns is mirror-symmetric

User · Answer

If you have boarder field 5 5 for examle  I used next method of checking   public static boolean checkWin char symb      int SIZE   5           for  int i   0  i  lt  SIZE-1  i                  for  int j   0  j  lt SIZE-1   j                        vertical checking             if  map 0  j     symb  amp  amp  map 1  j     symb  amp  amp  map 2  j     symb  amp  amp  map 3  j     symb  amp  amp  map 4  j     symb  return true          j 0                             horisontal checking             if map i  0     symb  amp  amp  map i  1     symb  amp  amp  map i  2     symb  amp  amp  map i  3     symb  amp  amp  map i  4     symb  return true      i 0                     diagonal checking  5 5          if  map 0  0     symb  amp  amp  map 1  1     symb  amp  amp  map 2  2     symb  amp  amp  map 3  3     symb  amp  amp  map 4  4     symb  return true          if  map 4  0     symb  amp  amp  map 3  1     symb  amp  amp  map 2  2     symb  amp  amp  map 1  3     symb  amp  amp  map 0  4     symb  return true           return false               I think  it s more clear  but probably is not the most optimal way

User · Answer

Here is my solution using an 2-dimensional array   private static final int dimension   3  private static final int     board   new int dimension  dimension   private static final int xwins   dimension   1  private static final int owins   dimension   -1   public static void main String   args        Scanner scanner   new Scanner System in       int count   0      boolean keepPlaying   true      boolean xsTurn   true      while  keepPlaying            xsTurn    count   2    0           System out print  Enter i-j in the format             if  xsTurn                System out println   X plays                else               System out println   O plays                        String result   null          while  result    null                result   parseInput scanner  xsTurn                     String   xy   result split               int x   Integer parseInt xy 0            int y   Integer parseInt xy 1            keepPlaying   makeMove xsTurn  x  y           count              if  xsTurn            System out print  X          else           System out print  O              System out println   WON        printArrayBoard board      private static String parseInput Scanner scanner  boolean xsTurn        String line   scanner nextLine        String   values   line split  -        int x   Integer parseInt values 0        int y   Integer parseInt values 1        boolean alreadyPlayed   alreadyPlayed x  y       String result   null      if  alreadyPlayed            System out println  Already played in this x-y  Retry          else           result        x         y            return result     private static boolean alreadyPlayed int x  int y        System out println  x-y      x    -    y     board x  y       board x  y        if  board x  y     0            return true            return false     private static void printArrayBoard int     board        for  int i   0  i  lt  dimension  i              int   height   board i           for  int j   0  j  lt  dimension  j                  System out print height j                            System out println             private static boolean makeMove boolean xo  int x  int y        if  xo            board x  y    1        else           board x  y    -1            boolean didWin   checkBoard        if  didWin            System out println  keep playing              return didWin     private static boolean checkBoard           check horizontal     int   horizontalTotal   new int dimension       for  int i   0  i  lt  dimension  i              int   height   board i           int total   0          for  int j   0  j  lt  dimension  j                  total    height j                     horizontalTotal i    total            for  int a   0  a  lt  horizontalTotal length  a              if  horizontalTotal a     xwins    horizontalTotal a     owins                System out println  horizontal                return false                        check vertical     int   verticalTotal   new int dimension        for  int j   0  j  lt  dimension  j              int total   0          for  int i   0  i  lt  dimension  i                  total    board i  j                     verticalTotal j    total            for  int a   0  a  lt  verticalTotal length  a              if  verticalTotal a     xwins    verticalTotal a     owins                System out println  vertical                return false                        check diagonal     int total1   0      int total2   0      for  int i   0  i  lt  dimension  i              for  int j   0  j  lt  dimension  j                  if  i    j                    total1    board i  j                             if  i     dimension - 1 - j                     total2    board i  j                                     if  total1    xwins    total1    owins            System out println  diagonal 1            return false            if  total2    xwins    total2    owins            System out println  diagonal 2            return false            return true

User · Answer

you can use a magic square http   mathworld wolfram com MagicSquare html if any row  column  or diag adds up to 15 then a player has won

User · Answer

Here is a solution I came up with  this stores the symbols as chars and uses the char s int value to figure out if X or O has won  look at the Referee s code   public class TicTacToe       public static final char BLANK     u0000       private final char     board      private int moveCount      private Referee referee       public TicTacToe int gridSize            if  gridSize  lt  3              throw new IllegalArgumentException  TicTacToe board size has to be minimum 3x3 grid            board   new char gridSize  gridSize           referee   new Referee gridSize              public char     displayBoard             return board clone               public String move int x  int y            if  board x  y     BLANK              return       x         y      is already occupied           board x  y    whoseTurn            return referee isGameOver x  y  board x  y     moveCount              private char whoseTurn             return moveCount   2    0    X     O              private class Referee           private static final int NO OF DIAGONALS   2          private static final int MINOR   1          private static final int PRINCIPAL   0          private final int gridSize          private final int   rowTotal          private final int   colTotal          private final int   diagonalTotal           private Referee int size                gridSize   size              rowTotal   new int size               colTotal   new int size               diagonalTotal   new int NO OF DIAGONALS                      private String isGameOver int x  int y  char symbol  int moveCount                if  isWinningMove x  y  symbol                   return symbol     won the game                if  isBoardCompletelyFilled moveCount                   return  Its a Draw                return  continue                      private boolean isBoardCompletelyFilled int moveCount                return moveCount    gridSize   gridSize                     private boolean isWinningMove int x  int y  char symbol                if  isPrincipalDiagonal x  y   amp  amp  allSymbolsMatch symbol  diagonalTotal  PRINCIPAL                   return true              if  isMinorDiagonal x  y   amp  amp  allSymbolsMatch symbol  diagonalTotal  MINOR                   return true              return allSymbolsMatch symbol  rowTotal  x     allSymbolsMatch symbol  colTotal  y                      private boolean allSymbolsMatch char symbol  int   total  int index                total index     symbol              return total index    gridSize    symbol                     private boolean isPrincipalDiagonal int x  int y                return x    y                     private boolean isMinorDiagonal int x  int y                return x   y    gridSize - 1                      Also here are my unit tests to validate it actually works  import static com agilefaqs tdd demo TicTacToe BLANK  import static org junit Assert assertArrayEquals  import static org junit Assert assertEquals   import org junit Test   public class TicTacToeTest       private TicTacToe game   new TicTacToe 3         Test     public void allCellsAreEmptyInANewGame             assertBoardIs new char         BLANK  BLANK  BLANK                      BLANK  BLANK  BLANK                      BLANK  BLANK  BLANK                   Test expected   IllegalArgumentException class      public void boardHasToBeMinimum3x3Grid             new TicTacToe 2               Test     public void firstPlayersMoveMarks X OnTheBoard             assertEquals  continue   game move 1  1            assertBoardIs new char         BLANK  BLANK  BLANK                      BLANK   X   BLANK                      BLANK  BLANK  BLANK                   Test     public void secondPlayersMoveMarks O OnTheBoard             game move 1  1           assertEquals  continue   game move 2  2            assertBoardIs new char         BLANK  BLANK  BLANK                      BLANK   X   BLANK                      BLANK  BLANK   O                    Test     public void playerCanOnlyMoveToAnEmptyCell             game move 1  1           assertEquals   1 1  is already occupied   game move 1  1                Test     public void firstPlayerWithAllSymbolsInOneRowWins             game move 0  0           game move 1  0           game move 0  1           game move 2  1           assertEquals  X won the game    game move 0  2                Test     public void firstPlayerWithAllSymbolsInOneColumnWins             game move 1  1           game move 0  0           game move 2  1           game move 1  0           game move 2  2           assertEquals  O won the game    game move 2  0                Test     public void firstPlayerWithAllSymbolsInPrincipalDiagonalWins             game move 0  0           game move 1  0           game move 1  1           game move 2  1           assertEquals  X won the game    game move 2  2                Test     public void firstPlayerWithAllSymbolsInMinorDiagonalWins             game move 0  2           game move 1  0           game move 1  1           game move 2  1           assertEquals  X won the game    game move 2  0                Test     public void whenAllCellsAreFilledTheGameIsADraw             game move 0  2           game move 1  1           game move 1  0           game move 2  1           game move 2  2           game move 0  0           game move 0  1           game move 1  2           assertEquals  Its a Draw    game move 2  0               private void assertBoardIs char     expectedBoard            assertArrayEquals expectedBoard  game displayBoard               Full solution  https   github com nashjain tictactoe tree master java

User · Answer

I made some optimization in the row  col  diagonal checks  Its mainly decided in the first nested loop if we need to check a particular column or diagonal  So  we avoid checking of columns or diagonals saving time  This makes big impact when the board size is more and a significant number of the cells are not filled    Here is the java code for that        int gameState int values      int boardSz          boolean colCheckNotRequired     new boolean boardSz    default is false     boolean diag1CheckNotRequired   false      boolean diag2CheckNotRequired   false      boolean allFilled   true        int x count   0      int o count   0         Check rows        for  int i   0  i  lt  boardSz  i              x count   o count   0          for  int j   0  j  lt  boardSz  j                  if values i  j     x val x count                if values i  j     o val o count                if values i  j     0                                colCheckNotRequired j    true                  if i  j diag1CheckNotRequired   true                  if i   j    boardSz - 1 diag2CheckNotRequired   true                  allFilled   false                    No need check further                 break                                  if x count    boardSz return X WIN          if o count    boardSz return O WIN                          check cols        for  int i   0  i  lt  boardSz  i              x count   o count   0          if colCheckNotRequired i     false                        for  int j   0  j  lt  boardSz  j                      if values j  i     x val x count                    if values j  i     o val o count                      No need check further                 if values i  j     0 break                            if x count    boardSz return X WIN              if o count    boardSz return O WIN                       x count   o count   0         check diagonal 1        if diag1CheckNotRequired    false                for  int i   0  i  lt  boardSz  i                  if values i  i     x val x count                if values i  i     o val o count                if values i  i     0 break                    if x count    boardSz return X WIN          if o count    boardSz return O WIN             x count   o count   0         check diagonal 2        if  diag2CheckNotRequired    false                for  int i   boardSz - 1 j   0  i  gt   0  amp  amp  j  lt  boardSz  i-- j                  if values j  i     x val x count                if values j  i     o val o count                if values j  i     0 break                    if x count    boardSz return X WIN          if o count    boardSz return O WIN          x count   o count   0             if  allFilled    true                for  int i   0  i  lt  boardSz  i                  for  int j   0  j  lt  boardSz  j                      if  values i  j     0                        allFilled   false                      break                                               if  allFilled    false                    break                                     if  allFilled          return DRAW       return INPROGRESS

User · Answer

I just want to share what I did in Javascript  My idea is to have search directions  in grid it could be 8 directions  but search should be bi-directional so 8   2   4 directions  When a player does its move  the search starts from the location  It searches 4 different bi-directions until its value is different from the player s stone O or X   Per a bi-direction search  two values can be added but need to subtract one because starting point was duplicated  getWin x y value searchvector    if  arguments length  2      var checkTurn   this state squares y  x     var searchdirections     -1 -1   0 -1   1 -1   -1 0      return searchdirections reduce  maxinrow searchdirection   gt Math max this getWin x y checkTurn searchdirection  this getWin x y checkTurn  -searchdirection 0  -searchdirection 1    maxinrow  0     else     if  this state squares y  x    value        var result   1      if         x searchvector 0   gt   0  amp  amp  x searchvector 0   lt  3  amp  amp         y searchvector 1   gt   0  amp  amp  y searchvector 1   lt  3         result    this getWin x searchvector 0  y searchvector 1  value searchvector       return result      else       return 0           This function can be used with two parameters  x y   which are coordinates of the last move  In initial execution  it calls four bi-direction searches recursively with 4 parameters  All results are returned as lengths and the function finally picks the maximum length among 4 search bi-directions   x000D   x000D  class Square extends React Component     constructor props        super props       this state    value null         render         return          lt button className  square  onClick       gt  this props onClick    gt           this props value         lt  button gt                class Board extends React Component     renderSquare x y        return  lt Square value  this state squares y  x   onClick       gt  this handleClick x y     gt         handleClick x y        const squares   JSON parse JSON stringify this state squares        if   squares y  x   amp  amp   this state winner          squares y  x    this setTurn          this setState  squares  squares      gt           console log  Max in a row made by last move   squares y  x       this getWin x y -1             if  this getWin x y   4  this setState  winner squares y  x                           setTurn         var prevTurn   this state turn      this setState  turn prevTurn     X     O   X         return prevTurn           getWin x y value searchvector        if  arguments length  2          var checkTurn   this state squares y  x         var searchdirections     -1 -1   0 -1   1 -1   -1 0          return searchdirections reduce  maxinrow searchdirection   gt Math max this getWin x y checkTurn searchdirection  this getWin x y checkTurn  -searchdirection 0  -searchdirection 1    maxinrow  0         else         if  this state squares y  x    value            var result   1          if             x searchvector 0   gt   0  amp  amp  x searchvector 0   lt  3  amp  amp             y searchvector 1   gt   0  amp  amp  y searchvector 1   lt  3             result    this getWin x searchvector 0  y searchvector 1  value searchvector           return result          else           return 0                         constructor props        super props       this state           squares  Array 3  fill Array 3  fill null          turn   X         winner  null              render         const status    this state winner  Next player    this state turn      this state winner  won         return          lt div gt           lt div className  status  gt  status  lt  div gt           lt div className  board-row  gt             this renderSquare 0 0              this renderSquare 0 1              this renderSquare 0 2            lt  div gt           lt div className  board-row  gt             this renderSquare 1 0              this renderSquare 1 1              this renderSquare 1 2            lt  div gt           lt div className  board-row  gt             this renderSquare 2 0              this renderSquare 2 1              this renderSquare 2 2            lt  div gt         lt  div gt                class Game extends React Component     render         return          lt div className  game  gt           lt div className  game-board  gt             lt Board   gt           lt  div gt           lt div className  game-info  gt             lt div gt     status     lt  div gt             lt ol gt     TODO     lt  ol gt           lt  div gt         lt  div gt                                                             ReactDOM render     lt Game   gt     document getElementById  root      x000D  body     font  14px  Century Gothic   Futura  sans-serif    margin  20px     ol  ul     padding-left  30px      board-row after     clear  both    content        display  table      status     margin-bottom  10px      square     background   fff    border  1px solid  999    float  left    font-size  24px    font-weight  bold    line-height  34px    height  34px    margin-right  -1px    margin-top  -1px    padding  0    text-align  center    width  34px      square focus     outline  none      kbd-navigation  square focus     background   ddd      game     display  flex    flex-direction  row      game-info     margin-left  20px    x000D   lt script src  https   cdnjs cloudflare com ajax libs react 16 6 3 umd react production min js  gt  lt  script gt   lt script src  https   cdnjs cloudflare com ajax libs react-dom 16 6 3 umd react-dom production min js  gt  lt  script gt   lt div id  errors  style     background   c00    color   fff    display  none    margin  -20px -20px 20px    padding  20px    white-space  pre-wrap    gt  lt  div gt   lt div id  root  gt  lt  div gt   lt script gt  window addEventListener  mousedown   function e      document body classList add  mouse-navigation      document body classList remove  kbd-navigation        window addEventListener  keydown   function e      if  e keyCode     9        document body classList add  kbd-navigation        document body classList remove  mouse-navigation            window addEventListener  click   function e      if  e target tagName      A   amp  amp  e target getAttribute  href                  e preventDefault            window onerror   function message  source  line  col  error      var text   error   error stack    error   message      at     source         line         col          errors textContent    text     n     errors style display          console error    function old      return function error         errors textContent    Array prototype slice call arguments  join          n       errors style display           old apply this  arguments          console error    lt  script gt  x000D   x000D   x000D

User · Answer

This is similar to Osama ALASSIRY s answer  but it trades constant-space and linear-time for linear-space and constant-time  That is  there s no looping after initialization   Initialize a pair  0 0  for each row  each column  and the two diagonals  diagonal  amp  anti-diagonal   These pairs represent the accumulated  sum sum  of the pieces in the corresponding row  column  or diagonal  where   A piece from player A has value  1 0  A piece from player B has value  0 1    When a player places a piece  update the corresponding row pair  column pair  and diagonal pairs  if on the diagonals   If any newly updated row  column  or diagonal pair equals either  n 0  or  0 n  then either A or B won  respectively   Asymptotic analysis    O 1  time  per move  O n  space  overall    For the memory use  you use 4  n 1  integers    two elements n rows   two elements n columns   two elements two diagonals   4 n   4 integers   4 n 1  integers   Exercise  Can you see how to test for a draw in O 1  time per-move  If so  you can end the game early on a draw

User · Answer

How about this pseudocode   After a player puts down a piece at position  x y    col row diag rdiag 0 winner false for i 1 to n   if cell x i  player then col     if cell i y  player then row     if cell i i  player then diag     if cell i n-i 1  player then rdiag   if row n or col n or diag n or rdiag n then winner true   I d use an array of char  n n   with O X and space for empty    simple  One loop  Five simple variables  4 integers and one boolean  Scales to any size of n  Only checks current piece  No magic

User · Answer

This is a really simple way to check       public class Game           Game player1   new Game  x        Game player2   new Game  o         char piece       Game char piece           this piece   piece         public void checkWin Game player            check horizontal win     for  int i   0  i  lt   6  i    3             if  board i     player piece  amp  amp                  board i   1     player piece  amp  amp                  board i   2     player piece              endGame player                 check vertical win     for  int i   0  i  lt   2  i               if  board i     player piece  amp  amp                  board i   3     player piece  amp  amp                  board i   6     player piece              endGame player                 check diagonal win     if   board 0     player piece  amp  amp              board 4     player piece  amp  amp              board 8     player piece                 board 2     player piece  amp  amp              board 4     player piece  amp  amp              board 6     player piece          endGame player

User · Answer

a non-loop way to determine if the point was on the anti diag    if  x   y    n - 1

User · Answer

I don t know Java that well  but I do know C  so I tried adk s magic square idea  along with Hardwareguy s search restriction       tic-tac-toe c    to compile        gcc -o tic-tac-toe tic-tac-toe c    to run          tic-tac-toe  include  lt stdio h gt      the two types of marks available typedef enum   Empty 2  X 0  O 1  NumMarks 2   Mark  char const MarkToChar      XO        a structure to hold the sums of each kind of mark typedef struct   unsigned char of NumMarks     Sum      a cell in the board  which has a particular value  define MAGIC NUMBER 15 typedef struct     Mark mark    unsigned char const value    size t const num sums    Sum   const sums 4     Cell    define NUM ROWS 3  define NUM COLS 3     create a sum for each possible tic-tac-toe Sum row NUM ROWS     0   Sum col NUM COLS     0   Sum nw diag    0   Sum ne diag    0       initialize the board values so any row  column  or diagonal adds to    MAGIC NUMBER  and so they each record their sums in the proper rows  columns     and diagonals Cell board NUM ROWS  NUM COLS                  Empty  8  3     amp row 0    amp col 0    amp nw diag            Empty  1  2     amp row 0    amp col 1             Empty  6  3     amp row 0    amp col 2    amp ne diag                      Empty  3  2     amp row 1    amp col 0             Empty  5  4     amp row 1    amp col 1    amp nw diag   amp ne diag            Empty  7  2     amp row 1    amp col 2                       Empty  4  3     amp row 2    amp col 0    amp ne diag            Empty  9  2     amp row 2    amp col 1             Empty  2  3     amp row 2    amp col 2    amp nw diag                 print the board void show board void      size t r  c    for  r   0  r  lt  NUM ROWS  r             if  r  gt  0    printf  --- --- --- n          for  c   0  c  lt  NUM COLS  c                 if  c  gt  0    printf               printf    c    MarkToChar board r  c  mark              printf   n               run the game  asking the player for inputs for each side int main int argc  char   argv        size t m    show board      printf  Enter moves as    lt row gt   lt col gt     no quotes  zero indexed  n      for  m   0  m  lt  NUM ROWS   NUM COLS  m             Mark const mark    Mark   m   NumMarks       size t c  r          read the player s move     do             printf   c s move     MarkToChar mark          fflush stdout         scanf   d  d    amp r   amp c         if  r  gt   NUM ROWS    c  gt   NUM COLS                  printf  illegal move  off the board   try again n                  else if  board r  c  mark    Empty                  printf  illegal move  already taken   try again n                  else                 break                    while  1                Cell   const cell    amp  board r  c          size t s            update the board state       cell- gt mark   mark        show board              check for tic-tac-toe       for  s   0  s  lt  cell- gt num sums  s                    cell- gt sums s - gt of mark     cell- gt value          if  cell- gt sums s - gt of mark     MAGIC NUMBER                      printf  tic-tac-toe   c wins  n   MarkToChar mark              goto done                                printf  stalemate    nobody wins    n    done    return 0      It compiles and tests well       gcc -o tic-tac-toe tic-tac-toe c     tic-tac-toe              --- --- ---              --- --- ---              Enter moves as      no quotes  zero indexed    X s move  1 2              --- --- ---            X   --- --- ---              O s move  1 2   illegal move  already taken   try again   O s move  3 3   illegal move  off the board   try again   O s move  2 2              --- --- ---            X   --- --- ---            O   X s move  1 0              --- --- ---    X       X   --- --- ---            O   O s move  1 1              --- --- ---    X   O   X   --- --- ---            O   X s move  0 0    X         --- --- ---    X   O   X   --- --- ---            O   O s move  2 0    X         --- --- ---    X   O   X   --- --- ---    O       O   X s move  2 1    X         --- --- ---    X   O   X   --- --- ---    O   X   O   O s move  0 2    X       O   --- --- ---    X   O   X   --- --- ---    O   X   O   tic-tac-toe  O wins      tic-tac-toe              --- --- ---              --- --- ---              Enter moves as      no quotes  zero indexed    X s move  0 0    X         --- --- ---              --- --- ---              O s move  0 1    X   O     --- --- ---              --- --- ---              X s move  0 2    X   O   X   --- --- ---              --- --- ---              O s move  1 0    X   O   X   --- --- ---    O         --- --- ---              X s move  1 1    X   O   X   --- --- ---    O   X     --- --- ---              O s move  2 0    X   O   X   --- --- ---    O   X     --- --- ---    O         X s move  2 1    X   O   X   --- --- ---    O   X     --- --- ---    O   X     O s move  2 2    X   O   X   --- --- ---    O   X     --- --- ---    O   X   O   X s move  1 2    X   O   X   --- --- ---    O   X   X   --- --- ---    O   X   O   stalemate    nobody wins        That was fun  thanks   Actually  thinking about it  you don t need a magic square  just a count for each row column diagonal   This is a little easier than generalizing a magic square to n  times  n matrices  since you just need to count to n

User · Answer

I was asked the same question in one of my interviews  My thoughts  Initialize the matrix with 0  Keep 3 arrays 1 sum row  size n  2  sum column  size n  3  diagonal  size 2   For each move by  X  decrement the box value by 1 and for each move by  0  increment it by 1  At any point if the row column diagonal which has been modified in current move has sum either -3 or  3 means somebody has won the game  For a draw we can use above approach to keep the moveCount variable   Do you think I am missing something    Edit  Same can be used for nxn matrix  Sum should be even  3 or -3

User · Answer

Ultra-efficient Bit-boarding Let s store the game in a binary integer  and evaluate everything using just one step   We know that X s moves occupy 9 bits  xxx xxx xxx We know that O s moves occupy 9 bits  ooo ooo ooo  So  a board position could be represented in just 18 bits  xoxoxo xoxoxo xoxoxo But  whilst this might look efficient  it doesn t help us with determining a win   We need a more useful bit pattern    one that not only encodes the moves  but also encodes the rows  columns and diagonals in a reasonable way  I would do this by using a clever integer value for each board position  Choosing a more useful representation First  we need a board notation  just so that we can discuss this   So  similar to Chess  lets number the rows with letters and the columns with numbers - so we know which square we re talking about      1 2 3     A a1 a2 a3   B b1 b2 b3   C c1 c2 c3     And let s give each a binary value  a1   100 000 000 100 000 000 100 000   Row A Col 1  top left corner  a2   010 000 000 000 100 000 000 000   Row A Col 2  top edge  a3   001 000 000 000 000 100 000 100   Row A Col 3  top right corner  b1   000 100 000 010 000 000 000 000   Row B Col 1  left edge  b2   000 010 000 000 010 000 010 010   Row B Col 2  middle square  b3   000 001 000 000 000 010 000 000   Row B Col 4  right edge  c1   000 000 100 001 000 000 000 001   Row C Col 1  bottom left corner  c2   000 000 010 000 001 000 000 000   Row C Col 2  bottom edge  c3   000 000 001 000 000 001 001 000   Row C Col 3  bottom right corner       where  the binary values encode which rows  columns and diagonals the position appears in    we ll look at how this works this later  We will use these values to build two representations of the game  one for X and one for O  X starts with an empty board   000 000 000 000 000 000 000 000 O starts with an empty board   000 000 000 000 000 000 000 000  Let s follow X s moves  O would be the same principle   X plays A1    so we OR  the X board  with value A1 X plays A2    so we OR with value A2 X plays A3    so we OR with value A3  What does that do to X s board value    a1   100 000 000 100 000 000 100 000     ORed with a2   010 000 000 000 100 000 000 000     ORed with a3   001 000 000 000 000 100 000 100     equals    XB   111 000 000 100 100 100 100 100 Reading from left to right we see that X has    111  All positions  in Row 1   o  A win  Yay   000  No positions  in Row 2 000  No positions  in Row 3 100  One position  Only the first position of Column 1 100  One position  Only the first position of Column 1 100  One position  Only the first position of Column 1 100  One position  Only the first position of Diagonal 1 100  One position  Only the first position of Diagonal 2  You ll notice that whenever X  or O  has a winning line  then there will also be three consecutive bits in his board value   Precisely Where those three bits are  dictates which row column diagonal he won on  So  the trick now is to find a way to check for this  three consecutive bits set  condition in a single operation  Modifying the values to make detection easier To assist with this  let s change our bit representation so that there are always ZEROs between the groups of three  Because 001 110 is also three consecutive bits - but they are NOT a valid win     so  a fixed zero spacer would break these up  0 001 0 110  So  after adding some spacing ZEROes  we can be confident that ANY three consecutive set bits in X s or O s board value indicates a win  So  our new binary values  with zero-padding  look like this    a1   100 0 000 0 000 0 100 0 000 0 000 0 100 0 000 0   0x80080080  hex  a2   010 0 000 0 000 0 000 0 100 0 000 0 000 0 000 0   0x40008000 a3   001 0 000 0 000 0 000 0 000 0 100 0 000 0 100 0   0x20000808 b1   000 0 100 0 000 0 010 0 000 0 000 0 000 0 000 0   0x08040000 b2   000 0 010 0 000 0 000 0 010 0 000 0 010 0 010 0   0x04004044 b3   000 0 001 0 000 0 000 0 000 0 010 0 000 0 000 0   0x02000400 c1   000 0 000 0 100 0 001 0 000 0 000 0 000 0 001 0   0x00820002 c2   000 0 000 0 010 0 000 0 001 0 000 0 000 0 000 0   0x00402000 c3   000 0 000 0 001 0 000 0 000 0 001 0 001 0 000 0   0x00200220  You ll notice that each  quot winline quot  of the board now requires 4 bits  8 winlines x 4 bits each   32 bits   Isn t that convenient         Parsing We could shift through all the bits looking for three consecutive bits  but that will take 32 shifts x 2 players    and a counter to keep track   It s slow  We could AND with 0xF  looking for the value 8 4 2 14   And this would allow us to check 4 bits at a time   Cutting the number of shifts by a quarter   But again  this is slow  So  instead  let s check ALL of the possibilities at once    Ultra-efficient win detection Imagine we wanted to evaluate the A3 A1 B2 C3 case  a win on the diagonal  a1   100 0 000 0 000 0 100 0 000 0 000 0 100 0 000 0  OR a3   001 0 000 0 000 0 000 0 000 0 100 0 000 0 100 0  OR b2   000 0 010 0 000 0 000 0 010 0 000 0 010 0 010 0  OR c3   000 0 000 0 001 0 000 0 000 0 001 0 001 0 000 0     XB   101 0 010 0 001 0 100 0 010 0 101 0 111 0 110 0   See the win  on Diagonal 1    Now  let s check it for a win  by efficiently merging three bits into one    Simply use   XB AND  XB  lt  lt  1  AND  XB  gt  gt  1  in other words  XB ANDed with  XB shifted left  AND  XB shiftted right  Let s try an example    10100100001010000100101011101100   whitespaces removed for easy shifting  AND  01001000010100001001010111011000   XB shifted left  AND  01010010000101000010010101110110   XB shifted left  Equals  00000000000000000000000001000000  See that   Any non-zero result means a win  But  where did they win Want to know where they won   Well  you could just use a second table   0x40000000   RowA 0x04000000   RowB 0x00400000   RowC 0x00040000   Col1 0x00004000   Col2 0x00000400   Col3 0x00000040   Diag1 0x00000004   Diag2  However  we can be smarter than that  as the pattern is VERY regular  For example  in assembly you can use BSF  Bit Scan Forward  to find the number of leading zeros   Then subtract 2 and then  4  Shift Right 2  - to get a number between 0 and 8    which you can use as an index to look up into an array of win strings     quot wins the top row quot    quot takes the middle row  quot        quot steals the diagonal  quot    This makes the whole game logic    from move checking  to board updating and right through to win loss detection and an appropriate success message  all fit in a handful of ASM instructions      it s tiny  efficient and ultrafast  Checking whether a move is playable Obviously  ORing  quot X s board quot  with  quot O s board quot    ALL POSITIONS So  you can check if a move is valid quite easily   If user chooses UpperLeft  this position has an integer value   Just check the  AND  of this Value with  XB OR OB         if the result is nonzero  then the position is already in use  Conclusion If you re looking for efficient ways to process a board  don t start with a board object   Try to discover some useful abstraction  See if the states fit within an integer  and think about what an  easy  bitmask to process would look like   With some clever choice of integers to represent moves  positions or boards    you might find that the entire game can be played  evaluated and scored VERY efficiently - using simply bitwise logic  Closing apologies BTW I m not a regular here on StackOverflow  so I hope this post wasn t too chaotic to follow   Also  please be kind     quot Human quot  is my second language and I m not quite fluent yet    Anyway  I hope this helps someone

User · Answer

I developed an algorithm for this as part of a science project once   You basically recursively divide the board into a bunch of overlapping 2x2 rects  testing the different possible combinations for winning on a 2x2 square   It is slow  but it has the advantage of working on any sized board  with fairly linear memory requirements   I wish I could find my implementation

User · Answer

Not sure if this approach is published yet  This should work for any m n board and a player is supposed to fill  winnerPos  consecutive position  The idea is based on running window   private boolean validateWinner int x  int y  int player          same col     int low   x-winnerPos-1      int high   low      while high  lt   x winnerPos-1            if isValidPos high  y   amp  amp  isFilledPos high  y  player                 high                if high - low    winnerPos                    return true                          else               low   high   1              high   low                         same row     low   y-winnerPos-1      high   low      while high  lt   y winnerPos-1            if isValidPos x  high   amp  amp  isFilledPos x  high  player                 high                if high - low    winnerPos                    return true                          else               low   high   1              high   low                      if high - low    winnerPos            return true               diagonal 1     int lowY   y-winnerPos-1      int highY   lowY      int lowX   x-winnerPos-1      int highX   lowX      while highX  lt   x winnerPos-1  amp  amp  highY  lt   y winnerPos-1            if isValidPos highX  highY   amp  amp  isFilledPos highX  highY  player                 highX                highY                if highX - lowX    winnerPos                    return true                          else               lowX   highX   1              lowY   highY   1              highX   lowX              highY   lowY                         diagonal 2     lowY   y winnerPos-1      highY   lowY      lowX   x-winnerPos 1      highX   lowX      while highX  lt   x winnerPos-1  amp  amp  highY  lt   y winnerPos-1            if isValidPos highX  highY   amp  amp  isFilledPos highX  highY  player                 highX                highY--              if highX - lowX    winnerPos                    return true                          else               lowX   highX   1              lowY   highY   1              highX   lowX              highY   lowY                      if highX - lowX    winnerPos            return true            return false     private boolean isValidPos int x  int y        return x  gt   0  amp  amp  x  lt  row  amp  amp  y  gt   0  amp  amp  y lt  col    public boolean isFilledPos int x  int y  int p  throws IndexOutOfBoundsException       return arena x  y     p

User · Answer

Heres my solution that I wrote for a project I m working on in javascript   If you don t mind the memory cost of a few arrays it s probably the fastest and simplest solution you ll find   It assumes you know the position of the last move         Determines if the last move resulted in a win for either player    board  is an array representing the board    lastMove  is the boardIndex of the last  most recent  move     these are the boardIndexes          0   1   2     --- --- ---      3   4   5     --- --- ---      6   7   8        returns true if there was a win     var winLines           1  2    4  8    3  6          0  2    4  7          0  1    4  6    5  8          4  5    0  6          3  5    0  8    2  6    1  7          3  4    2  8          7  8    2  4    0  3          6  8    1  4          6  7    0  4    2  5      function isWinningMove board  lastMove        var player   board lastMove       for  var i   0  i  lt  winLines lastMove  length  i              var line   winLines lastMove  i           if player     board line 0    amp  amp  player     board line 1                  return true                      return false

User · Answer

I just wrote this for my C programming class   I am posting it because none of the other examples here will work with any size rectangular grid  and any number N-in-a-row consecutive marks to win   You ll find my algorithm  such as it is  in the checkWinner   function  It doesn t use magic numbers or anything fancy to check for a winner  it simply uses four for loops - The code is well commented so I ll let it speak for itself I guess      This program will work with any whole number sized rectangular gameBoard     It checks for N marks in straight lines  rows  columns  and diagonals      It is prettiest when ROWS and COLS are single digit numbers     Try altering the constants for ROWS  COLS  and N for great fun          PPDs come first       include  lt stdio h gt       define ROWS 9                 The number of rows our gameBoard array will have      define COLS 9                 The number of columns of the same - Single digit numbers will be prettier       define N 3                    This is the number of contiguous marks a player must have to win      define INITCHAR               This changes the character displayed  a     here probably looks the best       define PLAYER1CHAR  X         Some marks are more aesthetically pleasing than others      define PLAYER2CHAR  O         Change these lines if you care to experiment with them      Function prototypes are next      int playGame     char gameBoard ROWS  COLS                     This function allows the game to be replayed easily  as desired     void initBoard   char gameBoard ROWS  COLS                     Fills the ROWSxCOLS character array with the INITCHAR character     void printBoard  char gameBoard ROWS  COLS                     Prints out the current board  now with pretty formatting and  s      void makeMove    char gameBoard ROWS  COLS   int player        Prompts for  and validates   a move and stores it into the array     int checkWinner  char gameBoard ROWS  COLS   int player        Checks the current state of the board to see if anyone has won     The starting line int main  void           Inits     char gameBoard ROWS  COLS          Our gameBoard is declared as a character array  ROWS x COLS in size     int winner   0      char replay         Code     do                                 This loop plays through the game until the user elects not to               winner   playGame gameBoard           printf   nWould you like to play again  Y for yes  anything else exits               scanf   c   amp replay             I have to use both a scanf   and a getchar   in         replay   getchar               order to clear the input buffer of a newline char                                         http   cboard cprogramming com c-programming 121190-problem-do-while-loop-char html         while   replay     y     replay     Y             Housekeeping     printf   n        return winner      int playGame char gameBoard ROWS  COLS         int turn   0  player   0  winner   0  i   0       initBoard gameBoard        do               turn                                       Every time this loop executes  a unique turn is about to be made         player    turn 1  2 1                      This mod function alternates the player variable between 1  amp  2 each turn         makeMove gameBoard player           printBoard gameBoard           winner   checkWinner gameBoard player            if  winner    0                        printBoard gameBoard                for  i 0 i lt 19-2 ROWS i                 Formatting - works with the default shell height on my machine                 printf   n                         Hopefully I can replace these with something that clears the screen for me              printf   n nCongratulations Player  i  you ve won with  i in a row  n n  winner N               return winner                   while   turn  lt  ROWS COLS                                 Once ROWS COLS turns have elapsed      printf   n nGame Over  n nThere was no Winner  -  n        The board is full and the game is over     return winner      void initBoard  char gameBoard ROWS  COLS         int row   0  col   0       for  row 0 row lt ROWS row                  for  col 0 col lt COLS col                          gameBoard row  col    INITCHAR         Fill the gameBoard with INITCHAR characters                      printBoard gameBoard                           Having this here prints out the board before     return                                 the playGame function asks for the first move     void printBoard  char gameBoard ROWS  COLS         There is a ton of formatting in here                                                    That I don t feel like commenting  P     int row   0  col   0  i 0                      It took a while to fine tune                                                    But now the output is something like      printf   n                                                                                            1   2   3     for  row 0 row lt ROWS row                        1                                                               -----------         if  row    0                               2                                                               -----------             printf                                 3                       for  i 0 i lt COLS i                                  printf    i    i 1                              printf   n n                       for  col 0 col lt COLS col                          if  col  0                  printf   i   row 1                printf    c   gameBoard row  col                 if  col lt COLS-1                  printf                          printf   n             if  row  lt  ROWS-1                        for i 0 i lt COLS-1 i                                  if i  0                      printf    ----                    else                     printf  ----                               printf  --- n                         return      void makeMove  char gameBoard ROWS  COLS  int player        int row   0  col   0  i 0      char currentChar       if  player    1                        This gets the correct player s mark         currentChar   PLAYER1CHAR      else         currentChar   PLAYER2CHAR       for  i 0 i lt 21-2 ROWS i                 Newline formatting again  -          printf   n         printf   nPlayer  i  please enter the column of your move    player       scanf   i   amp col       printf  Please enter the row of your move          scanf   i   amp row        row--                                  These lines translate the user s rows and columns numbering     col--                                   starting with 1  to the computer s  starting with 0       while gameBoard row  col     INITCHAR    row  gt  ROWS-1    col  gt  COLS-1      We are not using a do    while because                                                                                I wanted the prompt to change         printBoard gameBoard           for  i 0 i lt 20-2 ROWS i                printf   n            printf   nPlayer  i  please enter a valid move  Column first  then row  n  player           scanf   i  i   amp col  amp row            row--                              See above             col--             gameBoard row  col    currentChar      Finally  we store the correct mark into the given location     return                                 And pop back out of this function     int checkWinner char gameBoard ROWS  COLS   int player         I ve commented the last  and the hardest  for me anyway                                                                 check  which checks for backwards diagonal runs below  gt  gt  gt      int row   0  col   0  i   0      char currentChar       if  player    1          currentChar   PLAYER1CHAR      else         currentChar   PLAYER2CHAR       for   row   0  row  lt  ROWS  row                             This first for loop checks every row               for   col   0  col  lt   COLS- N-1    col                 And all columns until N away from the end                       while  gameBoard row  col     currentChar          For consecutive rows of the current player s mark                               col                    i                    if  i    N                                        return player                                              i   0                       for   col   0  col  lt  COLS  col                             This one checks for columns of consecutive marks               for   row   0  row  lt   ROWS- N-1    row                          while  gameBoard row  col     currentChar                                row                    i                    if  i    N                                        return player                                              i   0                       for   col   0  col  lt   COLS -  N-1    col                   This one checks for  forwards  diagonal runs               for   row   0  row  lt   ROWS- N-1    row                          while  gameBoard row  col     currentChar                                row                    col                    i                    if  i    N                                        return player                                              i   0                                                                             Finally  the backwards diagonals      for   col   COLS-1  col  gt  0  N-2   col--               Start from the last column and go until N columns from the first                                                            The math seems strange here but the numbers work out when you trace them         for   row   0  row  lt   ROWS- N-1    row             Start from the first row and go until N rows from the last                       while  gameBoard row  col     currentChar      If the current player s character is there                               row                                        Go down a row                 col--                                      And back a column                 i                                          The i variable tracks how many consecutive marks have been found                 if  i    N                                 Once i    N                                       return player                          Return the current player number to the                                                            winnner variable in the playGame function                                                            If it breaks out of the while loop  there weren t N consecutive marks             i   0                                          So make i   0 again                                                            And go back into the for loop  incrementing the row to check from            return 0                                               If we got to here  no winner has been detected                                                             so we pop back up into the playGame function     The end      Well  almost      Eventually I hope to get this thing going    with a dynamically sized array  I ll make    the CONSTANTS into variables in an initGame    function and allow the user to define them

User · Answer

How about a following approach for 9 slots  Declare 9 integer variables for a 3x3 matrix  a1 a2    a9  where a1 a2 a3 represent row-1 and a1 a4 a7 would form column-1  you get the idea   Use  1  to indicate Player-1 and  2  to indicate Player-2    There are 8 possible win combinations       Win-1  a1 a2 a3  answer could be 3 or 6 based on which player won      Win-2  a4 a5 a6     Win-3  a7 a8 a9     Win-4  a1 a4 a7              Win-7  a1 a5 a9     Win-8  a3 a5 a7  Now we know that if player one crosses a1 then we need to reevaluate sum of 3 variables  Win-1  Win-4 and Win-7  Whichever  Win-   variables reaches 3 or 6 first wins the game  If Win-1 variable reaches 6 first then Player-2 wins   I do understand that this solution is not scalable easily

User · Answer

If the board is n  times  n then there are n rows  n columns  and 2 diagonals  Check each of those for all-X s or all-O s to find a winner   If it only takes x  lt  n consecutive squares to win  then it s a little more complicated  The most obvious solution is to check each x  times  x square for a winner  Here s some code that demonstrates that    I didn t actually test this  cough   but it did compile on the first try  yay me    public class TicTacToe       public enum Square   X  O  NONE                   Returns the winning player  or NONE if the game has        finished without a winner  or null if the game is unfinished              public Square findWinner Square     board  int lengthToWin               Check each lengthToWin x lengthToWin board for a winner              for  int top   0  top  lt   board length - lengthToWin    top                int bottom   top   lengthToWin - 1               for  int left   0  left  lt   board length - lengthToWin    left                    int right   left   lengthToWin - 1                      Check each row                  nextRow  for  int row   top  row  lt   bottom    row                        if  board row  left     Square NONE                            continue                                             for  int col   left  col  lt   right    col                            if  board row  col     board row  left                                 continue nextRow                                                                       return board row  left                                         Check each column                  nextCol  for  int col   left  col  lt   right    col                        if  board top  col     Square NONE                            continue                                             for  int row   top  row  lt   bottom    row                            if  board row  col     board top  col                                 continue nextCol                                                                       return board top  col                                         Check top-left to bottom-right diagonal                  diag1  if  board top  left     Square NONE                        for  int i   1  i  lt  lengthToWin    i                            if  board top i  left i     board top  left                                 break diag1                                                                       return board top  left                                         Check top-right to bottom-left diagonal                  diag2  if  board top  right     Square NONE                        for  int i   1  i  lt  lengthToWin    i                            if  board top i  right-i     board top  right                                 break diag2                                                                       return board top  right                                                         Check for a completely full board          boolean isFull   true           full  for  int row   0  row  lt  board length    row                for  int col   0  col  lt  board length    col                    if  board row  col     Square NONE                        isFull   false                      break full                                                        The board is full          if  isFull                return Square NONE                       The board is not full and we didn t find a solution          else               return null

User · Answer

I am late the party  but I wanted to point out one benefit that I found to using a magic square  namely that it can be used to get a reference to the square that would cause the win or loss on the next turn  rather than just being used to calculate when a game is over   Take this magic square   4 9 2 3 5 7 8 1 6   First  set up an scores array that is incremented every time a move is made  See this answer for details  Now if we illegally play X twice in a row at  0 0  and  0 1   then the scores array looks like this    7  0  0  4  3  0  4  0     And the board looks like this   X     X             Then  all we have to do in order to get a reference to which square to win block on is   get winning move   function       for  var i   0  i  lt  scores length  i             keep track of the number of times pieces were added to the row        subtract when the opposite team adds a piece     if  scores i  inc     2          return 15 - state i  val     8               In reality  the implementation requires a few additional tricks  like handling numbered keys  in JavaScript   but I found it pretty straightforward and enjoyed the recreational math

User · Answer

Constant time solution  runs in O 8    Store the state of the board as a binary number  The smallest bit  2 0  is the top left row of the board  Then it goes rightwards  then downwards   I E     -----------------    2 0   2 1   2 2    -----------------    2 3   2 4   2 5    -----------------    2 6   2 7   2 8    -----------------    Each player has their own binary number to represent the state  because tic-tac-toe  has 3 states  X  O  amp  blank  so a single binary number won t work to represent the state of the board for multiple players   For example  a board like     -----------    X   O   X    -----------    O   X        -----------        O        -----------      0 1 2 3 4 5 6 7 8 X  1 0 1 0 1 0 0 0 0 O  0 1 0 1 0 0 0 1 0   Notice that the bits for player X are disjoint from the bits for player O  this is obvious because X can t put a piece where O has a piece and vice versa   To check whether a player has won  we need to compare all the positions covered by that player to a position we know is a win-position  In this case  the easiest way to do that would be by AND-gating the player-position and the win-position and seeing if the two are equal   boolean isWinner short X        for  int i   0  i  lt  8  i            if   X  amp  winCombinations i      winCombinations i               return true      return false      eg    X  111001010 W  111000000    win position  all same across first row  ------------    111000000   Note  X  amp  W   W  so X is in a win state   This is a constant time solution  it depends only on the number of win-positions  because applying AND-gate is a constant time operation and the number of win-positions is finite   It also simplifies the task of enumerating all valid board states  their just all the numbers representable by 9 bits  But of course you need an extra condition to guarantee a number is a valid board state  eg  0b111111111 is a valid 9-bit number  but it isn t a valid board state because X has just taken all the turns    The number of possible win positions can be generated on the fly  but here they are anyways   short   winCombinations   new short          each row   0b000000111    0b000111000    0b111000000       each column   0b100100100    0b010010010    0b001001001       each diagonal   0b100010001    0b001010100      To enumerate all board positions  you can run the following loop  Although I ll leave determining whether a number is a valid board state upto someone else   NOTE   2  9 - 1     2  8     2  7     2  6         2  1     2  0   for  short X   0  X  lt   Math pow 2 9  - 1   X       System out println isWinner X

[java] Algorithm for Determining Tic Tac Toe Game Over

Examples related to java

Examples related to algorithm

Examples related to tic-tac-toe