Java 确定井字游戏结束的算法

Algorithm for Determining Tic Tac Toe Game Over

提问by dreadwail

I've written a game of tic-tac-toe in Java, and my current method of determining the end of the game accounts for the following possible scenarios for the game being over:

我用 Java 编写了一个井字游戏，我目前确定游戏结束的方法考虑了游戏结束的以下可能情况：

1. The board is full, and no winner has yet been declared: Game is a draw.
2. Cross has won.
3. Circle has won.

1. 棋盘已满，尚未宣布获胜者：游戏为平局。
2. 克罗斯赢了。
3. 圆赢了。

Unfortunately, to do so, it reads through a predefined set of these scenarios from a table. This isn't necessarily bad considering that there are only 9 spaces on a board, and thus the table is somewhat small, but is there a better algorithmic way of determining if the game is over? The determination of whether someone has won or not is the meat of the problem, since checking if 9 spaces are full is trivial.

不幸的是，为此，它会从表中读取一组预定义的这些场景。考虑到棋盘上只有 9 个空间，因此桌子有点小，这不一定是坏事，但是有没有更好的算法方法来确定游戏是否结束？确定某人是否获胜是问题的核心，因为检查 9 个空格是否已满是微不足道的。

The table method might be the solution, but if not, what is? Also, what if the board were not size n=9? What if it were a much larger board, say n=16, n=25, and so on, causing the number of consecutively placed items to win to be x=4, x=5, etc? A general algorithm to use for all n = { 9, 16, 25, 36 ... }?

table 方法可能是解决方案，但如果不是，那是什么？另外，如果电路板不是尺寸n=9怎么办？如果它是一个更大的板，比如n=16，n=25等，造成连续放置物品的数量取胜是x=4，x=5等？用于所有人的通用算法n = { 9, 16, 25, 36 ... }？

采纳答案by Hardwareguy

You know a winning move can only happen after X or O has made their most recent move, so you can only search row/column with optional diag that are contained in that move to limit your search space when trying to determine a winning board. Also since there are a fixed number of moves in a draw tic-tac-toe game once the last move is made if it wasn't a winning move it's by default a draw game.

您知道获胜的移动只能在 X 或 O 进行最近一次移动后发生，因此您只能搜索包含在该移动中的可选 diag 的行/列，以在尝试确定获胜棋盘时限制您的搜索空间。此外，由于在画井字棋游戏中有固定数量的走法，如果最后一步不是获胜走法，则默认情况下是平局游戏。

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

编辑：此代码用于 n x n 板，连续 n 获胜（3x3 板需要连续 3 等）

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

编辑：添加了检查反诊断的代码，我无法找出一种非循环方式来确定该点是否在反诊断上，这就是为什么缺少该步骤的原因

public class TripleT {

    enum State{Blank, X, O};

    int n = 3;
    State[][] board = new State[n][n];
    int moveCount;

    void Move(int x, int y, State s){
        if(board[x][y] == State.Blank){
            board[x][y] = s;
        }
        moveCount++;

        //check end conditions

        //check col
        for(int i = 0; i < n; i++){
            if(board[x][i] != s)
                break;
            if(i == n-1){
                //report win for s
            }
        }

        //check row
        for(int i = 0; i < n; i++){
            if(board[i][y] != s)
                break;
            if(i == n-1){
                //report win for s
            }
        }

        //check diag
        if(x == y){
            //we're on a diagonal
            for(int i = 0; i < n; i++){
                if(board[i][i] != s)
                    break;
                if(i == n-1){
                    //report win for s
                }
            }
        }

        //check anti diag (thanks rampion)
        if(x + y == n - 1){
            for(int i = 0; i < n; i++){
                if(board[i][(n-1)-i] != s)
                    break;
                if(i == n-1){
                    //report win for s
                }
            }
        }

        //check draw
        if(moveCount == (Math.pow(n, 2) - 1)){
            //report draw
        }
    }
}

回答by adk

you can use a magic square http://mathworld.wolfram.com/MagicSquare.htmlif any row, column, or diag adds up to 15 then a player has won.

您可以使用魔方http://mathworld.wolfram.com/MagicSquare.html如果任何行、列或 diag 加起来为 15，则玩家获胜。

回答by John Kugelman

If the board is n× nthen there are nrows, ncolumns, and 2 diagonals. Check each of those for all-X's or all-O's to find a winner.

如果棋盘为n× n，则有n行、n列和 2 条对角线。检查每一个全 X 或全 O 以找到赢家。

If it only takes x< nconsecutive squares to win, then it's a little more complicated. The most obvious solution is to check each x× xsquare for a winner. Here's some code that demonstrates that.

如果只需要x< n个连续方格就可以获胜，那么情况就稍微复杂一些。最明显的解决方案是检查每个x× x方格中的获胜者。这是一些演示这一点的代码。

(I didn't actually test this *cough*, but it didcompile 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;
        }
    }
}

回答by rampion

I don't know Java that well, but I do know C, so I tried adk's magic square idea(along with Hardwareguy's search restriction).

我不太了解 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;
}

It compiles and tests well.

它可以很好地编译和测试。

% gcc -o tic-tac-toe tic-tac-toe.c
% ./tic-tac-toe
     |   |
  ---+---+---
     |   |
  ---+---+---
     |   |
  Enter moves as " " (no quotes, zero indexed)
  X's move: 1 2
     |   |
  ---+---+---
     |   | X
  ---+---+---
     |   |
  O's move: 1 2
  illegal move (already taken), try again
  O's move: 3 3
  illegal move (off the board), try again
  O's move: 2 2
     |   |
  ---+---+---
     |   | X
  ---+---+---
     |   | O
  X's move: 1 0
     |   |
  ---+---+---
   X |   | X
  ---+---+---
     |   | O
  O's move: 1 1
     |   |
  ---+---+---
   X | O | X
  ---+---+---
     |   | O
  X's move: 0 0
   X |   |
  ---+---+---
   X | O | X
  ---+---+---
     |   | O
  O's move: 2 0
   X |   |
  ---+---+---
   X | O | X
  ---+---+---
   O |   | O
  X's move: 2 1
   X |   |
  ---+---+---
   X | O | X
  ---+---+---
   O | X | O
  O's move: 0 2
   X |   | O
  ---+---+---
   X | O | X
  ---+---+---
   O | X | O
  tic-tac-toe! O wins!
% ./tic-tac-toe
     |   |
  ---+---+---
     |   |
  ---+---+---
     |   |
  Enter moves as " " (no quotes, zero indexed)
  X's move: 0 0
   X |   |
  ---+---+---
     |   |
  ---+---+---
     |   |
  O's move: 0 1
   X | O |
  ---+---+---
     |   |
  ---+---+---
     |   |
  X's move: 0 2
   X | O | X
  ---+---+---
     |   |
  ---+---+---
     |   |
  O's move: 1 0
   X | O | X
  ---+---+---
   O |   |
  ---+---+---
     |   |
  X's move: 1 1
   X | O | X
  ---+---+---
   O | X |
  ---+---+---
     |   |
  O's move: 2 0
   X | O | X
  ---+---+---
   O | X |
  ---+---+---
   O |   |
  X's move: 2 1
   X | O | X
  ---+---+---
   O | X |
  ---+---+---
   O | X |
  O's move: 2 2
   X | O | X
  ---+---+---
   O | X |
  ---+---+---
   O | X | O
  X's move: 1 2
   X | O | X
  ---+---+---
   O | X | X
  ---+---+---
   O | X | O
  stalemate... nobody wins :(
%

That was fun, thanks!

那很有趣，谢谢！

Actually, thinking about it, you don't need a magic square, just a count for each row/column/diagonal. This is a little easier than generalizing a magic square to n× nmatrices, since you just need to count to n.

实际上，考虑一下，您不需要魔方，只需对每行/列/对角线进行计数即可。这比将幻方推广到n×n矩阵要容易一些，因为您只需要数到n。

回答by Osama Al-Maadeed

How about this pseudocode:

这个伪代码怎么样：

After a player puts down a piece at position (x,y):

玩家在 (x,y) 位置放下棋子后：

col=row=diag=rdiag=0
winner=false
for i=1 to n
  if cell[x,i]=player then col++
  if cell[i,y]=player then row++
  if cell[i,i]=player then diag++
  if cell[i,n-i+1]=player then rdiag++
if row=n or col=n or diag=n or rdiag=n then winner=true

I'd use an array of char [n,n], with O,X and space for empty.

我会使用一个 char [n,n] 数组，其中 O,X 和空格为空。

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

1. 简单的。
2. 一圈。
3. 五个简单变量：4 个整数和一个布尔值。
4. 缩放到任意大小的 n。
5. 只检查当前作品。
6. 没有魔法。:)

回答by bgw

I developed an algorithm for this as part of a science project once.

我曾经为此开发了一种算法，作为科学项目的一部分。

You basically recursively divide the board into a bunch of overlapping 2x2 rects, testing the different possible combinations for winning on a 2x2 square.

您基本上递归地将棋盘划分为一堆重叠的 2x2 矩形，测试在 2x2 方格上获胜的不同可能组合。

It is slow, but it has the advantage of working on any sized board, with fairly linear memory requirements.

它很慢，但它的优点是可以在任何大小的板上工作，并且具有相当线性的内存要求。

I wish I could find my implementation

我希望我能找到我的实现

回答by CJ Gaconnet

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

这类似于Osama ALASSIRY 的答案，但它用恒定空间和线性时间换来了线性空间和恒定时间。也就是说，初始化后没有循环。

Initialize a pair (0,0)for each row, each column, and the two diagonals (diagonal & anti-diagonal). These pairs represent the accumulated (sum,sum)of the pieces in the corresponding row, column, or diagonal, where

(0,0)为每行、每列和两条对角线（对角线和反对角线）初始化一对。这些对代表(sum,sum)相应行、列或对角线上的碎片的累积，其中

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

When a player places a piece, update the corresponding row pair, column pair, and diagonal pairs (if on the diagonals). If any newly updated row, column, or diagonal pair equals either (n,0)or (0,n)then either A or B won, respectively.

当玩家放置一块时，更新相应的行对、列对和对角线对（如果在对角线上）。如果任何新更新的行、列或对角线对等于(n,0)或，(0,n)则 A 或 B 分别获胜。

Asymptotic analysis:

渐近分析：

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

For the memory use, you use 4*(n+1)integers.

对于内存使用，您使用4*(n+1)整数。

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

Exercise: Can you see how to test for a draw in O(1) time per-move? If so, you can end the game early on a draw.

练习：你能看到如何在每次移动的 O(1) 时间内测试平局吗？如果是这样，您可以在平局时提前结束游戏。

回答by Jeff

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

一种确定该点是否在反诊断上的非循环方式：

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

回答by mattR

I just wrote this for my C programming class.

我只是为我的 C 编程课写了这个。

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

我发布它是因为这里的其他示例都不会与任何大小的矩形网格一起使用，并且任何数量的连续N个标记都可以获胜。

You'll find my algorithm, such as it is, in the checkWinner()function. It doesn't use magic numbers or anything fancy to check for a winner, it simply uses four for loops - The code is well commented so I'll let it speak for itself I guess.

你会在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.

回答by sanjiv

I made some optimization in the row, col, diagonal checks. Its mainly decided in the first nested loop if we need to check a particular column or diagonal. So, we avoid checking of columns or diagonals saving time. This makes big impact when the board size is more and a significant number of the cells are not filled.

我在行、列、对角线检查中做了一些优化。如果我们需要检查特定的列或对角线，它主要在第一个嵌套循环中决定。因此，我们避免检查列或对角线以节省时间。当电路板尺寸更大并且大量单元格未填充时，这会产生很大影响。

Here is the java code for that.

这是用于此的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;
}