装箱谜题：把 12 种五格骨牌装进箱子

本章的内容

本章把 12 种五格骨牌装进形状固定的箱子，不留空隙。用 CP-SAT 时，需要的约束只有 add_exactly_one() 这一种。这是装箱类问题的共同结构：先列出候选，再让求解器在每块骨牌与每个位置各选一个。

• 用字符的二维数组表示 12 种五格骨牌

• 列出旋转、翻转之后所有可以放置的位置

• 用每块骨牌放一处、每一格属一块骨牌这两种 exactly_one 求解

from ortools.sat.python import cp_model
import numpy as np
from matplotlib import pyplot as plt
from matplotlib.cm import tab20
from matplotlib.collections import PatchCollection

12 种五格骨牌

五格骨牌是五个正方形以边相连的形状，即阶为 5 的多格骨牌；把旋转与翻转后相同的形状归为一类，恰好有 12 种。12 块共 60 格，这个数目决定了箱子的面积。

* 表示方块，空白表示不放方块的位置。

pentominos = dict(
    F=[" **",
       "** ",
       " * "],
    P=["***",
       "** "],
    I=["*****"],
    N=["**  ",
       " ***"],
    L=["****",
       "   *"],
    T=["***",
       " * ",
       " * "],
    U=["* *",
       "***"],
    V=["*  ",
       "*  ",
       "***"],
    W=["*  ",
       "** ",
       " **"],
    X=[" * ",
       "***",
       " * "],
    Y=["  * ",
       "****"],
    Z=["** ",
       " * ",
       " **"],
)

def as_array(block):
    """把字符列表变成 NumPy 的二维数组"""
    return np.array([list(row) for row in block])


def plot_pentominos(pentominos):
    """把 12 种并排画出来"""
    fig, ax = plt.subplots()
    ax.set_aspect('equal')
    rectangles = []
    for i, (name, block) in enumerate(pentominos.items()):
        r, c = np.where(block == '*')
        dx, dy = i % 4 * 6, i // 4 * 4
        for x, y in zip(c + dx, r + dy):
            rectangles.append(plt.Rectangle((x, y), 1, 1, facecolor=tab20.colors[i],
                                            edgecolor="white"))
    collection = PatchCollection(rectangles, match_original=True)
    ax.add_collection(collection)
    ax.autoscale_view()
    ax.axis('off')


pentominos_arr = {key: as_array(val) for key, val in pentominos.items()}
plot_pentominos(pentominos_arr)

pentominos_arr['W'] 是由 * 与空白组成的二维数组。

pentominos_arr['W']

array([['*', ' ', ' '],
       ['*', '*', ' '],
       [' ', '*', '*']], dtype='<U1')

箱子

箱子也用二维数组表示，1 是可以放骨牌的格，0 是原本就空着的格，而 12 块五格骨牌共 12 × 5 = 60 格，因此箱子的面积也要做成 60 格。五种箱子的形状不同，可放的格数都是 60。

board1 = np.ones((8, 8), dtype=np.uint8)   # 64 - 4 = 60 格（中央空着）
board1[3:5, 3:5] = 0
board2 = np.ones((3, 20), dtype=np.uint8)
board3 = np.ones((4, 15), dtype=np.uint8)
board4 = np.ones((5, 12), dtype=np.uint8)
board5 = np.ones((6, 10), dtype=np.uint8)

boards = [board1, board2, board3, board4, board5]
print(board1)

[[1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1]
 [1 1 1 0 0 1 1 1]
 [1 1 1 0 0 1 1 1]
 [1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1]
 [1 1 1 1 1 1 1 1]]

列出可放置的位置

每块骨牌有四种旋转、两种左右翻转，即八种朝向。把它们分别放到箱子中的每个位置，就得到全部可放置的位置。

• pentomino[:, ::step]：step=-1 时左右翻转

• np.rot90(tile, r)：旋转 90 度 r 次

• 放置的格全部为 1 时才可放置，超出箱子会引发 IndexError，这种情况跳过即可

同一个形状会重复出现，因此先放进 set，再用 sorted() 变成列表；sorted() 让位置编号固定下来，后面的字典才能按编号索引。

from itertools import product
from collections import defaultdict, namedtuple

Location = namedtuple('Location', 'pentomino cells')


def get_all_locations(pentominos, board):
    """列出 12 种骨牌所有能放的位置"""
    ymax, xmax = board.shape
    locations = set()

    for i, pentomino in enumerate(pentominos):
        for step in (1, -1):                      # 左右翻转
            flipped = pentomino[:, ::step]
            for r in range(4):                    # 旋转 90° × 4
                tile = np.rot90(flipped, r)
                locy, locx = np.where(tile == "*")
                for y, x in product(range(ymax), range(xmax)):
                    locy2 = locy + y
                    locx2 = locx + x
                    try:
                        if np.all(board[locy2, locx2] == 1):
                            cells = tuple(sorted(zip(locy2.tolist(), locx2.tolist())))
                            locations.add(Location(i, cells))
                    except IndexError:
                        pass                      # 超出了箱子
    return sorted(locations)


locations = get_all_locations(pentominos_arr.values(), boards[0])
print(len(locations), "种摆法")
for loc in locations[:5]:
    print(loc)

1568 种摆法
Location(pentomino=0, cells=((0, 0), (0, 1), (1, 1), (1, 2), (2, 1)))
Location(pentomino=0, cells=((0, 0), (1, 0), (1, 1), (1, 2), (2, 1)))
Location(pentomino=0, cells=((0, 1), (0, 2), (1, 0), (1, 1), (2, 1)))
Location(pentomino=0, cells=((0, 1), (0, 2), (1, 2), (1, 3), (2, 2)))
Location(pentomino=0, cells=((0, 1), (1, 0), (1, 1), (1, 2), (2, 0)))

求解

对 locations 的每个元素各造一个布尔变量 flag，为 True 表示把骨牌放在该处，否则不放。

约束只有 add_exactly_one()，按作用对象分成两类。

1. 每块骨牌放一处：同一块骨牌不能放两个地方

2. 每一格属一块骨牌：一格不能被两块骨牌占住，也就是所有格都被填满

不需要再写“骨牌之间不重叠”的约束：重叠会让某一格被两块骨牌选中，与第 2 条冲突。两条约束各管一侧，合起来就规定了整个摆放。

pentomino_locations 是骨牌到它可放置位置编号的字典，cell_locations 是格到包含该格的放置编号的字典。

def solve_board(board):
    """用 12 块五格骨牌把箱子装满"""
    locations = get_all_locations(pentominos_arr.values(), board)

    pentomino_locations = defaultdict(list)   # 骨牌 → 能放的位置编号
    cell_locations = defaultdict(list)        # 格子 → 包含该格子的摆法编号

    for idx, (tile_id, cells) in enumerate(locations):
        pentomino_locations[tile_id].append(idx)
        for cell in cells:
            cell_locations[cell].append(idx)

    model = cp_model.CpModel()
    flags = np.array([model.new_bool_var(f"b{i}") for i in range(len(locations))])

    # 每块骨牌 1 处，每个格子 1 块
    for d in (pentomino_locations, cell_locations):
        for index in d.values():
            model.add_exactly_one(flags[index].tolist())

    solver = cp_model.CpSolver()
    if solver.solve(model) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        raise ValueError("没有找到解")

    return [locations[i].cells for i, flag in enumerate(flags) if solver.value(flag)]


def plot_solution(solution):
    """把解出的摆放画出来"""
    h, w = np.array(solution).reshape(-1, 2).max(axis=0) + 1
    fig, ax = plt.subplots(figsize=(w * 0.25, h * 0.25))
    ax.set_aspect('equal')

    rectangles = []
    for i, block in enumerate(solution):
        for y, x in block:
            rectangles.append(plt.Rectangle((x, y), 1, 1, facecolor=tab20.colors[i],
                                            edgecolor='white'))

    collection = PatchCollection(rectangles, match_original=True)
    ax.add_collection(collection)
    ax.autoscale_view()
    ax.invert_yaxis()
    ax.axis('off')
    return fig

下面依次解出五种箱子，并画出来。

for board in boards:
    solution = solve_board(board)
    plot_solution(solution)

验算

检查解出的摆放是否真的满足全部条件，验算只读结果，不依赖求解器的内部状态。

def check_solution(board, solution):
    """每块骨牌都是 5 格，既没有重叠也没有空隙"""
    filled = {}
    for i, block in enumerate(solution):
        if len(block) != 5:
            return False, "有骨牌不是 5 格"
        for y, x in block:
            if (y, x) in filled:
                return False, f"格子 {(y, x)} 重叠了"
            filled[y, x] = i

    target = {(y, x) for y, x in zip(*np.where(board == 1))}
    if set(filled) != target:
        return False, "还有没填满的格子"
    return True, f"{len(solution)} 块骨牌把所有格子都填满了"


for board in boards:
    print(check_solution(board, solve_board(board)))

(True, '12 块骨牌把所有格子都填满了')

(True, '12 块骨牌把所有格子都填满了')

(True, '12 块骨牌把所有格子都填满了')

(True, '12 块骨牌把所有格子都填满了')

(True, '12 块骨牌把所有格子都填满了')

小结

• 五格骨牌的摆放，只需要列出可放置的位置，再加上 add_exactly_one 的选择就能解出

• 旋转与反转由 np.rot90() 与 pentomino[:, ::-1] 生成，共八种

• 重复的摆法先用 set 归并，再变成列表

• 约束只有两种，骨牌一侧与格一侧都放上 exactly_one，就既没有空隙也没有重叠