python解决八数码问题

听城

发布于 2018-04-27 14:59:21

2.4K0

发布于 2018-04-27 14:59:21

八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始状态转变成目标状态的移动棋子步数最少的移动步骤

一开始也是两眼一抹黑，连八数码是什么都不知道，经过度娘得到如上结果。那该如何实现呢？如果移动数字的话，8个数字，每次移动有4种选择，那就是32个种移动方案。那移动空格就只有4种选择，一下子清楚了很多。至于存储方案当然是数组了，交换起来多方便，是吧？实现方式呢？最初实验要求使用回溯算法解决，什么，回溯？！那不是和深度优先一样吗？无脑走找结果？算了，先试试吧。

import numpy as np

#返回两个数组对应位置相同值的个数
def calc(state1):
    b = np.array([[1, 2, 3], [8, 0, 4], [7, 6, 5]])
    postion = np.where(state1 == b)
    return len(state1[postion])
#打印八数码
def showInfo(a):
    for i in range(3):
        for j in range(3):
            print(a[i, j], end='   ')
        print("\n")
    print('->')
directions = ['up', 'down', 'left', 'right']

def SubStates(state):
    subStates = []
    row, col = np.where(state==0)
    for direction in directions:
        if 'left' == direction and col > 0:
            s = state.copy()
            s[row, col],s[row, col - 1] = s[row, col - 1],s[row, col]
            subStates.append(s)
        if 'up'  == direction and row > 0:
            s = state.copy()
            s[row, col],s[row - 1, col] = s[row - 1, col],s[row, col]
            subStates.append(s)
        if 'down'  == direction and row < 2:
            s = state.copy()
            s[row, col],s[row + 1, col] = s[row + 1, col],s[row, col]
            subStates.append(s)
        if 'right'  == direction and col < 2:
            s = state.copy()
            s[row, col],s[row, col + 1] = s[row, col + 1],s[row, col]
            subStates.append(s)
    return subStates
def DFS(first):
    stack = []
    stack.append(first)
    count = -1
    while stack:
        count += 1
        node = stack.pop()
        showInfo(node)
        if calc(node) == 9:
            return True,count
        s = SubStates(node)
        #res = sorted(s, key=calc)
        for x in res:
            stack.append(x)


#主函数
def main():
    start = np.array([[0, 1, 3], [8, 2, 4], [7, 6, 5]])
    #start = np.array([[2, 8, 3], [1, 0, 4], [7, 6, 5]])
    res,count = DFS(start)
    if res:
        print('经过%d次变换结束' %count)
if __name__ == '__main__':
    main()

用迭代方式很容易的写出了深度优先算法，可是貌似跑不出结果。。。what a fuck，什么鬼？遂找了个只移动两次的，运行，还是不行。随机压栈太疯狂了，加点约束吧。每次找和最终结果最相似的出栈应该可以。（这里说一下为了防止无限次循环，用宽度优先搜素比较合适，只需把pop()改成pop(0),如果用到排序的话那就要按相似度由高到低排列了）嗯，加上这句res = sorted(s, key=calc),压栈前按相似度由低到高做一次排序。移动两次的果然跑出来了，可是移动多次的还是不行。得，再想办法吧。做一个界限函数，用八数码迭代出来的层数加上相似度来搜索。这个值在一定限度才入栈，否则舍弃。这里我将节点封装成一个类来实现。

import numpy as np

class eightPuzzle(object):

    directions = ['up', 'down', 'left', 'right']
    max = 7
    def __init__(self,arr,cost=0,parent=None):
        self.arr = arr
        self.cost = cost
        self.parent = parent

    def getCost(self):
        return self.cost
    # 返回两个数组对应位置相同值的个数
    def calc(self,state):
        final = np.array([[1, 2, 3], [8, 0, 4], [7, 6, 5]])
        postion = np.where(state.arr == final)
        return len(state.arr[postion])

    # 打印八数码
    def showInfo(self):
        for i in range(3):
            for j in range(3):
                print(self.arr[i, j], end='   ')
            print("\n")
        print('->')

    def calc2(self, state1, stop):
        for x in stop:
            postion = np.where(state1.arr == x.arr)
            if len(state1.arr[postion]) == 9:
                return True
        return False

    def SubStates(self):
        subStates = []
        row, col = np.where(self.arr==0)
        for direction in self.directions:
            if 'left' == direction and col > 0:
                s = self.arr.copy()
                s[row, col],s[row, col - 1] = s[row, col - 1],s[row, col]
                new = eightPuzzle(s,self.cost+1,self)
                subStates.append(new)
            if 'up'  == direction and row > 0:
                s = self.arr.copy()
                s[row, col],s[row - 1, col] = s[row - 1, col],s[row, col]
                new = eightPuzzle(s, self.cost + 1,self)
                subStates.append(new)
            if 'down'  == direction and row < 2:
                s = self.arr.copy()
                s[row, col],s[row + 1, col] = s[row + 1, col],s[row, col]
                new = eightPuzzle(s, self.cost + 1,self)
                subStates.append(new)
            if 'right'  == direction and col < 2:
                s = self.arr.copy()
                s[row, col],s[row, col + 1] = s[row, col + 1],s[row, col]
                new = eightPuzzle(s, self.cost + 1,self)
                subStates.append(new)
        return subStates
    def DFS(self):
        stack = []
        stop = []
        stack.append(self)
        count = -1
        while True:
            if not stack:
                return False,count,node
            count += 1
            #stack = sorted(stack, key=self.calc)
            node = stack.pop()
            stop.append(node)
            node.showInfo()
            if self.calc(node) == 9:
                return True,count,node
            s = node.SubStates()
            if s:
                res = sorted(s, key=self.calc)
            else:
                continue
            for x in res:
                if (x.cost + 9 - self.calc(x))< eightPuzzle.max:
                    if self.calc2(x,stop):
                        continue
                    stack.append(x)

def showInfo(result):
    for node in result:
        for i in range(3):
            for j in range(3):
                print(node.arr[i, j], end='   ')
            print('\n')
        print('->')
#主函数
def main():
    #start = np.array([[0, 1, 3], [8, 2, 4], [7, 6, 5]])
    start = np.array([[2, 8, 3], [1, 0, 4], [7, 6, 5]])
    p = eightPuzzle(start)
    res,count,node = p.DFS()
    result = []
    if res:
        print('经过%d次变换结束' %count)
        while node:
            result.append(node)
            node = node.parent
        result.reverse()
        showInfo(result)
    else:
        print('规定范围内未找到合适路径，可增大界值')


if __name__ == '__main__':
    main()

这次经过七次搜索得到了最终答案。这时候发现输出很有意思，会出现初始状态。因此在深度搜索的过程中加了一个stop表，用来存储已经出栈的元素，每次入栈的时候查看若已经存在则扔掉。此时运行6次出现答案。结束。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017.10.10 ，如有侵权请联系 cloudcommunity@tencent.com 删除

python