问题描述

在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1 ~ 5 来表示，以及一块空缺用 0 来表示。

一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换。

最终当板 board 的结果是 [[1, 2, 3], [4, 5, 0]] 谜板被解开。

给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。

示例：

输入：board = [[1, 2, 3], [4, 0, 5]]
输出：1
解释：交换 0 和 5 ，1 步完成

输入：board = [[1, 2, 3], [5, 4, 0]]
输出：-1
解释：没有办法完成谜板

输入：board = [[4, 1, 2],[5, 0, 3]]
输出：5
解释：
完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4, 1, 2], [5, 0, 3]]
移动 1 次: [[4, 1, 2], [0, 5, 3]]
移动 2 次: [[0, 1, 2], [4, 5, 3]]
移动 3 次: [[1, 0, 2], [4, 5, 3]]
移动 4 次: [[1, 2, 0], [4, 5, 3]]
移动 5 次: [[1, 2, 3], [4, 5, 0]]

输入：board = [[3, 2, 4], [1, 5, 0]]
输出：14

提示：

board 是一个如上所述的 2 x 3 的数组。

board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/sliding-puzzle

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

带有剪枝函数的广度优先遍历

Python 实现

class Solution(object):
    def slidingPuzzle(self, board):
        """
        :type board: List[List[int]]
        :rtype: int
        """
        duplicate = set()
        board = "".join(map(str, (board[0] + board[1])))
        queue = [(0, board)]

        while queue:
            count, node = queue.pop(0)
            if node == "123450":
                return count
            for child in self.get_children(node):
                if child in duplicate:
                    continue
                duplicate.add(child)
                queue.append((count + 1, child))
        else:
            return -1

    def get_children(self, board):
        i = 0
        for i, ch in enumerate(board):
            if ch == '0':
                break
        else:
            raise RuntimeError("0 is not found")

        # up
        if i >= 3:
            yield board[:i - 3] + '0' + board[i - 2: 3] + board[3: i] + board[i - 3] + board[i + 1:]
        # down
        if i <= 2:
            yield board[:i] + board[i + 3] + board[i + 1: 3] + board[3: i + 3] + '0' + board[i + 4:]
        # left
        if i != 2 and i != 5:
            yield board[:i] + board[i + 1] + board[i] + board[i + 2:]
        # right
        if i != 0 and i != 3:
            yield board[:i - 1] + board[i] + board[i - 1] + board[i + 1:]