15谜题可解性判定

What · 是什么

15-puzzle(数字滑块谜题, N-puzzle) 是 4x4 方盘放 15 个编号方块加一个空格的滑块游戏，每步将空格与相邻方块交换，目标按序排列。求解可判定性问题：给定一个盘面能否还原？判定法则：奇数阶(m 为奇数)盘面可解 ⇔ 逆序对数为偶数；偶数阶(m 为偶数)盘面可解 ⇔ 逆序对奇偶性与(空格所在行距底行的距离)奇偶性相同。最优解为 NP 困难，可解性判定与搜索(如 A*)是两个不同层面的问题。

Why · 为什么

How · 实现

伪代码

# 判定 m 行 n 列 N-puzzle 是否可解
board = 二维数组(空格=0)
seq = 行主序读入所有非零数字
inv = 数 seq 逆序对数
if n 为奇数:          # 列数(空格所在行横向移动不改变奇偶)
  return inv % 2 == 0
else:                 # 偶数阶
  blank_row = 空格所在行(0-index, 距底= m-1-blank_row)
  return (inv + (m - 1 - blank_row)) % 2 == 0

Python 实现

def inversions(seq):
    """归并排序求逆序对数。"""
    seq = list(seq)
    n = len(seq)
    tmp = [0] * n

    def merge_sort(l, r):
        if r - l <= 1:
            return 0
        mid = (l + r) // 2
        cnt = merge_sort(l, mid) + merge_sort(mid, r)
        i, j, k = l, mid, l
        while i < mid and j < r:
            if seq[i] <= seq[j]:
                tmp[k] = seq[i]
                i += 1
            else:
                tmp[k] = seq[j]
                cnt += mid - i
                j += 1
            k += 1
        while i < mid:
            tmp[k] = seq[i]
            i += 1
            k += 1
        while j < r:
            tmp[k] = seq[j]
            j += 1
            k += 1
        seq[l:r] = tmp[l:r]
        return cnt

    return merge_sort(0, n)


def is_solvable(board):
    """判断 m 行 n 列 N-puzzle 是否可解。
    board: list[list[int]], 0 表示空格。
    """
    m = len(board)
    n = len(board[0])
    seq = []
    blank_row = -1
    for i in range(m):
        for j in range(n):
            if board[i][j] == 0:
                blank_row = i
            else:
                seq.append(board[i][j])
    inv = inversions(seq)
    if n % 2 == 1:
        return inv % 2 == 0
    # 偶数阶: 逆序对奇偶性 与 空格距底行距离奇偶性 相同
    dist_from_bottom = m - 1 - blank_row
    return (inv + dist_from_bottom) % 2 == 0


def solved_board(m, n):
    """生成目标盘面(空格在右下)。"""
    b = [[(i * n + j + 1) % (m * n) for j in range(n)] for i in range(m)]
    return b


if __name__ == '__main__':
    # 目标盘面必可解
    assert is_solvable(solved_board(4, 4)) is True
    assert is_solvable(solved_board(3, 3)) is True

    # 3x3 已知可解盘
    ok33 = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
    assert is_solvable(ok33) is True
    # 3x3 已知不可解盘(交换1和2)
    bad33 = [[2, 1, 3], [4, 5, 6], [7, 8, 0]]
    assert is_solvable(bad33) is False

    # 4x4 目标盘
    ok44 = solved_board(4, 4)
    assert is_solvable(ok44) is True
    # 4x4 交换两个非空格数字应不可解(逆序奇偶变化)
    bad44 = [row[:] for row in ok44]
    bad44[0][0], bad44[0][1] = bad44[0][1], bad44[0][0]
    assert is_solvable(bad44) is False

    # 空格位置对偶数阶有影响: 目标盘移动空格到第0行
    moved = [row[:] for row in ok44]
    # 把空格从(3,3)移到(0,0), 其余数字循环移位保持合法
    vals = [v for row in ok44 for v in row if v != 0]
    it = iter(vals)
    newb = [[0] * 4 for _ in range(4)]
    for i in range(4):
        for j in range(4):
            if (i, j) == (0, 0):
                continue
            newb[i][j] = next(it)
    # 这种整盘平移不改变逆序数, 但空格行距变了 -> 奇偶可能改变
    print('3x3 ok=', is_solvable(ok33), ' bad=', is_solvable(bad33))
    print('4x4 ok=', is_solvable(ok44), ' bad=', is_solvable(bad44))
    print('4x4 moved blank to top-left:', is_solvable(newb))
    print('All 15-puzzle solvability tests passed!')

易错点

• 逆序对计算要跳过空格(0), 把空格算进去会得到错误奇偶
• 奇偶阶判据不同: 奇数阶只看逆序对, 偶数阶要加空格行距(距底行)奇偶
• 行主序读盘面: 空格不参与逆序, 但位置要单独记录
• 把空格放到正确位置不算入逆序(空格不是数字), 读入时 if val != 0 才 append
• 判可解≠可解路径, 别在判定题里用 BFS 全状态(4x4 状态空间 16!/2 巨大)

例题

信源

• OI Wiki✓ https://oi-wiki.org/misc/15-puzzle/
• OI Wiki✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/misc/15-puzzle.md
• CP-Algorithms✓ https://cp-algorithms.com/others/15-puzzle.html
• web✓ https://en.wikipedia.org/wiki/15_puzzle