使用二維數組遞歸檢查TicTacToe中的獲勝者？

Question

我正在Java中製作一個TicTacToe遊戲我需要使用一個二維數組，並使用遞歸來檢查是否有贏家。

我覺得我可以很容易地做一個非遞歸檢查獲勝者，但我不知道從哪裏開始，如果我使用遞歸來做到這一點，因爲我在遞歸方面很新穎。有人可以指導我在哪裏開始這種算法的過程？

Answer 1

假設你的板子看起來像：

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

現在，理所當然地認爲是一個相當有限的（和做作）使用遞歸，但是，正如你所說，這不適合遞歸的情況。如果您不打算將其擴展爲超過標準的3x3井字遊戲，那麼最好使用八個if聲明。

Answer 2

我同意使用這種遞歸似乎有點被迫。然而，一個想法是基於勝利的定義：在任何方向上連續三個X或O.首先選擇一個潛在的起點（除了中間的任何地方，不能開始一個3平方的行），並選擇一個可能的工作方向。 （可能工作的一組方向是起始方塊的函數。）遞歸步驟是：如果您需要沿着特定方向排成一行，例如X，並且當前位置具有X，然後朝那個方向邁出一步，然後從那裏開始尋找（n - 1）。當n = 0時停止。對於每個起點和方向執行此整個過程，直到您找到勝利或用完選項。

我覺得這足以讓你開始。