Tic Tac Toe Over Game Definition Algorithm

Question

I wrote the tic-tac-toe game in Java, and my current method for determining the end of the game takes into account the following possible scenarios for the game:

• The board is full and the winner has not yet been announced: the game is a draw.
• The cross won.
• The circle won.

Unfortunately, for this he reads through a predefined set of these scripts from the table. This is not necessarily bad, given that there are only 9 spaces on the board, and therefore the table is somewhat small, but is there a better algorithmic way to determine if the game has ended? Determining whether someone won or not is a problem issue, as checking for filling in 9 spaces is trivial.

A table method may be a solution, but if not, then what? Also, what if the board was not n=9 ? What if it was a much larger board, say n=16 , n=25 , etc., forcing the number of consecutively placed items to win like x=4 , x=5 , etc.? General algorithm to use for all n = { 9, 16, 25, 36 ... } ?

Answer 1

You know that a winning move can only happen after X or O has made the very last move, so you can only search for a row / column with an optional diagonal that is contained in this transition to limit the search space when trying to determine a winning board. In addition, since there is a fixed number of moves in a tic-tac-toe-game draw after the last move is made, if it was not the default winning move, the game is a draw.

edit: this code is for the nth board with n in the line to win (3x3 board board 3 in the line, etc.)

edit: code was added to check the anti-diagram, I could not understand if there was a method for determining whether a point was on the anti-range, so why this 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 } } } 

Answer 2

you can use the magic square http://mathworld.wolfram.com/MagicSquare.html if any row, column or diag adds up to 15, after which the player wins.

Answer 3

This is similar to Osama ALASSIRY's answer , but it trades constant space and linear time for linear space and constant time. That is, after initialization, there is no loop.

Initialize a pair (0,0) for each row, each column, and two diagonals (diagonal and anti-diagonal). These pairs are accumulated (sum,sum) figures 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 puts a piece, update the corresponding pair of rows, a pair of columns and diagonal pairs (if on the diagonals). If any new updated pair of rows, columns or diagonal is equal to either (n,0) or (0,n) , then either A or B won respectively.

Asymptotic analysis:

 O (1) time (per move)
 O (n) space (overall)

To use memory, 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 a draw in O (1) time per turn? If so, you can end the game at the start of the rally.

Answer 4

How about this pseudo code:

After the player has put the piece in 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 would use an array of char [n, n], with O, X and a space for empty.

• simply.
• One cycle.
• Five simple variables: 4 integers and one logical.
• Scales to any size n.
• Checks only the current position.
• No magic. :)

Answer 5

Here is my solution that I wrote for a project that I am working on in javascript. If you don't mind the memory cost of multiple arrays, this is probably the fastest and easiest solution you will find. It is assumed that 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

I just wrote this for my C programming class.

I am posting it because none of the other examples here will work with a rectangular grid of any size, and any number in a row N -in-row in a row to win.

You will find my algorithm, for example, in the checkWinner() function. It does not use magic numbers or anything interesting to test the winner, it just uses four for cycles. The code is well commented, so I will let it speak on its own, I think.

 // 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 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 rows and columns numbering col--; // (starting with 1) to the computer (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 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 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 7

If the board is n × n, i.e. n rows, n columns and 2 diagonals. Check each one for all-X or all-O to find a winner.

If he takes only x <n consecutive squares to win, then this is a little trickier. The most obvious solution is to check each x & times; x square for the winner. Here is some code that demonstrates this.

(I really did not test this * cough *, but it compiled 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 8

I don't know Java very well, but I know C, so I tried the idea of ​​adk magic square (along with Hardwareguy 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 move do { printf("%c 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 move: 1 2
      |  |
   --- + --- + ---
      |  |  X
   --- + --- + ---
      |  |
   O move: 1 2
   illegal move (already taken), try again
   O move: 3 3
   illegal move (off the board), try again
   O move: 2 2
      |  |
   --- + --- + ---
      |  |  X
   --- + --- + ---
      |  |  O
   X move: 1 0
      |  |
   --- + --- + ---
    X |  |  X
   --- + --- + ---
      |  |  O
   O move: 1 1
      |  |
   --- + --- + ---
    X |  O |  X
   --- + --- + ---
      |  |  O
   X move: 0 0
    X |  |
   --- + --- + ---
    X |  O |  X
   --- + --- + ---
      |  |  O
   O move: 2 0
    X |  |
   --- + --- + ---
    X |  O |  X
   --- + --- + ---
    O |  |  O
   X move: 2 1
    X |  |
   --- + --- + ---
    X |  O |  X
   --- + --- + ---
    O |  X |  O
   O 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 move: 0 0
    X |  |
   --- + --- + ---
      |  |
   --- + --- + ---
      |  |
   O move: 0 1
    X |  O |
   --- + --- + ---
      |  |
   --- + --- + ---
      |  |
   X move: 0 2
    X |  O |  X
   --- + --- + ---
      |  |
   --- + --- + ---
      |  |
   O move: 1 0
    X |  O |  X
   --- + --- + ---
    O |  |
   --- + --- + ---
      |  |
   X move: 1 1
    X |  O |  X
   --- + --- + ---
    O |  X |
   --- + --- + ---
      |  |
   O move: 2 0
    X |  O |  X
   --- + --- + ---
    O |  X |
   --- + --- + ---
    O |  |
   X move: 2 1
    X |  O |  X
   --- + --- + ---
    O |  X |
   --- + --- + ---
    O |  X |
   O move: 2 2
    X |  O |  X
   --- + --- + ---
    O |  X |
   --- + --- + ---
    O |  X |  O
   X move: 1 2
    X |  O |  X
   --- + --- + ---
    O |  X |  X
   --- + --- + ---
    O |  X |  O
   stalemate ... nobody wins :(
 %

It was fun, thanks!

Actually, thinking about this, you do not need a magic square, just an account for each row / column / diagonal. This is a little easier than generalizing the magic square to n * times; n , since you just need to count n .

Answer 9

I was asked the same question in one of my interviews. My thoughts: Initialize the matrix with 0. Store 3 arrays 1) sum_row (size n) 2) sum_column (size n) 3) diagonal (size 2)

For each move along (X), decrease the field value by 1 and for each move along (0) increase it by 1. At any time, if the row / column / diagonal that has been changed in the current movement has the sum either -3 or +3 means that someone won the game. For a draw, we can use the above approach to save the moveCount variable.

What do you think I'm missing something?

Edit: The same can be used for the nxn matrix. The amount must be equal to +3 or -3.

Answer 10

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

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

Answer 11

I did some optimization in strings, col, diagonal checks. It was mainly decided in the first nested loop if we need to check a specific column or diagonal. This way we avoid checking columns or diagonals that save time. This is of great importance when the board size is larger and a significant number of cells are empty.

Here is the Java code for this.

  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 12

I'm late to the party, but I wanted to point out one advantage that I found using the magic square , namely that it can get a link to the square, which will lead to victory or loss on the next move, instead of just being used to calculate when the game is over.

Take this magic square:

 4 9 2 3 5 7 8 1 6 

First, set up the scores array, which grows every time you move. See this answer for more details. Now, if we illegally lose X twice in a row at [0,0] and [0,1], the scores array looks like this:

 [7, 0, 0, 4, 3, 0, 4, 0]; 

And the panel looks like this:

 X . . X . . . . . 

Then all we need to do to get a link to which square to win / block:

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

Actually, the implementation requires a few extra tricks, such as handling numbered keys (in JavaScript), but I found it pretty simple and enjoyed the recreational math.

Answer 13

I like this algorithm since it uses the 1x9 representation against the 3x3 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 14

Another option: generate a table with a code. Before symmetry, you can win only three ways: the extreme row, the middle row or the diagonal. Take these three and rotate them in every possible way:

 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 may have more use in your game code: if you get to the board where you already saw the rotated version, you can just take the cached value or cache the best transition from this (and disable it back). , .

( , , -.)

Answer 15

, , char int, , X O ( )

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

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

: https://github.com/nashjain/tictactoe/tree/master/java

Answer 16

9 ? 9 3x3 (a1, a2.... a9), a1, a2, a3 -1 a1, a4, a7 -1 ( ). "1", "-1" "2", "-2".

8 : Win-1: a1 + a2 + a3 ( 3 6 , ) 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

, a1, : Win-1, Win-4 Win-7. ?? 3 6 . Win-1 6, Player-2.

, .

Answer 17

O (8), 4 . Player = . .

 // O(8) boolean isWinner(short X) { for (int i = 0; i < 8; i++) if ((X & winCombinations[i]) == winCombinations[i]) return true; return false; } short[] winCombinations = new short[]{ 7, 7 << 3, 7 << 6, // horizontal 73, 73 << 1, 73 << 2, // vertical 273, // diagonal 84 // anti-diagonal }; for (short X = 0; X < 511; X++) System.out.println(isWinner(X)); 

Answer 18

.

  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 19

5 * 5 , :

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

, , , , .

Answer 20

:

 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 ij 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 xy. Retry"); } else { result = "" + x + "," + y; } return result; } private static boolean alreadyPlayed(int x, int y) { System.out.println("xy: " + 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 21

.

2x2 , 2x2.

, .