0

我为 8 个谜题问题的广度搜索算法编写了一个 python 代码。游戏的状态被编码为列表列表（二维列表）。目标是从给定状态到达[[1,2,3],[8,0,4],[7,6,5]]。代码输出从给定状态到目标的路径。它工作正常，但对于这种特殊情况[[0,1,2],[7,8,3],[6,5,4]]并没有给出整个路径，而是给出了路径中的最后三个状态。

请您尝试指出错误的位置。这是代码。注意程序从语句开始：

"""
This program solves the 8 puzzel problems using Breadth First Search Algorithm.
"""

import copy

def successor(astate):
    """
    This function takes an instance of the 8 puzzel problem and generates all the legal successors.
    """
    up = copy.deepcopy(astate)
    """
    important note:
    I use [:] and list() to copy lists but it was not working fine, hence deecopy is used instead.
    """
    down = copy.deepcopy(astate)
    left = copy.deepcopy(astate)
    right = copy.deepcopy(astate)
    successors = []
    for i in range(3):
        for j in range(3):
            if astate[i][j] == 0:
                row = i
                col = j
    if row != 0:
        dummy = up[row][col]
        up[row][col] = up[row -1][col]
        up[row-1][col] = dummy
        successors.append(up)
    if row != 2:
        dummy = down[row][col]
        down[row][col] = down[row+1][col]
        down[row+1][col] = dummy
        successors.append(down)
    if col != 2:
        dummy = right[row][col]
        right[row][col] = right[row][col+1]
        right[row][col+1] = dummy
        successors.append(right)
    if col != 0:
        dummy = left[row][col]
        left[row][col] = left[row][col-1]
        left[row][col-1] = dummy
        successors.append(left)
    return successors


def puzzle(astate):
    """
    This function takes a given instance of the 8 puzzel problem and returns the path to the goal where the goal is defined as below.
    """
    goal = [[1,2,3],[8,0,4],[7,6,5]]    #The goal state.
    generation = [astate]    #Nodes generated at each level.
    tracking = {}    #Track the path to the goal.
    path = []    #The path from the root to the goal.
    parent = generation.pop(0)    #Takes the first element of the list!!
    successors = successor(parent)    #Generate successors.
    key = str(parent)    #keys odictionaries must be hashable and mutable. Lists are illegal keys.
    tracking[key] = successors    #Associate successors with their parent.
    for asuccessor in successors:
        generation.append(asuccessor)    #Generate the first level.
    if goal in generation:    #if the goal is among the successors returns the path to it.
        path.insert(0, key)
        path.insert(0, goal)
        return path
    else:
        while generation != []:    #keep searching!
            parent = generation.pop(0)
            successors = successor(parent)    #generate successors 
            key = str(parent)
            tracking[key] = successors
            if goal in [astate for astate in successors]:    #if the goal is among the successors backtrack its path.
                path.insert(0, str(goal))    #Just because path contains states as strings!!
                path.insert(0, key)
                for key in tracking.keys():
                    for value in tracking.get(key):
                        if str(parent) == str(value):    #If the current (parent) is among the values of (key) then (key) is its parent.
                            path.insert(0, key)
                            parent = key
                            break
                return  path
            else:    #keep searching
                for asuccessor in successors:
                    if asuccessor not in generation:    #If the current successors is already generated do not add it.
                        if str(asuccessor) not in tracking.keys():    #If the successor is a previous parent do not add it.
                            generation.append(asuccessor)
        return
4

0 回答 0