用Python的OR-Tools搞定日历拼图：保姆级建模与求解教程（附完整代码）
用Python的OR-Tools搞定日历拼图：保姆级建模与求解教程（附完整代码）
日历拼图是一种将特定形状的拼图块填入带有日期标记的底板中的智力游戏。这类问题看似简单，实则涉及复杂的空间排列组合，非常适合用数学建模和优化求解的方法来解决。本文将带你从零开始，使用Google的OR-Tools工具包中的CP-SAT求解器，一步步构建并求解日历拼图问题。
1. 环境准备与问题分析
1.1 安装必要的Python库
首先确保你的Python环境已经安装了以下库：
pip install ortools numpy matplotlibOR-Tools是Google开发的开源优化工具包，其中CP-SAT求解器特别适合解决这类组合优化问题。我们将使用它来建模和求解拼图问题。
1.2 理解日历拼图的基本规则
日历拼图通常由以下几部分组成：
- 一个7x7的底板，其中包含月份、星期和日期的标记
- 10块不同形状的拼图块，每块由4-5个小方块组成
- 拼图块可以旋转和翻转，产生不同的形态
我们的目标是将这些拼图块填入底板，覆盖所有非日期标记的位置，同时不重叠且完全匹配底板形状。
2. 建立数学模型
2.1 定义决策变量
我们需要为每个拼图块的每个可能的放置方式创建一个二元变量：
from ortools.sat.python import cp_model model = cp_model.CpModel() # 定义拼图块数量、形态数、行列数 num_pieces = 10 num_states = 8 # 原始形态+7种旋转/翻转 rows = 7 cols = 7 # 创建决策变量：work[p,s,r,c]表示拼图块p在形态s下是否以(r,c)为基准点放置 work = {} for p in range(num_pieces): for s in range(num_states): for r in range(rows): for c in range(cols): work[p,s,r,c] = model.NewBoolVar(f'work_{p}_{s}_{r}_{c}')2.2 设置基本约束条件
每个拼图块必须且只能以一种形态放置在一个位置：
# 每个拼图块只能选择一种形态和一个位置 for p in range(num_pieces): model.AddExactlyOne(work[p,s,r,c] for s in range(num_states) for r in range(rows) for c in range(cols))底板上的每个位置最多只能被一个拼图块覆盖：
# 预定义底板形状 - 这里用0表示空白，1表示需要填充的位置 board = [ [0,0,1,1,1,0,0], [0,1,1,1,1,1,0], [1,1,1,1,1,1,1], [1,1,1,1,1,1,1], [1,1,1,1,1,1,1], [0,1,1,1,1,1,0], [0,0,1,1,1,0,0] ] # 确保每个需要填充的位置只被一个拼图块覆盖 for r in range(rows): for c in range(cols): if board[r][c] == 1: model.AddAtMostOne( work[p,s,r-i,c-j] for p in range(num_pieces) for s in range(num_states) for (i,j) in get_offsets(p,s) # 获取拼图块在形态s下的偏移量 if 0 <= r-i < rows and 0 <= c-j < cols )3. 拼图形状与变换处理
3.1 定义拼图块的原始形状
我们需要为每个拼图块定义其原始形状的方块位置：
pieces = [ # 每个拼图块定义为其小方块的相对坐标[(i,j)] [(0,0),(0,1),(0,2),(1,0),(1,1)], # 拼图块0 [(0,0),(0,1),(1,1),(2,1),(2,2)], # 拼图块1 # ...其他拼图块定义 ]3.2 实现拼图块的旋转和翻转
拼图块可以通过旋转和翻转产生不同的形态：
def get_transformed_piece(piece, state): """根据状态编号返回变换后的拼图形状""" transformed = [] for (i,j) in piece: if state == 0: # 原始形态 ni, nj = i, j elif state == 1: # 旋转90度 ni, nj = j, -i # ...其他变换状态 transformed.append((ni,nj)) return transformed def get_offsets(p, s): """返回拼图块p在形态s下的所有方块相对于基准点的偏移""" piece = pieces[p] transformed = get_transformed_piece(piece, s) return transformed4. 完整求解与结果可视化
4.1 设置求解器并执行求解
solver = cp_model.CpSolver() status = solver.Solve(model) if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: print("找到解!") # 处理解... else: print("未找到解")4.2 解析并可视化结果
我们可以将求解结果转换为可视化的拼图布局：
import matplotlib.pyplot as plt import numpy as np def visualize_solution(solution): fig, ax = plt.subplots(figsize=(8,8)) # 绘制底板 for r in range(rows): for c in range(cols): if board[r][c] == 0: ax.add_patch(plt.Rectangle((c,-r), 1, 1, color='lightgray')) # 绘制拼图块 colors = plt.cm.tab10.colors for p in range(num_pieces): for s in range(num_states): for r in range(rows): for c in range(cols): if solver.Value(work[p,s,r,c]): offsets = get_offsets(p,s) for (i,j) in offsets: ax.add_patch(plt.Rectangle( (c+j,-(r+i)), 1, 1, color=colors[p], alpha=0.7 )) ax.set_xlim(0, cols) ax.set_ylim(-rows, 0) ax.set_aspect('equal') ax.axis('off') plt.show() visualize_solution(solver)5. 高级技巧与优化
5.1 处理特定日期的约束
要解决特定日期的拼图问题，我们需要添加额外的约束：
def add_date_constraint(model, work, month, day, weekday): # 月份约束 (1-12) month_positions = [(0,2),(0,3),(0,4)] # 示例位置 for r,c in month_positions: model.Add(sum( work[p,s,r-i,c-j] for p in range(num_pieces) for s in range(num_states) for (i,j) in get_offsets(p,s) if (r-i,c-j) == (r,c) ) == month) # 类似添加日期和星期的约束...5.2 对称性消除
拼图问题通常有很多对称解，我们可以添加约束来消除对称性，加速求解：
# 强制某些拼图块按特定顺序放置，消除对称解 for p in range(1, num_pieces): model.Add( sum(r*cols + c for s in range(num_states) for r in range(rows) for c in range(cols) if solver.Value(work[p,s,r,c])) > sum(r*cols + c for s in range(num_states) for r in range(rows) for c in range(cols) if solver.Value(work[p-1,s,r,c])) )5.3 性能优化技巧
对于大型拼图或需要求解多个解的情况，可以考虑以下优化：
- 限制求解时间：
solver.parameters.max_time_in_seconds = 60 - 使用多线程：
solver.parameters.num_search_workers = 4 - 添加启发式规则：优先放置较大或形状特殊的拼图块
# 优化求解器参数 solver.parameters.max_time_in_seconds = 30 # 限制求解时间 solver.parameters.num_search_workers = 4 # 使用4个线程在实际项目中，我发现将较大的拼图块优先放置可以显著减少求解时间。另外，合理设置对称性消除约束可以避免求解器浪费时间在本质上相同的解上。