Python：实现空当接龙的深度优先搜索

Question

我已经尝试用 DFS 解决空当接龙游戏一个多月了，现在只取得了部分成功。我是一个新手，没有 CS 背景，第一次使用 classes 和递归来解决问题，主要是试图模仿我通过 Google-searches 和 Stack Overflow 帖子找到的东西. （非常欢迎对代码清晰度等提出一般性意见）

游戏代码在这里：https://pastebin.com/39KGZAW1，我希望它是可以理解的。其背后的想法是：

创建 Board (class) 的实例，类似于游戏中的快照
找到所有可能的走法
每一步创建一个新实例，update（class 函数）该棋盘

问题是：

似乎花的时间太长了（当我尝试保存每个板时计算机运行内存不足，所以我停止并使用了生成器和双端队列），从未找到解决方案
当我尝试使用 mini_stacks（少于 13 张卡片的卡片组，目前只有 1 和 2 ！）它似乎也没有找到任何解决方案。
递归方法似乎比 while-loop

Boards

更多细节：游戏逻辑编码完成后，我主要尝试了两种DFS的方法。第一个是递归函数：

def rec(board):

    if not board.moves:
        return 
    else:
        for i in board.moves:
            new = copy.deepcopy(board) # instead of a deep copy I also tried 
            # creating a new instance taking inputs directly from the board
            globals()["it"] += 1 # for lack of a better way
            new.tt = globals()["it"]
            new.update(i)
            if new._end == True:
                raise Exception("Solved!") # didn't focus on this yet
            boards.append(new)
            rec(new)

game = Board(mini_stacks) # or full_stacks, to initialize the recursion
rec(game) # start the recursion with the game

第二种方法是使用 while 循环：

game = Board(mini_stacks)
boards = deque()
boards.append(game)
while boards:  

    current_search = boards.popleft()
    if current_search._end:
        print("Win")
        winning = copy.deepcopy(current_search)
        break # win

    if current_search.moves:
        for no,move in enumerate(current_search.moves):
            new = copy.deepcopy(current_search)
            it += 1
            new.tt = it
            new.update(move)
            boards.insert(no,new)

稍作修改，我创建了一个生成器函数（也是新概念）并将其用于 while 循环，添加了一个堆栈（=deque？）：

def next_generator(boards=boards):

    if boards[0].moves:
        for no,move in enumerate(boards[0].moves):
            new = copy.deepcopy(boards[0])
            globals()["it"] += 1
            new.tt = globals()["it"]
            new.update(move)
            boards.append(new)
        yield boards.popleft()

while True:

    current_search = next(next_generator())
    if current_search._end:
        print("Win")
        winning = copy.deepcopy(current_search)
        break # win 

game = Board(mini_stacks)
boards = deque()
boards.append(game)
next_generator()

Answer 1

所以在休息后我找到了它。看起来，它既不是递归也不是 while 循环。我做了以下事情：

核心代码（pastebin link）的重大变化：

删除了我检查 memory 中的第一项是否在切片 [1:] 中的部分，而是在 add_moves 函数中，就在将移动附加到 self._moves 我检查它是否已经在内存中：if move not in self.memory: self._moves.append(move) （为每个追加都这样做）
- 我现在使用游戏中的纸牌数量（堆叠中找到的最大数量）代替对获胜条件进行硬编码

核心代码的小改动：

已删除 self.memory.append("move 0")，因为没有必要
在 add_moves 函数中，我为每张卡片和堆叠添加了一种颜色，而不仅仅是具有不同的形状。一个简单的：if card[2][1] in ["D","H"]: card_color = "red" 和 else: card_color = "black"（堆叠中的每张牌都有一张，将牌更改为 stack[-1][1]

使用第二种方法（while 没有函数定义的循环）我测试了各种大小的堆栈。当花费太多时间时，我停止程序，洗牌并重新运行。对于大小为 2-6 的解决方案相对较快，然后对于 7+ 的时间（以及创建的 Board 个对象）猛增。我尝试了 9,11 和 13 卡，但没有很快找到解决方案，最终我感到无聊。

在这里您可以看到没有创建棋盘，直到解决（或停止）每副牌大小 5 次重新运行s（洗牌）。

Python：实现空当接龙的深度优先搜索

Python: Implementing Depth-First Search for Freecell Solitaire

python

recursion

depth-first-search

python-3.x