Поиск в глубину в Python

Question

Хорошо, в общем, я пытаюсь выполнить поиск в глубину для пасьянса с мини-колышками. Для тех, кто не знаком с игрой, все довольно просто.

Есть доска с 10 лунками и 9 колышками, колышек представлен 1, а пустое пятно - 0. Вы можете перемещать колышек назад или вперед на две лунки за раз (но вы можете двигаться только на пустой отверстие), и если в процессе вы перепрыгиваете через другой колышек, вы вынимаете его, и он становится дырой.

Вот как выглядит игра:

[1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 1, 0, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1] #etc until only 1 peg left

Итак, у меня есть функция генератора, которая находит все допустимые ходы для определенного "узла" или игрового поля:

def succ(self, node):
    size = len(node)

    # find all legal moves going forward
    for pos in range(0, size-1):
        new_node = list(node)
        if ((node[pos] == 1) and (pos < (size - 2)) and (node[pos+2] == 0)):
            new_node[pos] = 0  # we're moving now
            new_node[pos+2] = 1 # this is where we're moving the peg to
            new_node[pos+1] = 0  # take out the peg here if there was one
            yield new_node

    # find all legal moves going backwards
    for pos in range(0, size-1):
        new_node = list(node)
        if ((node[pos] == 1) and (pos > 1) and (node[pos-2] == 0)):
            new_node[pos] = 0  # we're moving now
            new_node[pos-2] = 1 # this is where we're moving the peg
            new_node[pos-1] = 0  # take out the peg here if there was one
            yield new_node

Теперь, если вы знаете поиск в глубину, это похоже на БОЛЬШОЙ генератор, который можно использовать при решении этой головоломки. Либо это? (Я думаю, что, может быть, вы можете помочь придумать более Pythonic способ?)

Ну, моя функция решения рекурсивных головоломок, которая будет использовать генератор, не работает, может, вы мне поможете?

def goal(self, node):
    pegs = 0

    for pos in node:
        if pos == 1:
            pegs += 1

    return (pegs == 1) # returns True if there is only 1 peg

def solve_board(dfs_obj, node):
    if goal(node):  # only 1 peg!
        print node
        return node

    for new_node in succ(node):
        print new_node
        return solve_board(new_node)

if __name__ == "__main__":
    solve_board([1, 1, 1, 1, 1, 0, 1, 1, 1, 1])

Так что, в принципе, я думаю, что моя функция succ () делает правильные вещи (может, это не так?), Но моя рекурсия solve_board () может быть прикольной, потому что плата не решает.

Answer 1

Поскольку вам разрешено перепрыгивать через пустые дыры, вам придется отслеживать любые узлы, которые вы уже посетили. В противном случае у вас будет бесконечный цикл.

Вам также не нужно замыкать цикл for, если вы не нашли цель

tested_nodes=set()
def solve_board(dfs_obj, node):
    if goal(node):  # only 1 peg!
        print node
        return node

    for new_node in succ(node):
        if tuple(new_node) not in tested_nodes:
            tested_nodes.add(tuple(new_node))
            print new_node
            result = solve_board(new_node)
            if result:  # True if it's a goal, None otherwise
                return result

У вас неверный диапазон в вашей функции succ, вы не должны вычитать 1 из размера диапазона. Вы также можете переписать его так, чтобы удалить одно из условий из if

def succ(self, node):
    size = len(node)

    # find all legal moves going forward
    for pos in range(size-2):
        new_node = list(node)
        if ((node[pos] == 1) and (node[pos+2] == 0)):
            new_node[pos] = 0  # we're moving now
            new_node[pos+2] = 1 # this is where we're moving the peg to
            new_node[pos+1] = 0  # take out the peg here if there was one
            yield new_node

    # find all legal moves going backwards
    for pos in range(1,size):
        new_node = list(node)
        if ((node[pos] == 1) and (node[pos-2] == 0)):
            new_node[pos] = 0  # we're moving now
            new_node[pos-2] = 1 # this is where we're moving the peg
            new_node[pos-1] = 0  # take out the peg here if there was one
            yield new_node

Другой способ написать функцию succ - это

def succ(self, node):
    for i in range(len(node)-2):
        j=i+3
        if node[i:j]==[1,1,0]:
            yield node[:i]+[0,0,1]+node[j:]
        if node[i:j]==[0,1,1]:
            yield node[:i]+[1,0,0]+node[j:]
        if node[i:j]==[1,0,0]:
            yield node[:i]+[0,0,1]+node[j:]
        if node[i:j]==[0,0,1]:
            yield node[:i]+[1,0,0]+node[j:]

Сначала слегка настраивает глубину, предпочитая движения, которые удаляют колышек

Answer 2

Я не расшифровал вашу функцию succ (), но при условии, что она работает, остальная часть программы действительно выполняет поиск в глубину. Я так понимаю, что код не заканчивается? Если succ может вернуть ранее обнаруженное состояние, то у вас может быть бесконечное дерево решений, и поиск в глубину может застрять в бесконечной ветви и пропустить правильное решение в другой ветви. В этом случае вам нужно использовать поиск в ширину.