0

我开始学习球拍,我正在使用任意数量树和生成递归从给定的板上获取板的每个可能版本。

所以假设我有这个板,其中 false 表示为空:

(list "X" "X" "O" "O" "X" "O" "X" #false "X")

根据要求,解决方案是:

(list
 (list "X" "X" "O" "O" "X" "O" "X" "X" "X")
 (list "X" "X" "O" "O" "X" "O" "X" "O" "X"))

球拍中的解决方案效果很好。我在 Python 中尝试了同样的事情,但它并没有像预期的那样工作。

我不断得到这样的输出:

[['X', 'X', 'O', 'O', 'X', 'O', 'X', 'X', 'X'], [['X', 'X', 'O', 'O', 'X', 'O', 'X', 'O', 'X'], []]]

或者

['X', 'X', 'O', 'O', 'X', 'O', 'X', 'X', 'X', 'X', 'X', 'O', 'O', 'X', 'O', 'X', 'O', 'X']

或更糟。

我似乎无法让它给我想要的输出。

如果没有其他方法,我正在考虑对输出进行一些后期处理,但我想避免这种情况。

我需要的是这个:

[['X', 'X', 'O', 'O', 'X', 'O', 'X', 'X', 'X'], ['X', 'X', 'O', 'O', 'X', 'O', 'X', 'O', 'X']]

无论如何,让我知道您是否可以提供帮助。

这是我的python代码:

"""
Brute force solution for tic-tac-toe.
"""


"""
Data definitions:

;; Value is one of:
;; - false
;; - "X"
;; - "O"
;; interp. a square is either empty (represented by false) or has and "X" or an "O"


;; Board is (listof Value)
;; a board is a list of 9 Values

"""

#
## CONSTANTS
#
B0 = [False for i in range(9)]
B1 = [
    False,  "X",  "O",
     "O",   "X",  "O",
    False, False, "X"
]
B2 = [
        "X",  "X",  "O",
        "O",  "X",  "O",
        "X", False, "X",
      ]

B3 = [
        "X", "O",  "X",
        "O", "O", False,
        "X", "X", False,
]


"""
PROBLEM 1

 In this problem we want you to design a function that produces all
 possible filled boards that are reachable from the current board.

 In actual tic-tac-toe, O and X alternate playing. For this problem
 you can disregard that. You can also assume that the players keep
 placing Xs and Os after someone has won. This means that boards that
 are completely filled with X, for example, are valid.

"""


def fill_board(index, bd):
    """
    Returns a list of 2 board versions with
    the index filled with "X" and "O"

    :param index: int; index of position in list to be filled
    :param bd: Board
    :return: (listof Board)
    """
    return [
        bd[:index] + ["X"] + bd[index+1:],
        bd[:index] + ["O"] + bd[index + 1:],
    ]


assert fill_board(0, B1) == [
    [
    "X",  "X",  "O",
     "O",   "X",  "O",
    False, False, "X"
    ],
    [
    "O",  "X",  "O",
     "O",   "X",  "O",
    False, False, "X"
    ],
]

assert fill_board(5, B3) == [
[
        "X", "O",  "X",
        "O", "O", "X",
        "X", "X", False,
],
[
        "X", "O",  "X",
        "O", "O", "O",
        "X", "X", False,
],
]


def find_blank(bd):
    """
    Return the index of the
    first empty (False) value
    in the board.
    ASSUME: there is at least one
    empty cell.

    :param bd: Board
    :return:  Index
    """
    return bd.index(False)

assert find_blank(B0) == 0
assert find_blank(B2) == 7
assert find_blank(B3) == 5


def next_boards(bd):
    """
    Produce the next version of initial board.
    Finds the first empty (False) cell, and produces
    2 versions of the board; one with X and one with O
    :param bd: Board
    :return: (listof Board)
    """

    return fill_board(find_blank(bd), bd)


assert next_boards(B0) == [
    ["X"] + B0[1:],
    ["O"] + B0[1:],
]


assert next_boards(B3) == [
[
        "X", "O", "X",
        "O", "O", "X",
        "X", "X", False,
],
[
        "X", "O", "X",
        "O", "O", "O",
        "X", "X", False,
],
]


def solve(bd):
    """
    Produce all possible filled boards that are
    reachable from the current board.

    :param bd: Board (listof Value)
    :return:  (listof Board)
    """
    def is_full(bd):
        """
        Returns true if board is full; meaning
        if every value on the board is a string.

        :param bd: Board (listof Value)
        :return: Boolean
        """
        return all(type(i) is str for i in bd)

    def solve__bd(bd):
        """
        Mutually refential function with
        solve__lobd. This is where all the actual
        computation takes place.
        The two functions are responsible for
        generating and operating on the tree.
        The tree (arbitraty arity tree) represents
        another version of the board filled with an
        additional X or O.

        :param bd: Board (listof Value)
        :return: (listof Board)
        """

        if is_full(bd):
            return list(bd)

        return solve__lobd(next_boards(bd))

    def solve__lobd(lobd):
        """
        Helper function of solve, alongside solve__bd
        :param lobd: (listof Board)
        :return:     (listof Board)
        """

        if not lobd:
            return []

        return [solve__bd(lobd[0]), solve__lobd(lobd[1:])]

    return solve__bd(bd)


assert solve(B2) == [
    [
        "X", "X", "O",
        "O", "X", "O",
        "X", "X", "X",
      ],
    [
        "X", "X", "O",
        "O", "X", "O",
        "X", "O", "X",
      ],
]


assert solve(B3) == [
    [
        "X", "O", "X",
        "O", "O", "X",
        "X", "X", "X",
    ],
    [
        "X", "O", "X",
        "O", "O", "X",
        "X", "X", "O",
    ],
    [
        "X", "O", "X",
        "O", "O", "O",
        "X", "X", "X",
    ],
    [
        "X", "O", "X",
        "O", "O", "O",
        "X", "X", "O",
    ],
]
4

1 回答 1

0

这看起来像一个类似缺点的混乱。我没有对此进行测试,但我敢打赌你的问题出现在这里:

return [solve__bd(lobd[0]), solve__lobd(lobd[1:])]

我猜你想要

return [solve__bd(lobd[0])] + solve__lobd(lobd[1:])]

... 反而。

但是:Python 列表不是链表。cons在 Racket 中将元素添加到列表中是一种有效且合理的方法,但是+在单元素列表和更长的列表上使用 Python 的运算符形成列表将需要复制列表的所有后续元素。

对于短列表(例如,对少于 10K 个元素的列表进行线性运算或对少于 100 个元素左右的列表进行二次运算),这无关紧要。对于更长的,它会的。Python 人会告诉你你做错了,你应该在现有数组上使用突变。然后球拍的人会告诉你,Python 人被困在过去。欢迎来到精彩的编程世界!

于 2017-07-20T11:54:12.480 回答