在Python中递归生成每个Tic-Tac-Toe游戏

Question

我正在开发一个项目,我生成每个可能的井字游戏阵列.作为一个概念证明,我正在研究用9个子数组填充数组的代码.每个子数组将有两个值,第一个为0或1(分别为x和o),第二个为1到9(表示放置时).我希望得到的数组示例如下:

[[0, 0], [1, 1], [0, 2], [1, 3], [0, 4], [1, 5], [0, 6], [1, 7], [0, 8]]

我已经编写了代码,使用9 for循环,每个循环嵌套在上面的一个,这给了我想要的结果(每个可能的数组,每个都是唯一的).但我试图编写代码,使用递归,并避免编写大量的嵌套循环.

当我运行下面的代码时,它只能生成上面的数组,并且无法创建其他组合.我的代码如下:

print("running...")

allGames = []
checkCurrentGame = [5, 5, 5, 5, 5, 5, 5, 5, 5]
stepsDown = 0

def cleanGame(move, currentGame):
    for j in range(9):
        if (currentGame[j][1] >= move):
            currentGame[j] = [5, 0]

def completeMove(moveNumber, currentGame):
    global stepsDown
    stepsDown = stepsDown + 1
    for i in range(9):
        cleanGame(moveNumber, currentGame)
        if (currentGame[i][0] == 5):
            currentGame[i][0] = i % 2
            currentGame[i][1] = moveNumber
            allGames.append(currentGame)
            break
    if (stepsDown < 9):
        generateGame(currentGame)

def generateGame(currentGame):
    for i in range(9):
        completeMove(i, currentGame)

generateGame([[5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0], [5, 0]])

for x in range(len(allGames)):
    print(allGames[x])

Answer 1

我建议您在 YouTube 上观看此视频。教授对递归讲得非常好。我认为这比获得工作代码对您更有利。他以数独为例，但这两个游戏都只是二维数组。

如果您观看了该视频，您将知道如何修改此示例以更好地满足您的需求。伪代码：

def place(who, when, where, table):
    if (None, None) not in table: # the table is full
        print(table)
        return

    if table[where] not (None, None): # this cell is already marked
        return

    table[where] (who, when) # can place our mark on the cell
    # make the recursive calls
    for i in range(9):
        place(who.opponent, when+1, i, table)

for cell in range(9):
    empty = [(None, None) for _ in range(9)]
    place(firstplayer, 0, cell, empty)