Алгоритм определения окончания игры в крестики-нолики

Я написал игру в крестики-нолики на Java, и мой текущий метод определения конца игры учитывает следующие возможные сценарии завершения игры:

1. Доска заполнена, победитель еще не объявлен: игра - ничья.
2. Кросс победил.
3. Круг победил.

К сожалению, для этого он считывает заранее определенный набор этих сценариев из таблицы. Это не обязательно плохо, учитывая, что на доске всего 9 мест, и поэтому таблица несколько мала, но есть ли лучший алгоритмический способ определить, окончена ли игра? Определение того, выиграл ли кто-то или нет, - это суть проблемы, поскольку проверка заполнения 9 пробелов тривиальна.

Табличный метод может быть решением, но если нет, то что? Кроме того, что, если бы плата не была размером n=9? Что, если бы это была доска гораздо большего размера, скажем n=16, n=25и т. Д., В результате чего количество последовательно размещаемых элементов было бы равным x=4, x=5и т. Д.? Общий алгоритм для всех n = { 9, 16, 25, 36 ... }?

Вы знаете, что выигрышный ход может произойти только после того, как X или O сделали свой последний ход, поэтому вы можете искать только строку / столбец с необязательной диагональю, которая содержится в этом ходу, чтобы ограничить пространство поиска при попытке определить выигрышную доску. Кроме того, поскольку в игре в крестики-нолики с ничьей есть фиксированное количество ходов, после того, как был сделан последний ход, если он не был выигрышным, по умолчанию это игра с ничьей.

изменить: этот код предназначен для доски размером n на n с n в ряду, чтобы выиграть (3x3 доски 3 в ряд и т. д.)

edit: добавлен код для проверки анти-диагноза, я не мог понять, как без цикла определить, была ли точка на антидиаге, поэтому этот шаг отсутствует

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

вы можете использовать магический квадрат http://mathworld.wolfram.com/MagicSquare.html, если сумма в любой строке, столбце или диагонали равна 15, значит, игрок выиграл.

Как насчет этого псевдокода:

После того, как игрок кладет фишку на позицию (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

Я бы использовал массив char [n, n] с O, X и пробелом для пустого.

1. просто.
2. Одна петля.
3. Пять простых переменных: 4 целых и одна логическая.
4. Весы на любой размер n.
5. Проверяет только текущий кусок.
6. Никакой магии. :)

Это похоже на ответ Усамы АЛАССИРИ , но он меняет постоянное пространство и линейное время на линейное пространство и постоянное время. То есть после инициализации не происходит зацикливания.

Инициализируйте пару (0,0)для каждой строки, каждого столбца и двух диагоналей (диагональной и антидиагональной). Эти пары представляют собой накопленные (sum,sum)кусочки в соответствующей строке, столбце или диагонали, где

Фишка игрока А имеет ценность (1,0).
Фишка игрока B имеет ценность (0,1)

Когда игрок кладет фишку, обновите соответствующую пару строк, пару столбцов и диагональные пары (если они находятся на диагоналях). Если какая-либо недавно обновленная пара строк, столбцов или диагоналей равна одному (n,0)или, (0,n)то выигрывает либо A, либо B соответственно.

Асимптотический анализ:

O (1) раз (за ход)
O (n) пробел (в целом)

Для использования памяти вы используете 4*(n+1)целые числа.

two_elements * n_rows + two_elements * n_columns +
two_elements * two_diagonals = 4 * n + 4 целых числа = 4 (n + 1) целых числа

Упражнение: видите ли вы, как проверить ничью за O (1) раз за ход? В таком случае вы можете досрочно завершить игру при ничьей.

Вот мое решение, которое я написал для проекта, над которым я работаю, на javascript. Если вы не возражаете против стоимости памяти нескольких массивов, это, вероятно, самое быстрое и простое решение, которое вы найдете. Предполагается, что вы знаете позицию последнего хода.

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

Я только что написал это для своего класса программирования C.

Я публикую его, потому что ни один из других примеров здесь не будет работать с прямоугольной сеткой любого размера и любым количеством N -в-ряда последовательных оценок для победы.

Вы найдете мой алгоритм таким, какой он есть, в checkWinner()функции. Он не использует магические числа или что-то необычное для проверки победителя, он просто использует четыре цикла for - код хорошо прокомментирован, поэтому я думаю, он говорит сам за себя.

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

Если размер доски n × n, то есть n строк, n столбцов и 2 диагонали. Проверьте каждый из них на все-X или все-O, чтобы найти победителя.

Если потребуется для победы x < n последовательных квадратов, то все немного сложнее. Наиболее очевидное решение - проверить каждый квадрат x × x на победителя. Вот код, демонстрирующий это.

(Я фактически не проверить это * кашель *, но он сделал компиляции с первой попытки, яй меня!)

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

Я не так хорошо знаю Java, но я знаю C, поэтому я попробовал идею магического квадрата adk (вместе с ограничением поиска Hardwareguy ).

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

Он хорошо компилируется и тестируется.

% gcc -o крестики-нолики крестики-нолики.c
% ./крестики-нолики
     | |
  --- + --- + ---
     | |
  --- + --- + ---
     | |
  Введите ходы как "" (без кавычек, с нулевым индексом)
  Ход X: 1 2
     | |
  --- + --- + ---
     | | Икс
  --- + --- + ---
     | |
  Ход O: 1 2
  неправильный ход (уже сделан), попробуйте еще раз
  Ход O: 3 3
  неправильный ход (вне доски), попробуйте еще раз
  Ход O: 2 2
     | |
  --- + --- + ---
     | | Икс
  --- + --- + ---
     | | О
  Ход X: 1 0
     | |
  --- + --- + ---
   X | | Икс
  --- + --- + ---
     | | О
  Ход O: 1 1
     | |
  --- + --- + ---
   X | O | Икс
  --- + --- + ---
     | | О
  Ход X: 0 0
   X | |
  --- + --- + ---
   X | O | Икс
  --- + --- + ---
     | | О
  Ход O: 2 0
   X | |
  --- + --- + ---
   X | O | Икс
  --- + --- + ---
   O | | О
  Ход X: 2 1
   X | |
  --- + --- + ---
   X | O | Икс
  --- + --- + ---
   O | X | О
  Ход O: 0 2
   X | | О
  --- + --- + ---
   X | O | Икс
  --- + --- + ---
   O | X | О
  крестики-нолики! О побед!
% ./крестики-нолики
     | |
  --- + --- + ---
     | |
  --- + --- + ---
     | |
  Введите ходы как "" (без кавычек, с нулевым индексом)
  Ход X: 0 0
   X | |
  --- + --- + ---
     | |
  --- + --- + ---
     | |
  Ход O: 0 1
   X | O |
  --- + --- + ---
     | |
  --- + --- + ---
     | |
  Ход X: 0 2
   X | O | Икс
  --- + --- + ---
     | |
  --- + --- + ---
     | |
  Ход O: 1 0
   X | O | Икс
  --- + --- + ---
   O | |
  --- + --- + ---
     | |
  Ход X: 1 1
   X | O | Икс
  --- + --- + ---
   O | X |
  --- + --- + ---
     | |
  Ход O: 2 0
   X | O | Икс
  --- + --- + ---
   O | X |
  --- + --- + ---
   O | |
  Ход X: 2 1
   X | O | Икс
  --- + --- + ---
   O | X |
  --- + --- + ---
   O | X |
  Ход O: 2 2
   X | O | Икс
  --- + --- + ---
   O | X |
  --- + --- + ---
   O | X | О
  Ход X: 1 2
   X | O | Икс
  --- + --- + ---
   O | X | Икс
  --- + --- + ---
   O | X | О
  тупик ... никто не выигрывает :(
%

Было весело, спасибо!

На самом деле, если задуматься, вам не нужен магический квадрат, просто счет для каждой строки / столбца / диагонали. Это немного проще, чем обобщение магического квадрата на матрицы n× n, поскольку вам просто нужно посчитать до n.

Мне задали тот же вопрос в одном из интервью. Мои мысли: Инициализировать матрицу с 0. Сохраните 3 массива 1) sum_row (размер n) 2) sum_column (размер n) 3) диагональ (размер 2)

Для каждого хода на (X) уменьшайте значение прямоугольника на 1 и для каждого хода на (0) увеличивайте его на 1. В любой момент, если строка / столбец / диагональ, которые были изменены в текущем ходу, имеют сумму либо -3, либо + 3 означает, что кто-то выиграл игру. Для розыгрыша мы можем использовать вышеуказанный подход, чтобы сохранить переменную moveCount.

Вы думаете, я что-то упускаю?

Изменить: то же самое можно использовать для матрицы nxn. Сумма должна быть даже +3 или -3.

Непетлевой способ определить, была ли точка на антидиаге:

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

Я опаздываю на вечеринку, но я хотел указать на одно преимущество, которое я обнаружил в использовании магического квадрата , а именно на то, что его можно использовать для получения ссылки на квадрат, который вызовет выигрыш или проигрыш на следующем ходу, а не просто используется для расчета, когда игра окончена.

Возьмите этот магический квадрат:

4 9 2
3 5 7
8 1 6

Во-первых, настройте scoresмассив, который увеличивается при каждом перемещении. См. Этот ответ для подробностей. Теперь, если мы незаконно сыграем X дважды подряд в точках [0,0] и [0,1], тогда scoresмассив будет выглядеть так:

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

А плата выглядит так:

X . .
X . .
. . .

Затем все, что нам нужно сделать, чтобы получить ссылку на квадрат, на котором нужно выиграть / заблокировать:

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

На самом деле для реализации требуется несколько дополнительных приемов, таких как обработка нумерованных ключей (в JavaScript), но мне это показалось довольно простым, и мне понравилась развлекательная математика.

Я сделал некоторую оптимизацию в проверках строк, столбцов, диагоналей. В основном это решается в первом вложенном цикле, если нам нужно проверить конкретный столбец или диагональ. Таким образом, мы избегаем проверки столбцов или диагоналей, экономя время. Это имеет большое значение, когда размер платы больше, а значительное количество ячеек не заполнено.

Вот код Java для этого.

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

Мне нравится этот алгоритм, поскольку он использует представление платы 1x9 против 3x3.

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

Другой вариант: сгенерируйте свою таблицу с кодом. С точки зрения симметрии, есть только три способа выиграть: ряд по краям, средний ряд или диагональ. Возьмите эти три и раскрутите их всеми возможными способами:

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

Эти симметрии могут иметь больше применений в вашем игровом коде: если вы дойдете до доски, которую уже видели повернутую версию, вы можете просто взять кэшированное значение или кэшированный лучший ход из этого (и открутить его обратно). Обычно это намного быстрее, чем оценка поддерева игры.

(Листание влево и вправо также может помочь; здесь в этом не было необходимости, потому что набор поворотов выигрышных паттернов зеркально-симметричен.)

Вот решение, которое я придумал, в нем символы хранятся как символы и используется значение int типа char, чтобы выяснить, выиграл ли 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

Как насчет следующего подхода для 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

Теперь мы знаем, что если игрок 1 пересекает a1, нам нужно повторно вычислить сумму трех переменных: Win-1, Win-4 и Win-7. Какой бы ни была победа? переменная достигает 3 или 6 первых выигрышей в игре. Если переменная Win-1 первой достигает 6, то выигрывает Игрок-2.

Я понимаю, что это решение нелегко масштабировать.

Это действительно простой способ проверить.

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

}

Если у вас, например, граничное поле 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; 
        }

Думаю, так понятнее, но, наверное, не самый оптимальный.

Вот мое решение с использованием двумерного массива:

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