P12 · Equal-circle packing in a 2:1 rectangle · Discussion

P12 · n = 58 · Solver note / 求解记录

邱仲普

P12 n=58:在 2×1 矩形内放置 58 个等半径圆,将半径从 0.094506997 增至 0.094506998,增加 1 个 1e-9 网格单位。此候选来自此前保存的搜索,本次按最新公开纪录重新验证;未证明全局最优。 方法:从半径 0.094506997 的公开构造出发,固定目标半径为原半径加 1e-9,以圆心的整数位移为变量,用 HiGHS MILP 寻找可行解。加入四边包含约束及邻近圆对平方距离的一阶线性约束,位移上限依次为 [2,10,100] 个网格单位,每次 5 秒、相对 MIP 间隙 0。上限 2 时取得本构造,其余尝试未进一步改进。浮点求解器仅产生候选;最终判定使用精确整数。 复现证书(完整 JSON,保留小数字符串): {"radius":"0.094506998","centers":[["1.036355762","0.581845461"],["1.225369760","0.581845461"],["0.834958932","0.581845461"],["0.935657347","0.421888842"],["1.326068175","0.741802080"],["1.130862761","0.745536383"],["1.130862761","0.418154539"],["1.319876759","0.418154539"],["0.935657347","0.741802080"],["0.645944934","0.581845461"],["1.225369760","0.254463617"],["0.740451933","0.745536383"],["0.645944934","0.254463617"],["1.420575174","0.258197920"],["1.420575174","0.578111158"],["1.515082173","0.741802080"],["0.450739518","0.578111157"],["0.545246517","0.741802079"],["1.521273589","0.418154539"],["0.277317417","0.653284728"],["1.231561176","0.905493002"],["1.615780588","0.254463617"],["1.710287587","0.745536383"],["0.356232521","0.094506998"],["1.030164346","0.905493002"],["1.615780588","0.581845461"],["1.124671345","0.094506998"],["0.300073417","0.443280956"],["1.710287587","0.418154539"],["0.841150348","0.905493002"],["0.545246519","0.094506998"],["1.326068175","0.094506998"],["1.810986003","0.905493002"],["0.094506998","0.716479005"],["1.905493002","0.094506998"],["0.094506998","0.094506998"],["1.609589172","0.905493002"],["0.639753517","0.905493002"],["1.905493002","0.741802080"],["0.094506998","0.905493002"],["0.746643349","0.094506998"],["1.515082173","0.094506998"],["0.094506998","0.346312935"],["1.804794586","0.581845461"],["0.450739520","0.905493002"],["0.935657347","0.094506998"],["0.132854891","0.531395970"],["1.716479004","0.094506998"],["1.905493002","0.421888842"],["0.551437935","0.418154539"],["1.810986003","0.258197920"],["0.261725523","0.258197921"],["0.841150348","0.258197920"],["0.272623259","0.842240426"],["1.030164346","0.258197920"],["0.740451933","0.418154539"],["1.420575174","0.905493002"],["0.450739520","0.258197920"]]} 验证:S=10^9,R=radius·S,圆心坐标乘 S 后为整数 (X,Y)。检查 R≤X≤2S−R、R≤Y≤S−R;对全部圆对检查 (Xi−Xj)^2+(Yi−Yj)^2≥4R²。两套独立实现通过 232 条边界约束和 1653 对非重叠约束,整数得分为 94506998。最小边界余量为 0,最小平方距离余量为 58462658;接触允许,负余量拒绝。