数字华容道-15拼图问题

题意

最近要做一道题目，题目的意思是：

用尽量少的步数，尽量短的时间，将棋盘上的数字方块，按照从左到右、从上到下的顺序重新排列整齐

1.首先要判断是否可达

2.其次使用的是3种算法来解决

a.深度优先搜索

b.广度优先搜索

c.迭代加深的深度优先搜索

【上图为三阶】

思路

把问题看成0在往4个方向走，不断的与相邻的数进行交换形成新的状态图，但要注意重复出现的状态，也要注意移动的时候是否触及边界。0的走法不唯一，所以有bfs,dfs和id-dfs。

如何判断是否有解？

• 若格子列数为奇数，则逆序数必须为偶数
• 若格子列数为偶数，且逆序数为偶数，则当前空格所在行数与初始空格所在行数的差为偶数
• 若格子列数为偶数，且逆序数为奇数，则当前空格所在行数与初始空格所在行数的差为奇数

如何求逆序数个数？

a = np.array(self.arr).flatten()
b = list(a)
b.remove(0)
ans = 0
for i in range(len(b)):
    for j in range(i + 1, len(b)):
        if b[i] > b[j]:
            ans += 1
return ans 

如何找到0的位置？

index = np.argwhere(np.array(self.arr) == 0)
return index[0][0], index[0][1]

如何对0进行移动？

def move_0(self, direction):
    """
        移动0的位置
        :param direction: U D L R 上下左右
        :return: 是否可移动，移动后的节点
        """
    # 复制当前矩阵数据
    new_arr = deepcopy(self.arr)
    # 找到0的位置
    x, y = self.find_0()
    # 判断移动方向进行移动+判断边界
    if direction == 'U':
        if x == 0:
            return False, None
        else:
            new_arr[x][y] = new_arr[x - 1][y]
            new_arr[x - 1][y] = 0
            elif direction == 'D':
                if x == len(new_arr) - 1:  # 如果x在最后一行
                    return False, None
                else:
                    new_arr[x][y] = new_arr[x + 1][y]
                    new_arr[x + 1][y] = 0
                    elif direction == 'L':
                        if y == 0:
                            return False, None
                        else:
                            new_arr[x][y] = new_arr[x][y - 1]
                            new_arr[x][y - 1] = 0
                            elif direction == 'R':
                                if y == len(new_arr) - 1:
                                    return False, None
                                else:
                                    new_arr[x][y] = new_arr[x][y + 1]
                                    new_arr[x][y + 1] = 0
                                    return True, Node(arr=new_arr, parent=self, depth=self.depth + 1)

BFS

广度优先搜索算法，需要用借助一个队列和一个列表来实现。

def bfs(node, last_node):
        """
        广度优先搜索 此处主要用队列处理
        :param node: 初始节点
        :param last_node: 目标节点
        :return:
        """
        operate_queue = []
        finished_queue = []
        operate_queue.append(node)
        while True:
            print('operated number:{}'.format(len(operate_queue)))
            if not operate_queue:
                return False, None
            queue_first_node = operate_queue.pop(0)
            finished_queue.append(queue_first_node)
            for direction in directions:
                has_result, next_node = queue_first_node.move_0(direction)
                if has_result and next_node not in finished_queue:
                    operate_queue.append(next_node)
                    if next_node == last_node:
                        return True, next_node

DFS

深度优先搜索算法，需要借助一个栈和一个列表来实现。

 def dfs(node, last_node):
        """
        深度优先搜索 此处主要用栈处理
        :param node: 初始节点
        :param last_node: 目标节点
        :return:
        """
        operate_stack = []
        finished_queue = []
        operate_stack.append(node)
        while True:
            print('operated number:{}'.format(len(operate_stack)))
            if not operate_stack:
                return False, None
            stack_top_node = operate_stack.pop()
            finished_queue.append(stack_top_node)
            for direction in directions:
                has_result, next_node = stack_top_node.move_0(direction)
                if has_result and next_node not in finished_queue:
                    operate_stack.append(next_node)
                    if next_node == last_node:
                        return True, next_node

ID-DFS

迭代加深的深度优先搜索算法，需要借助一个栈和两个列表来实现

def id_dfs(node, last_node, k=10):
        """
        迭代加深的深度优先算法
        :param node: 初始节点
        :param last_node: 目标节点
        :param k: 预定义的k层深度
        :return:
        """
        # 待处理的节点放进栈中
        operate_stack = []
        # 已遍历的节点放进完成队列
        finished_queue = []
        # 因大于k层放入临时列表
        tmp = []
        operate_stack.append(node)
        while True:
            print('operated number:{}'.format(len(operate_stack)))
            if not operate_stack:
                if tmp:
                    operate_stack = tmp
                    tmp = []
                    k = k + 1
                else:
                    return False, None
            stack_top_node = operate_stack.pop()
            print("First judge depth :{},k:{}".format(stack_top_node.depth, k))
            if stack_top_node.depth < k:
                finished_queue.append(stack_top_node)
                for direction in directions:
                    has_result, next_node = stack_top_node.move_0(direction)
                    if has_result and next_node not in finished_queue:
                        print("Second judge depth :{},k:{}".format(next_node.depth, k))
                        if next_node.depth <= k:
                            if next_node == last_node:
                                return True, next_node
                            operate_stack.append(next_node)
                        else:
                            tmp.append(next_node)
            else:
                tmp.append(stack_top_node)

完整代码

import numpy as np
from copy import deepcopy
from enum import Enum

# 代表方向上下左右
directions = ['U', 'D', 'L', 'R']


# 定义枚举类，三种算法
class Algorithm(Enum):
    BFS = 1
    DFS = 2
    ID_DFS = 3


# 定义节点
class Node:

    def __init__(self, arr, parent, depth=1):
        """
        初始化
        :param arr: 二维数组
        :param parent: 父节点
        :param depth: 深度
        """
        self.arr = arr
        self.parent = parent
        self.depth = depth

    def find_0(self):
        """
        找到0的位置
        :return: 坐标索引
        """
        index = np.argwhere(np.array(self.arr) == 0)
        return index[0][0], index[0][1]

    def move_0(self, direction):
        """
        移动0的位置
        :param direction: U D L R 上下左右
        :return: 是否可移动，移动后的节点
        """
        # 复制当前矩阵数据
        new_arr = deepcopy(self.arr)
        # 找到0的位置
        x, y = self.find_0()
        # 判断移动方向进行移动+判断边界
        if direction == 'U':
            if x == 0:
                return False, None
            else:
                new_arr[x][y] = new_arr[x - 1][y]
                new_arr[x - 1][y] = 0
        elif direction == 'D':
            if x == len(new_arr) - 1:  # 如果x在最后一行
                return False, None
            else:
                new_arr[x][y] = new_arr[x + 1][y]
                new_arr[x + 1][y] = 0
        elif direction == 'L':
            if y == 0:
                return False, None
            else:
                new_arr[x][y] = new_arr[x][y - 1]
                new_arr[x][y - 1] = 0
        elif direction == 'R':
            if y == len(new_arr) - 1:
                return False, None
            else:
                new_arr[x][y] = new_arr[x][y + 1]
                new_arr[x][y + 1] = 0
        return True, Node(arr=new_arr, parent=self, depth=self.depth + 1)

    def get_way(self):
        """
        回溯获取路径
        :return: 节点列表
        """
        way = []
        cur = self
        while cur is not None:
            way.insert(0, cur)
            cur = cur.parent
        return way

    def print_array(self):
        """
        输出矩阵
        :return:
        """
        print(np.array(self.arr))

    def __eq__(self, other):
        """
        重写eq 判断两个节点的矩阵是否相同即可
        :param other:
        :return:
        """
        return self.arr == other.arr if other else False

    def has_answer(self, last_node):
        """
        求逆序个数(除了0) 判断是否有解
        :return: 有解则为True
        """
        a = np.array(self.arr).flatten()
        b = list(a)
        b.remove(0)
        ans = 0
        for i in range(len(b)):
            for j in range(i + 1, len(b)):
                if b[i] > b[j]:
                    ans += 1

        # 若格子列数为奇数，则逆序数必须为偶数；
        # 若格子列数为偶数，且逆序数为偶数，则当前空格所在行数与初始空格所在行数的差为偶数；
        # 若格子列数为偶数，且逆序数为奇数，则当前空格所在行数与初始空格所在行数的差为奇数。

        if len(a) % 2 == 0:
            x0, y0 = self.find_0()
            x1, y1 = last_node.find_0()
            return (ans % 2 == 0 and abs(y1 - y0) % 2 == 0) or (ans % 2 != 0 and abs(y1 - y0) % 2 != 0)
        else:
            return ans % 2 == 0


# 定义解决器
class Solver:
    def __init__(self, first_node, last_node):
        """
        初始化 最初矩阵与目标矩阵
        :param first_node: 初始矩阵
        :param last_node: 目标矩阵
        """
        self.first_node = first_node
        self.last_node = last_node

    def solve(self, alg):
        """
        处理15拼图问题
        :param alg: 选取的算法
        :return:
        """
        if self.first_node.has_answer(self.last_node):
            if alg == Algorithm.BFS:
                result, node = self.bfs(self.first_node, self.last_node)
            elif alg == Algorithm.DFS:
                result, node = self.dfs(self.first_node, self.last_node)
            elif alg == Algorithm.ID_DFS:
                result, node = self.id_dfs(self.first_node, self.last_node, k=10)
            else:
                print("error~wrong algorithm")
                return
            # 输出路径
            if result:
                print("get answer as follow:")
                way = node.get_way()
                for w in way:
                    if w:
                        w.print_array()
                return
        print("no answer~")

    @staticmethod
    def id_dfs(node, last_node, k=10):
        """
        迭代加深的深度优先算法
        :param node: 初始节点
        :param last_node: 目标节点
        :param k: 预定义的k层深度
        :return:
        """
        # 待处理的节点放进栈中
        operate_stack = []
        # 已遍历的节点放进完成队列
        finished_queue = []
        # 因大于k层放入临时列表
        tmp = []
        operate_stack.append(node)
        while True:
            print('operated number:{}'.format(len(operate_stack)))
            if not operate_stack:
                if tmp:
                    operate_stack = tmp
                    tmp = []
                    k = k + 1
                else:
                    return False, None
            stack_top_node = operate_stack.pop()
            print("First judge depth :{},k:{}".format(stack_top_node.depth, k))
            if stack_top_node.depth < k:
                finished_queue.append(stack_top_node)
                for direction in directions:
                    has_result, next_node = stack_top_node.move_0(direction)
                    if has_result and next_node not in finished_queue:
                        print("Second judge depth :{},k:{}".format(next_node.depth, k))
                        if next_node.depth <= k:
                            if next_node == last_node:
                                return True, next_node
                            operate_stack.append(next_node)
                        else:
                            tmp.append(next_node)
            else:
                tmp.append(stack_top_node)

    @staticmethod
    def dfs(node, last_node):
        """
        深度优先搜索 此处主要用栈处理
        :param node: 初始节点
        :param last_node: 目标节点
        :return:
        """
        operate_stack = []
        finished_queue = []
        operate_stack.append(node)
        while True:
            print('operated number:{}'.format(len(operate_stack)))
            if not operate_stack:
                return False, None
            stack_top_node = operate_stack.pop()
            finished_queue.append(stack_top_node)
            for direction in directions:
                has_result, next_node = stack_top_node.move_0(direction)
                if has_result and next_node not in finished_queue:
                    operate_stack.append(next_node)
                    if next_node == last_node:
                        return True, next_node

    @staticmethod
    def bfs(node, last_node):
        """
        广度优先搜索 此处主要用队列处理
        :param node: 初始节点
        :param last_node: 目标节点
        :return:
        """
        operate_queue = []
        finished_queue = []
        operate_queue.append(node)
        while True:
            print('operated number:{}'.format(len(operate_queue)))
            if not operate_queue:
                return False, None
            queue_first_node = operate_queue.pop(0)
            finished_queue.append(queue_first_node)
            for direction in directions:
                has_result, next_node = queue_first_node.move_0(direction)
                if has_result and next_node not in finished_queue:
                    operate_queue.append(next_node)
                    if next_node == last_node:
                        return True, next_node


if __name__ == '__main__':
    last_arr = [[1, 2, 3, 4],
                [5, 6, 7, 8],
                [9, 10, 11, 12],
                [13, 14, 15, 0]]

    first_arr = [[3, 2, 1, 4],
                 [7, 6, 5, 8],
                 [11, 10, 9, 12],
                 [13, 15, 14, 0]]
    #
    # last_arr = [[1, 2, 3, 4],
    #             [5, 6, 7, 8],
    #             [9, 10, 11, 12],
    #             [13, 14, 15, 0]]
    #
    # first_arr =[[1, 2, 3, 4],
    #             [5, 6, 7, 8],
    #              [10, 12, 0, 14],
    #              [9, 11, 13, 15]]
    # last_arr = [[1, 2, 3],
    #             [4, 5, 6],
    #             [7, 8, 0]]
    #
    # first_arr = [[1, 3, 4],
    #              [8, 6, 5],
    #              [2, 7, 0]]

    # last_arr = [[1, 2],
    #             [3, 0]]
    #
    # first_arr = [[0, 1],
    #              [3, 2]]

    solver = Solver(Node(arr=first_arr, parent=None), Node(arr=last_arr, parent=None))
    solver.solve(Algorithm.ID_DFS)