P13 · Packing circles of radius 1,2,…,n into a square · Discussion

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

邱仲普

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