用Python的OR-Tools搞定日历拼图一个线性规划小白的保姆级实战日历拼图是一种经典的益智游戏玩家需要将不同形状的拼图块完美地放入一个带有日期标记的底板中。对于技术爱好者来说这不仅是一个消遣更是一个绝佳的编程挑战。本文将带你用Python的OR-Tools库从零开始构建一个能够自动解决日历拼图问题的程序。即使你之前从未接触过线性规划或约束规划也能跟着这个保姆级教程一步步实现。1. 环境准备与工具安装在开始之前我们需要准备好开发环境。推荐使用Python 3.8或更高版本并创建一个干净的虚拟环境python -m venv puzzle_env source puzzle_env/bin/activate # Linux/macOS # 或者 puzzle_env\Scripts\activate # Windows接下来安装必要的依赖库pip install ortools numpy matplotlibOR-Tools是Google开发的一个强大的优化工具包它提供了多种求解器包括我们要用到的CP-SAT求解器。CP-SAT特别适合解决这类离散优化问题它能高效处理整数变量和逻辑约束。提示如果你在使用Jupyter Notebook可以在代码单元格开头添加%matplotlib inline来直接在笔记本中显示图形。2. 理解问题与数据建模日历拼图的核心挑战在于如何将10块不同形状的拼图块每块由4-5个小方块组成完美地放入7x7的底板中。每个拼图块可以有多种旋转和翻转的形态这大大增加了问题的复杂性。我们需要建立一个数学模型来表示这个问题。关键思路是每个拼图块(p)有多个可能的形态(s)每个形态下拼图块的每个小方块(n)都有特定的位置(r,c)我们需要确保每个底板位置最多被一个小方块占据每个拼图块的所有小方块必须属于同一个形态拼图块之间不能重叠让我们先定义一些基础数据结构import numpy as np from ortools.sat.python import cp_model # 拼图块定义 - 每个拼图块的基本形状原始形态 pieces { 0: [(0,0), (1,0), (2,0), (2,1), (3,0)], # 举例L形 1: [(0,0), (0,1), (1,0), (1,1)], # 方形 # ...其他8个拼图块的定义 } # 底板定义 - 7x7网格标记哪些位置是可用的 board np.ones((7,7), dtypebool) # 设置不可用的位置如日历的特殊形状 board[0, 0] False # 举例3. 构建0-1决策变量CP-SAT求解器要求我们将问题转化为一组决策变量和约束条件。对于这个问题我们需要创建一个5维的0-1变量矩阵model cp_model.CpModel() # 创建决策变量 # work[p,n,s,r,c]表示拼图p的第n个小方块在形态s下是否位于(r,c) work {} for p in pieces: # 遍历所有拼图块 for n, _ in enumerate(pieces[p]): # 遍历拼图块的所有小方块 for s in range(8): # 8种可能的形态 for r in range(7): # 7行 for c in range(7): # 7列 if board[r, c]: # 只有底板可用的位置才创建变量 work[(p, n, s, r, c)] model.NewBoolVar(fwork_p{p}_n{n}_s{s}_r{r}_c{c})这个数据结构看起来复杂但它精确地表示了所有可能的拼图放置方式。接下来我们需要添加约束条件来确保解决方案的有效性。4. 添加约束条件4.1 每个位置最多一个小方块底板上的每个位置最多只能被一个小方块占据for r in range(7): for c in range(7): if board[r, c]: # 该位置所有拼图块、小方块、形态的总和 ≤ 1 model.AddAtMostOne( work[(p, n, s, r, c)] for p in pieces for n in range(len(pieces[p])) for s in range(8) if (p, n, s, r, c) in work )4.2 每个小方块必须且只能属于一个形态和位置对于每个拼图块的每个小方块它必须恰好出现在一个形态的一个位置上for p in pieces: for n in range(len(pieces[p])): # 该小方块在所有形态和位置上的总和 1 model.AddExactlyOne( work[(p, n, s, r, c)] for s in range(8) for r in range(7) for c in range(7) if (p, n, s, r, c) in work )4.3 拼图块的所有小方块必须属于同一形态我们需要确保一个拼图块的所有小方块都使用相同的形态for p in pieces: for s in range(8): # 创建一个辅助变量表示拼图p是否使用形态s piece_used model.NewBoolVar(fpiece{p}_used_s{s}) # 如果任何小方块使用了形态s则piece_used必须为真 for n in range(len(pieces[p])): for r in range(7): for c in range(7): if (p, n, s, r, c) in work: model.AddImplication( work[(p, n, s, r, c)], piece_used ) # 如果piece_used为真则所有小方块必须使用形态s for n in range(len(pieces[p])): for r in range(7): for c in range(7): if (p, n, s, r, c) in work: model.AddImplication( piece_used, work[(p, n, s, r, c)] ).OnlyEnforceIf(piece_used)5. 处理拼图形状和形态变换拼图块可以有多种形态旋转和翻转。我们需要确保在特定形态下拼图块的小方块保持正确的相对位置关系。首先我们定义一个函数来生成所有可能的形态def generate_transformations(original_shape): transformations [] # 原始形态 transformations.append(original_shape) # 旋转90度 rotated90 [(-y, x) for x, y in original_shape] transformations.append(rotated90) # 旋转180度 rotated180 [(-x, -y) for x, y in original_shape] transformations.append(rotated180) # 旋转270度 rotated270 [(y, -x) for x, y in original_shape] transformations.append(rotated270) # 水平翻转 flipped [(-x, y) for x, y in original_shape] transformations.append(flipped) # 垂直翻转 flipped_vert [(x, -y) for x, y in original_shape] transformations.append(flipped_vert) # 对角线翻转 flipped_diag [(y, x) for x, y in original_shape] transformations.append(flipped_diag) # 反对角线翻转 flipped_anti_diag [(-y, -x) for x, y in original_shape] transformations.append(flipped_anti_diag) return transformations然后我们需要添加约束来确保拼图块在特定形态下保持正确的形状# 预先生成所有拼图块的所有形态 piece_transformations { p: generate_transformations(pieces[p]) for p in pieces } for p in pieces: for s, transformed_shape in enumerate(piece_transformations[p]): # 对于拼图块p的形态s确保小方块的相对位置正确 base_x, base_y transformed_shape[0] # 第一个小方块作为基准 for n, (dx, dy) in enumerate(transformed_shape): if n 0: # 基准小方块不需要约束 continue for r in range(7): for c in range(7): # 计算相对位置 new_r r dx - base_x new_c c dy - base_y # 如果新位置在底板范围内 if 0 new_r 7 and 0 new_c 7 and board[new_r, new_c]: # 如果基准小方块在(r,c)则第n个小方块必须在(new_r, new_c) model.AddImplication( work[(p, 0, s, r, c)], work[(p, n, s, new_r, new_c)] ) else: # 如果相对位置超出边界则基准小方块不能在(r,c) model.Add(work[(p, 0, s, r, c)] 0)6. 求解与结果可视化现在我们已经建立了完整的模型可以开始求解了solver cp_model.CpSolver() status solver.Solve(model) if status cp_model.OPTIMAL or status cp_model.FEASIBLE: print(找到解决方案) # 创建一个空底板来显示结果 solution np.zeros((7,7), dtypeint) # 收集所有被放置的小方块 for (p, n, s, r, c), var in work.items(): if solver.Value(var): solution[r, c] p 1 # 用不同数字表示不同拼图块 # 可视化结果 import matplotlib.pyplot as plt plt.figure(figsize(8,8)) plt.imshow(solution, cmaptab20) for r in range(7): for c in range(7): if board[r, c]: plt.text(c, r, str(solution[r, c]), hacenter, vacenter, colorwhite) plt.title(日历拼图解决方案) plt.axis(off) plt.show() else: print(未找到解决方案)注意对于复杂的拼图配置求解可能需要几分钟时间。CP-SAT求解器会尝试各种可能的组合来找到满足所有约束的解。7. 性能优化与高级技巧随着你对OR-Tools的熟悉可以考虑以下优化技巧对称性消除某些拼图块的形态可能是等价的可以添加约束减少重复计算。# 示例消除拼图块0的某些对称形态 for s in [2, 5, 7]: # 假设这些形态与其他形态等价 for n in range(len(pieces[0])): for r in range(7): for c in range(7): if (0, n, s, r, c) in work: model.Add(work[(0, n, s, r, c)] 0)启发式搜索可以指导求解器优先尝试某些拼图块或位置。# 设置搜索启发式 - 优先尝试较大的拼图块 for p in sorted(pieces, keylambda x: -len(pieces[x])): for n in range(len(pieces[p])): for s in range(8): for r in range(7): for c in range(7): if (p, n, s, r, c) in work: solver.AddHint(work[(p, n, s, r, c)], 1)并行求解OR-Tools支持多线程求解。solver.parameters.num_search_workers 4 # 使用4个线程时间限制对于复杂问题可以设置时间限制。solver.parameters.max_time_in_seconds 60.0 # 限制为60秒在实际项目中我发现将拼图块按大小排序并优先放置较大的拼图块通常能显著提高求解速度。另外合理设置搜索启发式参数也能带来意想不到的效果。