Python/A算法-八数码问题.py

# 目标序列end = [1,2,3,8,0,4,7,6,5]
# end = 1 2 3
#       8 0 4
#       7 6 5
import sys


class Statusobj:
    def __init__(self):
        # 状态序列
        self.array = []
        # 该状态下的深度
        self.deep = 0
        # 该状态的f(n) = g(n) + h(n)评估函数值
        self.Fn = 0
        # 该状态由上一个状态经何种操作得到，避免出现死循环
        # 1:up  2:down  3:left  4:right
        self.preoperate = 0
        self.Father = Statusobj


# 判断八数码问题是否有解，在于若两个状态的逆序奇偶性 相同，则可相互到达，否则不可相互到达
def getreversenum(array):  # 获取当前状态的逆序数和
    count = 0
    for i in range(len(array)):
        for j in range(i+1, len(array)):
            if array[j] < array[i]:
                count += 1
    return count


def countnotinplace(array, end):  # 统计当前状态和目标状态相比较的不在位将牌数
    count = 0
    for i in range(len(array)):
        if array[i] != end[i] and array[i] != 0:
            count += 1
    return count


def selectoperate(i, preoperate):  # 通过当前状态下的序列下标和上一次操作符得到可选择的操作
    selected = []
    if 3 <= i <= 8 and preoperate != 2:
        selected.append(1)
    if 0 <= i <= 5 and preoperate != 1:
        selected.append(2)
    if i in [1, 2, 4, 5, 7, 8]:
        if preoperate != 4:
            selected.append(3)
    if i in [0, 1, 3, 4, 6, 7]:
        if preoperate != 3:
            selected.append(4)
    return selected


def op(i, x):  # 通过操作符得到新下标
    if i == 1:  # up
        return x-3
    if i == 2:  # down
        return x+3
    if i == 3:  # left
        return x-1
    if i == 4:  # right
        return x+1


def newarray(operate, array):  # 通过操作符拓展的新节点
    subscript = array.index(0)
    newindex = op(operate, subscript)
    temp = array[subscript]
    array[subscript] = array[newindex]
    array[newindex] = temp
    return array


def printarray(array):
    print(f"{array[:3]}\n{array[3:6]}\n{array[6:]}\n", end='')


def main():
    openlist = []  # open表，保存待扩展实例对象
    closelist = []  # close表
    endarray = [1, 2, 3, 8, 0, 4, 7, 6, 5]
    initobj = Statusobj()
    initobj.array = list(map(int, input("请输入原始状态的八数码序列：").split()))
    initobj.deep = 0  # 初始化执行深度
    initobj.Fn = initobj.deep + countnotinplace(initobj.array, endarray)
    openlist.append(initobj)
    array_reverse = getreversenum(initobj.array) - initobj.array.index(0)
    end_reverse = getreversenum(endarray) - endarray.index(0)
    if array_reverse % 2 == end_reverse % 2:
        while True:
            if openlist[0].array == endarray: # 达到目标状态
                end_list = []
                end_list.append(openlist[0])
                deep = openlist[0].deep
                closelist.append(openlist[0])
                del openlist[0]
                father = closelist[-1].Father
                while father.deep >= 1:
                    end_list.append(father)
                    father = father.Father
                end_list.append(initobj)
                print("目标状态：")
                printarray(endarray)
                print("【变换成功,共需要" + str(deep) + "次变换】")
                d = 0
                for it in reversed(end_list):
                    print("当前深度为：{}".format(d))
                    d += 1
                    print("操作序号为：{}".format(it.preoperate))
                    printarray(it.array)
                sys.exit()
            else:
                zero_index = openlist[0].array.index(0)
                temp_list = []
                operation = selectoperate(zero_index, openlist[0].preoperate)
                for ope in operation:
                    copy_array = openlist[0].array.copy()  # .copy()复制序列，必不可少
                    new_array = newarray(ope, copy_array)
                    new_obj = Statusobj()
                    new_obj.array = new_array  # 序列
                    new_obj.deep = openlist[0].deep + 1  # 深度
                    new_obj.preoperate = ope  # 上一操作符
                    new_obj.Father = openlist[0]  # 父亲节点
                    new_obj.Fn = new_obj.deep + countnotinplace(new_array, endarray)  # 评估函数
                    temp_list.append(new_obj)
                closelist.append(openlist[0])
                del openlist[0]
                for item in temp_list:
                    openlist.append(item)
                openlist.sort(key=lambda x: x.Fn)
    else:
        print("此情况下无解！")


main()
# 2 8 3 1 6 4 7 0 5