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

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

邱仲普

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