当我还是个孩子的时候，我经常玩 Ubongo 棋盘游戏，最近我发现了 Pentomino 拼图，我想用 python 为它创建一个自定义解算器。这是我得到的：
import datetime
def solve(height, width, pieces):
sorted_pieces = sort_pieces_by_length(pieces)
board = [['' for _ in range(width)] for _ in range(height)]
result = []
counter = 0
def is_valid_placement(piece, x, y):
first_coord = piece[0]
if not (0 <= x < width and 0 <= y < height) or board[y][x] != '':
return False
for px, py in piece[1:]:
nx, ny = x + px - first_coord[0], y + py - first_coord[1]
if not (0 <= nx < width and 0 <= ny < height) or board[ny][nx] != '':
return False
return True
def place_piece(piece, x, y, char):
first_coord = piece[0]
board[y][x] = char
for px, py in piece[1:]:
nx, ny = x + px - first_coord[0], y + py - first_coord[1]
board[ny][nx] = char
def remove_piece(piece, x, y):
first_coord = piece[0]
board[y][x] = ''
for px, py in piece[1:]:
nx, ny = x + px - first_coord[0], y + py - first_coord[1]
board[ny][nx] = ''
def find_smallest_area():
visited = set()
smallest_area = height * width
occupied_tiles = 0
for y in range(height):
for x in range(width):
if board[y][x] != '':
occupied_tiles += 1
def bfs(start_x, start_y):
nonlocal smallest_area
queue = [(start_x, start_y)]
area = 0
while queue:
curr_x, curr_y = queue.pop(0)
if (curr_x, curr_y) in visited or not (0 <= curr_x < width and 0 <= curr_y < height) or board[curr_y][curr_x] != '':
continue
visited.add((curr_x, curr_y))
area += 1
for dir_x, dir_y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
new_x, new_y = curr_x + dir_x, curr_y + dir_y
queue.append((new_x, new_y))
smallest_area = min(smallest_area, area)
for y in range(height):
for x in range(width):
if occupied_tiles + len(visited) == height * width:
return smallest_area
if (x, y) not in visited and board[y][x] == '':
bfs(x, y)
return smallest_area
def rotateR(piece_coords):
return sorted([[y, -x] for x, y in piece_coords], key=lambda coord: (coord[0], coord[1]))
def rotateH(piece_coords):
return sorted([[-x, y] for x, y in piece_coords], key=lambda coord: (coord[0], coord[1]))
def backtrack(piece_index):
nonlocal result,counter
counter+=1
if piece_index == len(sorted_pieces):
result.append([row[:] for row in board])
return True
piece_name, piece_coords = list(sorted_pieces.items())[piece_index]
reset_coords = piece_coords
def try_place(x, y, piece_coords, placed_pieces, piece_index):
if not piece_already_placed(piece_coords, placed_pieces):
place_piece(piece_coords, x, y, piece_name)
placed_pieces.append(piece_coords)
if find_smallest_area() >= 5 and backtrack(piece_index + 1):
return True
remove_piece(piece_coords, x, y)
return False
for y in range(height):
for x in range(width):
if board[y][x] != '':
continue
placed_pieces = []
piece_coords = reset_coords
if is_valid_placement(piece_coords, x, y):
if try_place(x, y, piece_coords, placed_pieces, piece_index):
return True
for _ in range (3):
piece_coords = rotateR(piece_coords)
if is_valid_placement(piece_coords, x, y):
if try_place(x, y, piece_coords, placed_pieces, piece_index):
return True
piece_coords = reset_coords
piece_coords = rotateH(piece_coords)
if is_valid_placement(piece_coords, x, y):
if try_place(x, y, piece_coords, placed_pieces, piece_index):
return True
for _ in range (3):
piece_coords = rotateR(piece_coords)
if is_valid_placement(piece_coords, x, y):
if try_place(x, y, piece_coords, placed_pieces, piece_index):
return True
return False
start_time = datetime.datetime.now()
backtrack(0)
print("TOTAL BACKTRACKS",counter)
print("Time to find: ",(datetime.datetime.now() - start_time).total_seconds(), "sec")
return result[0]
def sort_pieces_by_length(piece_dict):
sorted_pieces = dict(sorted(piece_dict.items(), key=lambda item: len(item[1]),reverse=True))
for piece_name, piece_coords in sorted_pieces.items():
sorted_pieces[piece_name] = sorted(piece_coords, key=lambda coord: (coord[0], coord[1]))
return sorted_pieces
def piece_already_placed(new_piece, pieces):
for piece in pieces:
if are_pieces_same(new_piece, piece):
return True
return False
def are_pieces_same(piece1, piece2):
# Calculate the biases on x and y axes
piece1 = [coord.copy() for coord in piece1]
piece2 = [coord.copy() for coord in piece2]
for coord1, coord2 in zip(piece1, piece2): # move to the positive quadrant
coord1[0] += 10
coord1[1] += 10
coord2[0] += 10
coord2[1] += 10
piece1 = sorted(piece1, key=lambda coord: (coord[0], coord[1]))
piece2 = sorted(piece2, key=lambda coord: (coord[0], coord[1]))
bias_x = piece2[0][0] - piece1[0][0]
bias_y = piece2[0][1] - piece1[0][1]
# Check if all corresponding coordinates are the same with the calculated biases
for coord1, coord2 in zip(piece1, piece2):
if coord1[0] + bias_x != coord2[0] or coord1[1] + bias_y != coord2[1]:
return False
return True
print(solve(5, 12, {'F': [[0, 0], [1, 0], [1, -1], [1, 1], [2, 1]], 'W': [[0, 0], [1, 0], [1, 1], [2, 1], [2, 2]], 'V': [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2]], 'X': [[0, 0], [1, 0], [-1, 0], [0, 1], [0, -1]], 'N': [[0, 0], [0, 1], [1, 1], [1, 2], [1, 3]], 'P': [[0, 0], [0, 1], [0, 2], [1, 1], [1, 2]], 'U': [[0, 0], [0, 1], [1, 0], [2, 0], [2, 1]], 'Z': [[0, 0], [1, 0], [1, -1], [1, -2], [2, -2]], 'I': [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]], 'Y': [[0, 0], [1, 0], [2, 0], [2, 1], [3, 0]], 'T': [[0, 0], [0, 1], [0, 2], [-1, 2], [1, 2]], 'L': [[0, 0], [0, 1], [1, 0], [0, 2], [0, 3]]}))
它找到了正确的解决方案，但我想获得所有解决方案（或者至少在合理的时间内获得更多解决方案）。我尝试做一些优化，但我认为它100%仍然陷入不必要的递归分支。
它在我的电脑上 ~22 秒内找到一个解决方案。我添加了称为回溯计数器的打印，并且 23k 似乎太高了。
5×12 盒子有 1010 解（维基百科）。
当然，有一些复杂的技术可以加快速度，但是有一些琐碎的技术可以添加到我的代码中吗？
感谢您的帮助
以下是一些提高效率的想法：
对棋盘和棋子都使用位图。 Python 具有原生大整数，因此棋盘和棋子都可以用单个整数表示。可以对此类整数执行位运算（如 AND、OR、XOR）。这比逐个比较字符要快。
在搜索过程中不要旋转/翻转棋子。在预处理阶段执行此操作，以便对于每个片段，您都可以将其位置、旋转和翻转预先计算为位图列表。
不要寻找棋盘上的下一个空闲位置，而是找到被棋子覆盖的可能性最小的单元格。您可以限制您将考虑查找此“难以覆盖”单元的单元：此类单元通常位于棋盘边界旁边或已放置的棋子旁边。我们甚至可以将其限制为分析板上每行一个单元：扫描该行时的第一个空闲单元。在 5x12 棋盘的情况下，这将给出最多 5 个候选单元格的列表：对于每个候选单元格，计算可以覆盖该单元格的棋子放置数量（棋子的任何变换都将计数）。选择可能性最小的一个，因为这会限制搜索树的宽度。
寻找最小的封闭区域是相当昂贵的。实现了上一点后，您可以将其删除，因为您会发现一个无法被一块覆盖的单元格。这种负面结果通常会比小面积测试返回小于 5 的面积更早发生：在许多情况下，可用面积仍然很大，但其形状不允许一块覆盖角单元。因此回溯可以更快地发生，这是一个巨大的效率增益。
延迟将表示形式作为可打印字符串，直到获得覆盖（解决方案）：此时您可以花费一些执行时间将所选位图转换为相应的字母（“F”，“X”，“L”，。 ...）并按原样打印它们。
这是应用这些原则的代码：
def solve(height, width, pieces):
def rotate(piece):
lst = [""] * len(piece[0])
for line in piece:
for j, ch in enumerate(line):
lst[j] += ch
return tuple(reversed(lst))
def flip(piece):
return tuple(reversed(piece))
def all_transformations(piece):
transfos = [piece]
while len(transfos) < 4:
transfos.append(rotate(transfos[-1]))
transfos.extend(list(map(flip, transfos)))
return set(transfos)
def piece_to_bitmap(piece):
bitmap = 0
for line in piece:
bitmap = (bitmap << (width + 1)) | int(line, 2)
return bitmap
def create_piece_bitmaps(piece):
bitmaps = []
for rotated_piece in all_transformations(piece):
bitmap = piece_to_bitmap(rotated_piece)
# shift this bitmap accross the whole board
while bitmap < board:
if (bitmap & board) == 0: # Not overlapping a wall
bitmaps.append(bitmap)
bitmap <<= 1
return bitmaps
def get_candidates(board, piece_bitmaps):
# Consider only one cell per row: the first that is free in that row
# Then choose the one that has the least piece-bitmasks that can
# cover it.
# Then return that set of piece-bitmasks.
least_fillers = []
least = float('inf')
rowmask = (1 << (width + 1)) - 1
for _ in range(height):
bitrow = (board & rowmask) ^ rowmask # 1-bit indicates free cell
rowmask <<= width + 1 # for next iteration
if not bitrow: # this row is completely occupied
continue
cell = bitrow & -bitrow # get first (least) 1-bit (free cell)
# Check which piece-bitmasks can cover this cell
fillers = []
for key, bitmaps in piece_bitmaps.items():
for bitmap in bitmaps:
if cell & bitmap and bitmap & board == 0:
fillers.append((key, bitmap))
if len(fillers) >= least: # no improvement
break
else:
continue
break # no improvement
else: # improvement
least = len(fillers)
least_fillers = fillers
return least_fillers
def dfs(board, piece_bitmaps, moves):
if not piece_bitmaps: # all pieces were placed on the board
yield moves
for key, move in get_candidates(board, piece_bitmaps):
yield from dfs(
board | move,
{k: v for k, v in piece_bitmaps.items() if k != key},
{**moves, key: move}
)
def print_solution(solution):
cell = 1
for _ in range(height):
for _ in range(width):
key = next(key for key, bitmap in solution.items()
if cell & bitmap)
print(key, end="")
cell <<= 1
print()
cell <<= 1 # skip wall
print()
# Consider the board to be a bitmap. It starts empty, but we use
# one extra column to function as a vertical wall to separate rows
board = 1 << width # introduce width amount of zeros
for _ in range(height - 1):
board = ((board << 1) | 1) << width
# Generate bitmaps for all possible positions of all pieces on the board
piece_bitmaps = {
key: create_piece_bitmaps(piece) for key, piece in pieces.items()
}
i = 0
for solution in dfs(board, piece_bitmaps, {}):
i+=1
print(i, ":")
print_solution(solution)
solve(5, 12, {
'F': ("011",
"110",
"010"),
'W': ("100",
"110",
"011"),
'V': ("100",
"100",
"111"),
'X': ("010",
"111",
"010"),
'N': ("1100",
"0111"),
'P': ("111",
"011"),
'U': ("111",
"101"),
'Z': ("100",
"111",
"001"),
'I': ("11111", ),
'Y': ("1111",
"0100"),
'T': ("111",
"010",
"010"),
'L': ("1111",
"1000")
})
我对如何定义脚本底部的片段没有任何问题，但我发现将它们定义为小网格更直观，这也可以轻松转换为位图。
在我的基本笔记本电脑上，上述脚本在大约 5 分钟内生成了所有解决方案。在 repl.it 上大约需要 25 分钟。
输出以：
开头1 :
FFWWTTTYLLLL
VFFWWTYYYYXL
VFNNWTZZPXXX
VVVNNNZPPUXU
IIIIIZZPPUUU
2 :
FFWWTTTPLLLL
VFFWWTPPZZXL
VFNNWTPPZXXX
VVVNNNYZZUXU
IIIIIYYYYUUU
3 :
FFYYYYWWPPPN
VFFXYZZWWPPN
VFXXXZTUWUNN
VVVXZZTUUUNL
IIIIITTTLLLL
...最终以：
结束4038 :
LLYYYYFFVVVI
LZZYXFFUUUVI
LTZXXXFUWUVI
LTZZXNNWWPPI
TTTNNNWWPPPI
4039 :
LLYYYYNNNVVV
LZZYXNNWUUUV
LTZXXXWWUFUV
LTZZXWWFFFPP
TTTIIIIIFPPP
4040 :
LLIIIIIZZVVV
LYYYYFFZUUUV
LTYXFFZZUWUV
LTXXXFNNWWPP
TTTXNNNWWPPP
这还产生了简单的镜像解决方案，它们只是其他解决方案的整个板的翻转。这就是为什么此输出中的解决方案比维基百科所说的 (1010) 多四倍。
可以肯定的是，这还可以进一步优化。但如果需要更快的速度，我实际上会使用另一种编程语言，例如 C++。收获将会是巨大的。