用 python 解决 3x3 青蛙拼图

Question

这是一个谜题，您的目标是将青蛙头与内边缘的身体配对。包含的图片显示了已解决的难题。

我已经想过如何在 Python 中解决这个难题。我的想法是将瓷砖表示为 2x2 numpy 矩阵数组，[["RB", "GB"], ["BB", "GH"]]例如，然后循环遍历所有排列并检查青蛙是否在边缘匹配。然而，这种方法不会考虑旋转，这可以通过 numpy.rot90() 在单个矩阵上完成。

我不知道这是否是一个可行的解决方案，或者我是否采取了错误的方法来解决这个问题。

Answer 1

你有一个非常有趣的任务。我实现了我自己的解决方案，它应该非常快，因为它使用Numba，通常将 Python 代码平均提升 50 到 200 倍。

我的算法基于回溯方法，并且是非递归的（它使用堆栈）。

它查找并打印所有可能的解决方案，而不仅仅是第一个。请参阅我的答案结尾以查看控制台中的结果输出。打印第一个解决方案数量，然后以 ASCII 图形形式打印所有解决方案。

另外我的算法是通用的，这意味着您可以提供尽可能多的瓷砖，提供的瓷砖数量可以大于要覆盖的矩形（但不能更少），矩形不限于 3x3，它可以具有任意高度和宽度，宽度和高度也可能不相等。例如，您可以使用 20 个瓷砖来覆盖形状为 4x3 的矩形，这样在解决方案中将使用 12 个瓷砖而 8 个未使用。

算法的输入数据位于test()函数内部。它调用find(l, h, w)函数 wherea是所有现有瓷砖的列表，h以及w要覆盖的矩形的高度和宽度（以瓷砖计）。

输入图块采用下一种格式：每个图块应正好有 4 个字符串元素，每个字符串元素应正好有 2 个字符，第一个字符表示颜色，r：红色，g：绿色，b：蓝色，h：棕色；第二个字符是青蛙的侧面，b：底部，t：顶部（例如'bt'表示青蛙的蓝色顶部）。4 个元素表示 tile 的 4 个边，第一：右侧，第二：顶部，第三：左侧，第四：底部。

为了运行我的脚本，您必须仅通过命令行一次安装两个模块python -m pip install numpy numba。

我希望由于回溯和 Numba，我的算法可以解决非常多图块的任务。

还忘了提，我的算法也可以运行来找到不是所有可能的解决方案，而是任何第一个解决方案，为了只找到第一个，只是True作为 find 函数的最后一个参数传递，即运行find(l, h, w)如果你想找到所有解决方案并运行find(l, h, w, True)if你只想要第一个。

在线尝试以下代码！

import numpy as np, numba

@numba.njit(cache = True)
def nfind(a, h, w, first):
    hw = h * w
    n = a.shape[0]
    taken = np.zeros((n,), dtype = np.bool_)
    rot = np.zeros((h, w), dtype = np.int32)
    idx = np.zeros((h, w), dtype = np.int32)
    stack = np.zeros((hw, 2), dtype = np.int32)
    ans = np.zeros((0, h, w, 2), dtype = np.int32)
    i, r, istack = 0, 0, 0
    while True:
        y, x = istack // w, istack % w
        if i >= n or istack >= hw:
            if istack >= hw:
                cans = np.zeros((1, h, w, 2), dtype = np.int32)
                for i0 in range(h):
                    for i1 in range(w):
                        cans[0, i0, i1] = idx[i0, i1], rot[i0, i1]
                ans = np.concatenate((ans, cans))
                if first:
                    return ans
            istack -= 1
            if istack < 0:
                return ans
            i, r = stack[istack]
            taken[i] = False
            i, r = i + (r + 1) // 4, (r + 1) % 4
        elif (
            not taken[i] and
            (y == 0 or a[idx[y - 1, x], (rot[y - 1, x] + 3) % 4] == a[i, (r + 1) % 4] ^ 1) and
            (x == 0 or a[idx[y, x - 1], (rot[y, x - 1] + 0) % 4] == a[i, (r + 2) % 4] ^ 1)
        ):
            stack[istack] = i, r
            taken[i] = True
            idx[y, x] = i
            rot[y, x] = r
            istack += 1
            i, r = 0, 0
        else:
            i, r = i + (r + 1) // 4, (r + 1) % 4

def find(l, h, w, first = False):
    a = np.zeros((len(l), 4), dtype = np.uint8)
    col, sid = 'rgbh', 'bt'
    for i, x in enumerate(l):
        assert len(x) == 4, x
        for j, y in enumerate(x):
            assert len(y) == 2, y
            a[i, j] = (col.index(y[0]) << 1) | sid.index(y[1])
    r = nfind(a, h, w, first)
    print('Number of solutions: ', r.shape[0], '\n')
    s = []
    for i in range(r.shape[0]):
        ss = []
        for y in range(h):
            sss = []
            for x in range(w):
                e = []
                for j in range(4):
                    e += [l[r[i, y, x, 0]][(r[i, y, x, 1] + j) % 4]]
                sss += [[
                    f'  {e[1]}  ',
                    f'{e[2]}  {e[0]}',
                    f'  {e[3]}  ',
                ]]
            ss += [sss]
        s += [ss]
    bl = 4
    for i in range(0, len(s), bl):
        lines = [''] * (len(s[0]) * 4 - 1)
        for ie, e in enumerate(s[i : i + bl]):
            for y in range(len(s[0])):
                for x in range(len(s[0][0])):
                    for il, l in enumerate(e[y][x]):
                        lines[y * 4 + il] += l + ('|', ' # ')[x + 1 >= len(s[0][0])]
                    if y + 1 < len(s[0]):
                        lines[y * 4 + 3] += '-' * (7, 6)[x + 1 >= len(s[0][0])]
                        if x + 1 >= len(s[0][0]):
                            lines[y * 4 + 3] += ' # '
        lines += ['#' * (len(lines[0]) - 1)]
        for l in lines:
            print(l)
            
def test():
    find([
        ['gt', 'bt', 'bb', 'rb'], ['bt', 'hb', 'gb', 'rt'], ['bt', 'rb', 'bb', 'ht'],
        ['bb', 'rt', 'gt', 'hb'], ['bb', 'rb', 'bt', 'gt'], ['rb', 'hb', 'bt', 'gt'],
        ['rb', 'ht', 'gt', 'hb'], ['hb', 'gb', 'rt', 'gt'], ['rb', 'gb', 'ht', 'bt'],
    ], 3, 3)

if __name__ == '__main__':
    test()

控制台输出：

Number of solutions:  8

  bt  |  hb  |  rb   #   gt  |  gb  |  rb   #   bt  |  rb  |  rb   #   gt  |  bt  |  rb   #
bb  gt|gb  bt|bb  bt # bt  rb|rt  hb|ht  hb # rb  ht|hb  gt|gb  bt # hb  rt|rb  ht|hb  gt #
  rb  |  rt  |  ht   #   bb  |  gt  |  gt   #   bb  |  bt  |  ht   #   bb  |  bb  |  bt   #
-------------------- # -------------------- # -------------------- # -------------------- #
  rt  |  rb  |  hb   #   bt  |  gb  |  gb   #   bt  |  bb  |  hb   #   bt  |  bt  |  bb   #
gt  bb|bt  bb|bt  rb # gt  rb|rt  hb|ht  rb # hb  rt|rb  gt|gb  gt # rb  ht|hb  rt|rb  gt #
  hb  |  gt  |  gt   #   bb  |  bt  |  bt   #   gb  |  bt  |  rt   #   gb  |  gb  |  bt   #
-------------------- # -------------------- # -------------------- # -------------------- #
  ht  |  gb  |  gb   #   bt  |  bb  |  bb   #   gt  |  bb  |  rb   #   gt  |  gt  |  bb   #
gt  rb|rt  hb|ht  rb # gt  hb|ht  rb|rt  hb # bt  rb|rt  hb|ht  hb # hb  ht|hb  rt|rb  bt #
  hb  |  gt  |  bt   #   rb  |  bt  |  gt   #   bb  |  gt  |  gt   #   rb  |  gb  |  gt   #
###########################################################################################
  gt  |  gt  |  bt   #   gt  |  gt  |  bb   #   hb  |  rb  |  hb   #   bt  |  gt  |  hb   #
rb  bt|bb  bt|bb  gt # hb  ht|hb  rt|rb  bt # rb  gt|gb  bt|bb  gt # rb  ht|hb  rt|rb  gt #
  hb  |  rb  |  rb   #   rb  |  bb  |  gt   #   ht  |  ht  |  rt   #   gb  |  gb  |  ht   #
-------------------- # -------------------- # -------------------- # -------------------- #
  ht  |  rt  |  rt   #   rt  |  bt  |  gb   #   hb  |  hb  |  rb   #   gt  |  gt  |  hb   #
bt  bb|bt  gb|gt  gb # gt  gb|gt  rb|rt  hb # gb  gt|gb  bt|bb  bt # rb  bt|bb  bt|bb  gt #
  rb  |  hb  |  hb   #   hb  |  bb  |  bt   #   rt  |  rt  |  ht   #   hb  |  rb  |  rt   #
-------------------- # -------------------- # -------------------- # -------------------- #
  rt  |  ht  |  ht   #   ht  |  bt  |  bb   #   rb  |  rb  |  hb   #   ht  |  rt  |  rb   #
gt  bb|bt  gb|gt  rb # bt  gb|gt  hb|ht  rb # gt  bb|bt  bb|bt  rb # bt  bb|bt  gb|gt  bb #
  hb  |  rb  |  hb   #   rb  |  rb  |  bt   #   bt  |  gt  |  gt   #   rb  |  hb  |  bt   #
###########################################################################################