用 python 解决 3x3 青蛙拼图
Solving a 3x3 frog puzzle with python
这是一个谜题，您的目标是将青蛙头部与内边缘的身体配对。随附的图片显示了已解决的难题。
我已经在Python中思考了如何解决这个难题。我的想法是将图块表示为 2x2 numpy 矩阵的数组，例如 [["RB", "GB"], ["BB", "GH"]]，然后循环遍历所有排列并检查青蛙是否在边缘匹配。
然而，这种方法不会考虑旋转，这可以在单个矩阵上使用 numpy.rot90() 来完成。
我不知道这是否是一个可行的解决方案，或者我是否采取了错误的方法来解决这个问题。
你的任务很有趣。我实现了我自己的解决方案，它应该非常快，因为它使用 Numba 通常将 Python 代码平均提升 50x-200x 倍。
我的算法基于 backtracking 方法，并且是非递归的（它使用堆栈）。
它查找并打印所有可能的解决方案，而不仅仅是第一个。请参阅我的答案结尾以查看控制台中的结果输出。首先打印出一些解决方案，然后以 ASCII 图形形式打印所有解决方案。
而且我的算法是通用的，这意味着你可以提供尽可能多的瓷砖，提供的瓷砖数量可以大于要覆盖的矩形（但不能少于），矩形不限于 3x3，它可以具有任意高度和宽度，宽度和高度也可能不相等。例如。您可以使用 20 个瓷砖来覆盖形状为 4x3 的矩形，这样 12 个瓷砖将用于解决方案，8 个未使用。
算法的输入数据位于test()函数内。它调用 find(l, h, w) 函数，其中 a 是所有现有图块的列表，h 和 w 是要覆盖的矩形的高度和宽度（以图块计）。
输入图块采用以下格式：每个图块应恰好有 4 个字符串元素，每个字符串元素应恰好 2 个字符，第一个字符表示颜色，r：红色，g：绿色，b：蓝色，h：棕色；第二个字符是青蛙的一面，b：底部，t：顶部（例如 'bt' 表示青蛙的蓝色顶部）。 4个元素表示瓷砖的4个面，第一：右，第二：上，第三：左，第四：下。
为了 运行 我的脚本，你必须通过命令行一次安装两个模块 python -m pip install numpy numba。
我希望感谢回溯和 Numba，我的算法可以解决很多图块的任务。
还忘了说，我的算法也可以是 运行 不是找到所有可能的解决方案，而是找到任何第一个解决方案，为了只找到第一个，只需将 True 作为 find 函数的最后一个参数，即 运行 find(l, h, w) 如果你想找到所有的解决方案和 运行 find(l, h, w, True) 如果你只想要第一个。
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 #
###########################################################################################
正如John Coleman所说，暴力破解不是一个好的策略。我尝试了一下。这有望让您开始使用迭代方法，逐步构建解决方案。
将图块表示为二元组会更容易：
- 瓷砖颜色：
'G' 绿色，'P' 紫色 - 更像蓝色，'R' 红色，'B' 棕色。
- 平铺方向：
0 青蛙向外看，1 青蛙向内看（朝向平铺的中心）。
例如，您的编码 'RB' 转换为 ('R', 0)。
所以这是前两行：
tiles = [
[('P', 0), ('P', 1), ('G', 1), ('R', 0)],
[('G', 0), ('B', 0), ('P', 1), ('R', 1)],
[('P', 0), ('R', 0), ('P', 1), ('B', 1)],
[('G', 1), ('R', 1), ('P', 0), ('B', 0)],
[('P', 1), ('R', 0), ('P', 0), ('G', 1)],
[('P', 1), ('B', 0), ('R', 0), ('G', 1)],
]
棋盘将表示为二维数组：
np.zeros((2, 3), dtype='object')`
我们将遍历图板并针对每个位置（从左到右，从上到下），通过遍历可用的图块来搜索合适的图块。放置新瓷砖时，有两个水平约束 (i)：瓷砖在左侧，(ii) 瓷砖在上方。如果上方左侧 and/or 没有磁贴，则忽略约束。两只相邻的青蛙必须颜色匹配且方向相反。
这是一个可能的实现：
for (i, j), _ in np.ndenumerate(board):
above = None if i == 0 else board[i-1, j][3] # vertical constraint
left = None if j == 0 else board[i, j-1][2] # horizontal constraint
for t, tile in enumerate(tiles):
(c_left, dir_left), (c_up, dir_up), *_ = tile
if ((not left or (left[0] == c_left and left[1] != dir_left)) and
(not above or (above[0] == c_up and above[1] != dir_up))):
board[i, j] = tile
tiles.pop(t)
注意：如果你 运行 使用随机 tiles list 它很可能会失败。您应该改进此代码，以便在找不到下一个图块（即它到达内部循环的末尾）时回溯到先前的解决方案。此外，这不会考虑图块旋转，但您可以在内部循环中轻松添加此功能！
这是一个谜题，您的目标是将青蛙头部与内边缘的身体配对。随附的图片显示了已解决的难题。
我已经在Python中思考了如何解决这个难题。我的想法是将图块表示为 2x2 numpy 矩阵的数组，例如 [["RB", "GB"], ["BB", "GH"]]，然后循环遍历所有排列并检查青蛙是否在边缘匹配。
然而，这种方法不会考虑旋转，这可以在单个矩阵上使用 numpy.rot90() 来完成。
我不知道这是否是一个可行的解决方案，或者我是否采取了错误的方法来解决这个问题。
你的任务很有趣。我实现了我自己的解决方案，它应该非常快，因为它使用 Numba 通常将 Python 代码平均提升 50x-200x 倍。
我的算法基于 backtracking 方法，并且是非递归的（它使用堆栈）。
它查找并打印所有可能的解决方案，而不仅仅是第一个。请参阅我的答案结尾以查看控制台中的结果输出。首先打印出一些解决方案，然后以 ASCII 图形形式打印所有解决方案。
而且我的算法是通用的，这意味着你可以提供尽可能多的瓷砖，提供的瓷砖数量可以大于要覆盖的矩形（但不能少于），矩形不限于 3x3，它可以具有任意高度和宽度，宽度和高度也可能不相等。例如。您可以使用 20 个瓷砖来覆盖形状为 4x3 的矩形，这样 12 个瓷砖将用于解决方案，8 个未使用。
算法的输入数据位于test()函数内。它调用 find(l, h, w) 函数，其中 a 是所有现有图块的列表，h 和 w 是要覆盖的矩形的高度和宽度（以图块计）。
输入图块采用以下格式：每个图块应恰好有 4 个字符串元素，每个字符串元素应恰好 2 个字符，第一个字符表示颜色，r：红色，g：绿色，b：蓝色，h：棕色；第二个字符是青蛙的一面，b：底部，t：顶部（例如 'bt' 表示青蛙的蓝色顶部）。 4个元素表示瓷砖的4个面，第一：右，第二：上，第三：左，第四：下。
为了 运行 我的脚本，你必须通过命令行一次安装两个模块 python -m pip install numpy numba。
我希望感谢回溯和 Numba，我的算法可以解决很多图块的任务。
还忘了说，我的算法也可以是 运行 不是找到所有可能的解决方案，而是找到任何第一个解决方案，为了只找到第一个，只需将 True 作为 find 函数的最后一个参数，即 运行 find(l, h, w) 如果你想找到所有的解决方案和 运行 find(l, h, w, True) 如果你只想要第一个。
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 #
###########################################################################################
正如John Coleman所说，暴力破解不是一个好的策略。我尝试了一下。这有望让您开始使用迭代方法，逐步构建解决方案。
将图块表示为二元组会更容易：
- 瓷砖颜色：
'G'绿色，'P'紫色 - 更像蓝色，'R'红色，'B'棕色。 - 平铺方向：
0青蛙向外看，1青蛙向内看（朝向平铺的中心）。
例如，您的编码 'RB' 转换为 ('R', 0)。
所以这是前两行：
tiles = [
[('P', 0), ('P', 1), ('G', 1), ('R', 0)],
[('G', 0), ('B', 0), ('P', 1), ('R', 1)],
[('P', 0), ('R', 0), ('P', 1), ('B', 1)],
[('G', 1), ('R', 1), ('P', 0), ('B', 0)],
[('P', 1), ('R', 0), ('P', 0), ('G', 1)],
[('P', 1), ('B', 0), ('R', 0), ('G', 1)],
]
棋盘将表示为二维数组：
np.zeros((2, 3), dtype='object')`
我们将遍历图板并针对每个位置（从左到右，从上到下），通过遍历可用的图块来搜索合适的图块。放置新瓷砖时，有两个水平约束 (i)：瓷砖在左侧，(ii) 瓷砖在上方。如果上方左侧 and/or 没有磁贴，则忽略约束。两只相邻的青蛙必须颜色匹配且方向相反。
这是一个可能的实现：
for (i, j), _ in np.ndenumerate(board):
above = None if i == 0 else board[i-1, j][3] # vertical constraint
left = None if j == 0 else board[i, j-1][2] # horizontal constraint
for t, tile in enumerate(tiles):
(c_left, dir_left), (c_up, dir_up), *_ = tile
if ((not left or (left[0] == c_left and left[1] != dir_left)) and
(not above or (above[0] == c_up and above[1] != dir_up))):
board[i, j] = tile
tiles.pop(t)
注意：如果你 运行 使用随机 tiles list 它很可能会失败。您应该改进此代码，以便在找不到下一个图块（即它到达内部循环的末尾）时回溯到先前的解决方案。此外，这不会考虑图块旋转，但您可以在内部循环中轻松添加此功能！