10*10网格放置最少2*3块阻塞新增同规格块的算法咨询

这类网格铺砌下的最小阻塞问题，属于组合几何范畴内的最小阻塞集（Minimum Blocking Set）问题，细分到矩形铺砌场景下也被称为最小不可扩充铺砌问题，属于已被证明的NP难组合优化问题，没有通用的闭式解公式，常用的求解方向分为三类：

• 精确求解（小规模网格最优解）：首选*整数线性规划（ILP, Integer Linear Programming）建模，是目前小尺寸网格下拿到精确最优解的标准方案。建模逻辑为：枚举网格内所有可以合法放置目标矩形（比如你的场景里的23矩形，包含横放、竖放两种朝向）的位置，为每个位置设置0-1变量表示是否在这里放置矩形块；约束包含两部分，一是任意两个放置的矩形不能重叠占用同一个格子，二是所有未放置块的空位里，不存在任何一个可以完整放下目标矩形的连续区域；优化目标为最小化放置的矩形总数量。你提到的两个小网格参考结果，都是用这个方法验证得到的精确值。
• 下界推导：最常用的是周期染色不变量法，属于手算推理论证的核心技巧。操作方式是按照固定的周期给网格格子染色（比如针对23矩形通常用6色周期染色，保证无论怎么放一个23矩形，都会恰好覆盖每种颜色各1个格子），通过染色规则推导要让所有空位凑不出满足覆盖要求的完整矩形，最少需要占用多少个格子，再换算成最少需要的矩形块数量，用来和精确求解的结果交叉验证。
• 中大规模网格求解：可以把问题转化为布尔可满足性问题（SAT, Boolean Satisfiability Problem），配合通用SAT求解器做回溯剪枝搜索：从染色法得到的块数下界开始从小到大枚举k值，每次判断是否存在k个矩形块的放置方案能阻塞所有目标矩形的合法放置位置，第一个找到可行解的k就是答案。

内容的提问来源于stack exchange，提问作者Xus