Алгоритм определения Tic Tac Toe Game Over

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

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

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

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

20 76
javascript algorithm tic-tac-toe

20 ответов:

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

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

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

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

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

32

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

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

A piece from player A has value (1,0)
A piece from player B has value (0,1)

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

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

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

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

two_elements*n_rows + two_elements*n_columns +
two_elements*two_diagonals = 4*n + 4 integers = 4(n+1) integers

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

19

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

после того, как игрок ставит фигуру на позицию (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. никакой магии. :)
17

вот мое решение, которое я написал для проекта, над которым я работаю в 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;
}
8

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

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

вы найдете мой алгоритм, такой как он есть, в

6

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

если он принимает только 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;
        }
    }
}
5

Я не знаю Java так хорошо, но я знаю C, поэтому я попробовал идея магического квадрата АДК (вместе с ограничение поиска 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 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 :(
%

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

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

3

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

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

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

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

3

способ без цикла, чтобы определить, если точка была на анти diag:

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

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

вот код 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;
}
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), но я нашел это довольно простым и наслаждался рекреационной математикой.

1

Мне нравится этот алгоритм, поскольку он использует представление платы 1x9 vs 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;
}
1

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

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

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

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

0

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

0

Как насчет следующего подхода для 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 в зависимости от того, какой игрок выиграл) Победа-2: a4+a5+a6 Win-3: a7+a8+a9 Победа-4: a1+a4+a7 .... Победа-7: a1+a5+a9 Win-8: a3+a5 + a7

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

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

0

постоянное время O (8), в среднем 4 коротких И. игрок = короткий номер. Нуждается в дополнительных проверках, чтобы убедиться, что движение действительно. 

// 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));
0

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

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

}

0

Если у вас есть поле границы 5*5 для examle, я использовал следующий метод проверки:

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

Я думаю, это более понятно, но, вероятно, не самый оптимальный способ.

0

Я разработал алгоритм для этого в рамках научного проекта сразу.

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

Он медленный, но он имеет преимущество работы на любой размерной плате, с довольно линейными требованиями к памяти.

Я хотел бы найти свою реализацию

-1