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

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

邱仲普

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