java - 使用二维数组递归检查井字游戏中的获胜者？

Question

我正在用 Java 制作井字游戏，我需要使用二维数组并使用递归来检查是否有赢家。

我觉得我可以轻松地对获胜者进行非递归检查，但是如果我要使用递归来做这件事，我不知道从哪里开始，因为我对递归非常陌生。有人可以指导我从哪里开始这种算法的过程吗？

Answer 1

我同意为此使用递归似乎有点强迫。然而，一个想法是基于胜利的定义：在任何方向连续三个 X 或 O。首先选择一个潜在的起点（除了中间的任何地方，它不能开始一个 3 方格的行），然后选择一个可能有效的方向。（可能起作用的方向集是起始正方形的函数。）递归步骤是：如果您需要在特定方向上的一行中的n，例如 X，并且当前位置有一个 X，则取朝那个方向迈出一步，然后从那里开始朝那个方向连续寻找 ( n - 1)。当n = 0时停止。为每个起点和方向执行整个过程，直到找到胜利或用完所有选择。

我认为，这足以让你开始。

Answer 2

假设您的电路板看起来像：

            |            |
 cell[0][0] | cell[1][0] | cell[2][0]
            |            |
------------+------------+------------
            |            |
 cell[0][1] | cell[1][1] | cell[2][1]
            |            |
------------+------------+------------
            |            |
 cell[0][2] | cell[1][2] | cell[2][2]
            |            |

一种方法是简单地递归检查相邻的单元格（在一个方向上）。例如（伪代码）：

def checkSame (val, cellX, cellY. deltaX, deltaY):
    # No winner if check value is empty.

    if val == empty: return false

    # Winner if we've gone off edge. No need to worry about < 0
    # since one direction is always ascending but I've left it
    # in anyway.

    if cellX > 2 or cellY > 2: return true
    if cellX < 0 or cellY < 0: return true

    # No winner if piece has changed.

    if cell[cellX][cellY] != val: return false

    # Otherwise use recursion to check next one.

    return checkSame (val, cellX + deltaX, cellY + deltaY, deltaX, deltaY)

然后，我们只需要检查八个可能的起点/方向值：

# Check rows.

if checkSame (cell[0][0], 0, 0, 1, 0): return true
if checkSame (cell[0][1], 0, 1, 1, 0): return true
if checkSame (cell[0][2], 0, 2, 1, 0): return true

# Check columns.

if checkSame (cell[0][0], 0, 0, 0, 1): return true
if checkSame (cell[1][0], 1, 0, 0, 1): return true
if checkSame (cell[2][0], 2, 0, 0, 1): return true

# Check diagonals.

if checkSame (cell[0][0], 0, 0, 1, 1): return true
return checkSame (cell[0][2], 0, 2, 1, -1)

现在，当然，这是对递归的相当有限（和人为）的使用，但是正如您所说，无论如何，这并不是真正适合递归的情况。if如果您不打算将其扩展到超过标准的 3x3 tic-tac-toe，则使用八个语句要好得多。