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:

1. The board is full, and no winner has yet been declared: Game is a draw.
2. Cross has won.
3. 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 ... }?

Answer 1

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.

This code is for an n by n board with n in a row to win (3x3 board requires 3 in a row, etc)

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
        }
    }
}

Answer 2

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.

Answer 3

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.

1. simple.
2. One loop.
3. Five simple variables: 4 integers and one boolean.
4. Scales to any size of n.
5. Only checks current piece.
6. No magic. :)

Answer 4

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

Answer 5

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 < winLines[lastMove].length; i++) {
        var line = winLines[lastMove][i];
        if(player === board[line[0]] && player === board[line[1]]) {
            return true;
        }
    }
    return false;
}

Answer 6

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 :

1. a1 = 100 000 000 100 000 000 100 000 ... ORed with
2. a2 = 010 000 000 000 100 000 000 000 ... ORed with
3. 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 "winline" 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 << 1) AND (XB >> 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 :

{"wins the top row", "takes the middle row!", ... "steals the diagonal!" }

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 "X's board" with "O's board" = 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... "Human" is my second language and I'm not quite fluent yet ;)

Anyway, I hope this helps someone.

Answer 7

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 & 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 < 8; i++)
        if ((X & winCombinations[i]) == winCombinations[i])
            return true;
    return false;
}

eg.

X: 111001010
W: 111000000 // win position, all same across first row.
------------
&: 111000000

Note: X & 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 < (Math.pow(2,9) - 1); X++)
   System.out.println(isWinner(X));

Answer 8

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 <stdio.h>
    #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",&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 & 2 each turn
        makeMove(gameBoard,player);
        printBoard(gameBoard);
        winner = checkWinner(gameBoard,player);

        if (winner != 0)
        {
            printBoard(gameBoard);

            for (i=0;i<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 < 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<ROWS;row++)
    {
        for (col=0;col<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<ROWS;row++)                  // 1    |   |
    {                                           //   -----------
        if (row == 0)                           // 2    |   |
        {                                       //   -----------
            printf("  ");                       // 3    |   |

            for (i=0;i<COLS;i++)
            {
                printf(" %i  ",i+1);
            }

            printf("\n\n");
        }

        for (col=0;col<COLS;col++)
        {
            if (col==0)
                printf("%i ",row+1);

            printf(" %c ",gameBoard[row][col]);

            if (col<COLS-1)
                printf("|");
        }

        printf("\n");

        if (row < ROWS-1)
        {
            for(i=0;i<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<21-2*ROWS;i++)           // Newline formatting again :-(
        printf("\n");

    printf("\nPlayer %i, please enter the column of your move: ",player);
    scanf("%i",&col);
    printf("Please enter the row of your move: ");
    scanf("%i",&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 > ROWS-1 || col > COLS-1)  // We are not using a do... while because
    {                                                                       // I wanted the prompt to change
        printBoard(gameBoard);
        for (i=0;i<20-2*ROWS;i++)
            printf("\n");
        printf("\nPlayer %i, please enter a valid move! Column first, then row.\n",player);
        scanf("%i %i",&col,&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 >>>
    int row = 0, col = 0, i = 0;
    char currentChar;

    if (player == 1)
        currentChar = PLAYER1CHAR;
    else
        currentChar = PLAYER2CHAR;

    for ( row = 0; row < ROWS; row++)                       // This first for loop checks every row
    {
        for ( col = 0; col < (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 < COLS; col++)                       // This one checks for columns of consecutive marks
    {
        for ( row = 0; row < (ROWS-(N-1)); row++)
        {
            while (gameBoard[row][col] == currentChar)
            {
                row++;
                i++;
                if (i == N)
                {
                    return player;
                }
            }
            i = 0;
        }
    }

    for ( col = 0; col < (COLS - (N-1)); col++)             // This one checks for "forwards" diagonal runs
    {
        for ( row = 0; row < (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 > 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 < (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.

Answer 9

If the board is n × 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 < n consecutive squares to win, then it's a little more complicated. The most obvious solution is to check each x × 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 <= board.length - lengthToWin; ++top) {
            int bottom = top + lengthToWin - 1;

            for (int left = 0; left <= board.length - lengthToWin; ++left) {
                int right = left + lengthToWin - 1;

                // Check each row.
                nextRow: for (int row = top; row <= bottom; ++row) {
                    if (board[row][left] == Square.NONE) {
                        continue;
                    }

                    for (int col = left; col <= right; ++col) {
                        if (board[row][col] != board[row][left]) {
                            continue nextRow;
                        }
                    }

                    return board[row][left];
                }

                // Check each column.
                nextCol: for (int col = left; col <= right; ++col) {
                    if (board[top][col] == Square.NONE) {
                        continue;
                    }

                    for (int row = top; row <= 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 < 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 < 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 < board.length; ++row) {
            for (int col = 0; col < 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;
        }
    }
}

Answer 10

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 <stdio.h>

// 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, { &row[0], &col[0], &nw_diag } },
    { Empty, 1, 2, { &row[0], &col[1] } },
    { Empty, 6, 3, { &row[0], &col[2], &ne_diag } },
  },
  { 
    { Empty, 3, 2, { &row[1], &col[0] } },
    { Empty, 5, 4, { &row[1], &col[1], &nw_diag, &ne_diag } },
    { Empty, 7, 2, { &row[1], &col[2] } },
  },
  { 
    { Empty, 4, 3, { &row[2], &col[0], &ne_diag } },
    { Empty, 9, 2, { &row[2], &col[1] } },
    { Empty, 2, 3, { &row[2], &col[2], &nw_diag } },
  }
};

// print the board
void show_board(void)
{
  size_t r, c;
  for (r = 0; r < NUM_ROWS; r++) 
  {
    if (r > 0) { printf("---+---+---\n"); }
    for (c = 0; c < NUM_COLS; c++) 
    {
      if (c > 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 \"<row> <col>\" (no quotes, zero indexed)\n");
  for( m = 0; m < 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", &r, &c);
      if (r >= NUM_ROWS || c >= 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 = &(board[r][c]);
      size_t s;

      // update the board state
      cell->mark = mark;
      show_board();

      // check for tic-tac-toe
      for (s = 0; s < cell->num_sums; s++)
      {
        cell->sums[s]->of[mark] += cell->value;
        if (cell->sums[s]->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 × n matrices, since you just need to count to n.

Answer 11

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.

Answer 12

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 < START.length; i++) {
        int sum = 0;
        for (int j = 0; j < SIZE; j++) {
            sum += board[START[i] + j * INCR[i]];
        }
        if (Math.abs(sum) == SIZE) {
            return sum / SIZE;
        }
    }
    return 0;
}

Answer 13

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

Answer 14

a non-loop way to determine if the point was on the anti diag:

`if (x + y == n - 1)`

Answer 15

Here's an example implementation in React: CodeSandbox Demo.

The algorithm is quite straightforward:

For every move:
   checkDiagonals()
   checkVerticals()
   checkHorizontals()

Assigning 0 for an "O" input and 1 for an "X" input. The result of the check functions can be either 0, or 1, or 2 (draw).

Here's the implementation:

    const checkDiagonals = () => {
        if ((state[0][0] === val && state[1][1] === val && state[2][2] === val) ||
            (state[0][2] === val && state[1][1] === val && state[2][0] === val)) {
            return val;
        }
        return -1;
    }

    const checkVerticals = () => {
        for (let i = 0; i <= 2; i++) {
            if (state[0][i] === val && state[1][i] === val && state[2][i] === val) {
                return val;
            }
        }
        return -1;
    }

    const checkHorizontals = () => {
        for (let i = 0; i <= 2; i++) {
            if (state[i][0] === val && state[i][1] === val && state[i][2] === val) {
                return val;
            }
        }
        return -1;
    }

Then all is left, is to have a function that will trigger on every single user input:

const updateWinningPlayer = () => {

    const diagonals = checkDiagonals();
    const verticals = checkVerticals();
    const horizontals = checkHorizontals();

    if (diagonals !== -1) {
        setWinner(diagonals)
        return;
    }

    if (verticals !== -1) {
        setWinner(verticals);
        return;
    }

    if (horizontals !== -1) {
        setWinner(horizontals);
        return;
    }

    if (isDraw()) {
        setWinner(2);
    }
}

And there you have it!

GitHub repo link: https://github.com/mkotsollaris/tic-tac-toe

Answer 16

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 < boardSz; i++) {
        x_count = o_count = 0;
        for (int j = 0; j < 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 < boardSz; i++) {
        x_count = o_count = 0;
        if(colCheckNotRequired[i] == false)
        {
            for (int j = 0; j < 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 < 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 >= 0 && j < 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 < boardSz; i++) {
            for (int j = 0; j < boardSz; j++) {
                if (values[i][j] == 0) {
                    allFilled = false;
                    break;
                }
            }

            if (allFilled == false) {
                break;
            }
        }
    }

    if (allFilled)
        return DRAW;

    return INPROGRESS;
}

Answer 17

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 <= 6; i += 3) {

        if (board[i] == player.piece &&
                board[i + 1] == player.piece &&
                board[i + 2] == player.piece)
            endGame(player);
    }

    // check vertical win
    for (int i = 0; i <= 2; i++) {

        if (board[i] == player.piece &&
                board[i + 3] == player.piece &&
                board[i + 6] == player.piece)
            endGame(player);
    }

    // check diagonal win
    if ((board[0] == player.piece &&
            board[4] == player.piece &&
            board[8] == player.piece) ||
            board[2] == player.piece &&
            board[4] == player.piece &&
            board[6] == player.piece)
        endGame(player);
    }

}

Answer 18

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

Answer 19

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 < 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) && allSymbolsMatch(symbol, diagonalTotal, PRINCIPAL))
                return true;
            if (isMinorDiagonal(x, y) && 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

Answer 20

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.

Answer 21

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 < SIZE-1; i++) {
            for (int j = 0; j <SIZE-1 ; j++) {
                //vertical checking
            if (map[0][j] == symb && map[1][j] == symb && map[2][j] == symb && map[3][j] == symb && map[4][j] == symb) return true;      // j=0
            }
            //horisontal checking
            if(map[i][0] == symb && map[i][1] == symb && map[i][2] == symb && map[i][3] == symb && map[i][4] == symb) return true;  // i=0
        }
        //diagonal checking (5*5)
        if (map[0][0] == symb && map[1][1] == symb && map[2][2] == symb && map[3][3] == symb && map[4][4] == symb) return true;
        if (map[4][0] == symb && map[3][1] == symb && map[2][2] == symb && map[1][3] == symb && map[0][4] == symb) return true;

        return false; 
        }

I think, it's more clear, but probably is not the most optimal way.

Answer 22

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 < dimension; i++) {
        int[] height = board[i];
        for (int j = 0; j < 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 < dimension; i++) {
        int[] height = board[i];
        int total = 0;
        for (int j = 0; j < dimension; j++) {
            total += height[j];
        }
        horizontalTotal[i] = total;
    }
    for (int a = 0; a < 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 < dimension; j++) {
        int total = 0;
        for (int i = 0; i < dimension; i++) {
            total += board[i][j];
        }
        verticalTotal[j] = total;
    }
    for (int a = 0; a < 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 < dimension; i++) {
        for (int j = 0; j < 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;
}

Answer 23

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 <= x+winnerPos-1) {
        if(isValidPos(high, y) && 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 <= y+winnerPos-1) {
        if(isValidPos(x, high) && 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 <= x+winnerPos-1 && highY <= y+winnerPos-1) {
        if(isValidPos(highX, highY) && 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 <= x+winnerPos-1 && highY <= y+winnerPos-1) {
        if(isValidPos(highX, highY) && 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 >= 0 && x < row && y >= 0 && y< col;
}
public boolean isFilledPos(int x, int y, int p) throws IndexOutOfBoundsException {
    return arena[x][y] == p;
}

Answer 24

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)=>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] >= 0 && x+searchvector[0] < 3 && 
      y+searchvector[1] >= 0 && y+searchvector[1] < 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.

class Square extends React.Component {
  constructor(props) {
    super(props);
    this.state = {value:null};
  }
  render() {
    return (
      <button className="square" onClick={() => this.props.onClick()}>
        {this.props.value}
      </button>
    );
  }
}

class Board extends React.Component {
  renderSquare(x,y) {
    return <Square value={this.state.squares[y][x]} onClick={() => this.handleClick(x,y)} />;
  }
  handleClick(x,y) {
    const squares = JSON.parse(JSON.stringify(this.state.squares));
    if (!squares[y][x] && !this.state.winner) {
      squares[y][x] = this.setTurn();
      this.setState({squares: squares},()=>{
        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)=>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] >= 0 && x+searchvector[0] < 3 && 
          y+searchvector[1] >= 0 && y+searchvector[1] < 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 (
      <div>
        <div className="status">{status}</div>
        <div className="board-row">
          {this.renderSquare(0,0)}
          {this.renderSquare(0,1)}
          {this.renderSquare(0,2)}
        </div>
        <div className="board-row">
          {this.renderSquare(1,0)}
          {this.renderSquare(1,1)}
          {this.renderSquare(1,2)}
        </div>
        <div className="board-row">
          {this.renderSquare(2,0)}
          {this.renderSquare(2,1)}
          {this.renderSquare(2,2)}
        </div>
      </div>
    );
  }
}

class Game extends React.Component {
  render() {
    return (
      <div className="game">
        <div className="game-board">
          <Board />
        </div>
        <div className="game-info">
          <div>{/* status */}</div>
          <ol>{/* TODO */}</ol>
        </div>
      </div>
    );
  }
}

// ========================================

ReactDOM.render(
  <Game />,
  document.getElementById('root')
);

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;
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/react/16.6.3/umd/react.production.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/react-dom/16.6.3/umd/react-dom.production.min.js"></script>
<div id="errors" style="
  background: #c00;
  color: #fff;
  display: none;
  margin: -20px -20px 20px;
  padding: 20px;
  white-space: pre-wrap;
"></div>
<div id="root"></div>
<script>
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' && 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);
</script>

Answer 25

There was a tic-tac-toe question on another thread that I can't find now, but I found this, so here was my tic-tac-toe simulator I whipped up after reading the question:

from random import randint
from time import sleep

# Tic-tac-toe simulator
# The grid:
#  0 | 1 | 2
# -----------
#  3 | 4 | 5
# -----------
#  6 | 7 | 8
# -----------

# create winning lines
winlines = tuple(
    map(
        set,
        (
            (0, 1, 2),  # across
            (3, 4, 5),
            (6, 7, 8),
            (0, 3, 6),  # down
            (1, 4, 7),
            (2, 5, 8),
            (0, 4, 8),  # diagonals
            (2, 4, 6),
        ),
    )
)

for trials in range(10):
    # clear the table
    available = list(range(9))  # 9 positions 0-8
    xPlacement = set()
    oPlacement = set()

    winner = None

    while len(available):
        index = randint(0, len(available) - 1)
        move = available[index]
        if index < len(available) - 1:
            available[index] = available.pop()
        else:
            available.pop()
        print("X takes ", move)
        xPlacement.add(move)
        if any(((xPlacement & winline) == winline) for winline in winlines):
            winner = "X"
            break
        if len(available) == 0:
            break

        index = randint(0, len(available) - 1)
        move = available[index]
        if index < len(available) - 1:
            available[index] = available.pop()
        else:
            available.pop()
        print("O takes ", move)
        oPlacement.add(move)
        if any(((oPlacement & winline) == winline) for winline in winlines):
            winner = "O"
            break

    print(
        " {} | {} | {}\n-----------\n {} | {} | {}\n-----------\n {} | {} | {}".format(
            *[
                "X" if pos in xPlacement else "O" if pos in oPlacement else " "
                for pos in range(9)
            ]
        )
    )
    if winner:
        print(f"{winner} wins!")
    else:
        print("It's a tie!")
    sleep(1)

Answer 26

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