python - 用 python 解决一个 3x3 Frog 谜题

Question

这是一个谜题，您的目标是将 Frog 头与内边缘的 body 配对。随附的图片显示已解决的难题。

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

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

Answer 1

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

我的算法基于 backtracking方法，并且是非递归的(它使用堆栈)。

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

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

算法的输入数据位于test()函数内部。它调用 find(l, h, w) 函数，其中 a 是所有现有图 block 的列表，h 和 w 是要覆盖的矩形的高度和宽度(以图 block 计)。

输入图 block 的格式如下:每个图 block 应该正好有 4 个字符串元素，每个字符串元素应该正好有 2 个字符，第一个字符表示颜色，r:红色，g:绿色，b:蓝色，h:棕色；第二个字符是 Frog 的侧面，b:底部，t:顶部(例如 'bt' 表示 Frog 的蓝色顶部)。 4 个元素表示 tile 的 4 个边，第一个:右，第二个:上，第三个:左，第四个:下。

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

我希望感谢回溯和 Numba，我的算法可以解决非常多数量的图 block 的任务。

另外忘了提一下，我的算法也可以运行以查找不是所有可能的解决方案，而是查找任何第一个解决方案，以便仅找到第一个，只需将 True 作为 find 函数的最后一个参数，即如果您想找到所有解决方案，请运行 find(l, h, w)，如果您只想要第一个解决方案，请运行 find(l, h, w, True)。

Try following code online!

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   #
###########################################################################################