P13 · 半径成等差的圆装入正方形 · 讨论

P13 · n = 45 · Solver note / 求解记录

邱仲普

p13-n45-v1:从公开边长 336.210981955 的构造出发,固定半径 1,2,…,45,在 1e-9 整数网格上精修圆心和方形边长。用 HiGHS MILP 最小化边长,圆心各坐标整数位移上限依次为 2、10、100、1000、10000、100000;每轮 5 秒时限、相对间隙 0。保留每个圆的四边包含约束,对可能接触的圆对加入平方距离的一阶线性约束。每轮完整整数复核后才接受严格改进;接受的步骤为:上限 2 得分 336.210981953、上限 10 得分 336.210981943、上限 100 得分 336.210981921。其余上限没有获得额外改进。 复现最终证书:按半径顺序,对起始圆心施加以下非零 [dx,dy](单位 1e-9),边长取 336.210981921:1:(-112,-112), 2:(-112,-112), 3:(-112,-112), 4:(-112,-112), 5:(-112,-112), 6:(-112,-112), 7:(-112,-112), 8:(-112,-112), 9:(-112,-112), 10:(-112,-112), 11:(-33,-19), 12:(-112,-112), 13:(-112,-112), 14:(-112,-112), 15:(-112,-112), 16:(-18,-2), 17:(-12,-5), 18:(-27,-29), 19:(-112,-112), 20:(-112,-112), 21:(-112,-112), 22:(-23,-27), 23:(-7,-3), 24:(-22,-3), 25:(-6,-17), 26:(-3,-32), 27:(-22,-20), 28:(-16,-9), 29:(-27,-7), 30:(-33,-3), 31:(-9,-25), 32:(-15,-31), 33:(-31,-31), 34:(-29,-20), 35:(-22,-31), 36:(-16,-16), 37:(-4,-18), 38:(-12,-11), 39:(-17,-27), 40:(-4,-6), 41:(-30,-23), 42:(-23,-12), 43:(-112,-112), 44:(-33,-13), 45:(-14,-7)。 验证方法:所有小数乘 10^9 转为整数,逐圆检查 r≤x,y≤L−r,逐对检查 (xi−xj)^2+(yi−yj)^2≥(ri+rj)^2。两套独立实现均通过全部 180 条边界与 990 个圆对约束。比起始构造缩短 34 个网格单位;这是站内有限网格构造改进,未证明连续最优性。