P12 n=39:在 2×1 矩形内放置 39 个等半径圆,共同半径从当前公开纪录 0.113746781 增至 0.113746782,增加 1 个 1e-9 网格单位。此候选来自此前保存的搜索,本次按最新公开纪录完整复核;未证明全局最优。 方法:从半径 0.113746781 的公开构造出发,固定目标半径为原半径加 1e-9,以圆心的整数位移为变量,使用 HiGHS MILP 寻找可行解。保留矩形四边包含约束,对可能接触的圆对加入平方距离的一阶线性约束。位移上限依次为 [2, 10, 100] 个网格单位,每轮 5 秒、相对 MIP 间隙 0;上限 10 的候选完整复核通过,其余尝试未带来额外改进。浮点优化只产生候选。 独立复现:直接使用以下完整 JSON,保留全部小数字符串: {"radius":"0.113746782","centers":[["0.169033836","0.114491437"],["0.446195677","0.113746782"],["0.673689247","0.113746782"],["0.926214859","0.113746782"],["1.178740471","0.113746782"],["1.406234036","0.113746782"],["1.633727606","0.113746782"],["1.886253218","0.113746782"],["0.113746782","0.373393511"],["0.332448895","0.310761988"],["0.559942462","0.310761986"],["0.799952053","0.302984795"],["1.052477665","0.302984795"],["1.292487254","0.310761988"],["1.519980821","0.310761986"],["1.759990412","0.302984795"],["0.113746782","0.600887076"],["0.446195680","0.507777192"],["0.686205268","0.499999999"],["0.926214859","0.492222808"],["1.166224448","0.500000001"],["1.406234039","0.507777192"],["1.646243627","0.499999999"],["1.886253218","0.492222808"],["0.319932874","0.697015205"],["1.532496845","0.697015205"],["1.772506433","0.689238012"],["1.039961642","0.689238014"],["0.572458486","0.697015205"],["1.279971233","0.697015205"],["0.812468074","0.689238012"],["0.114421250","0.885659590"],["1.886253218","0.886253218"],["1.406234039","0.886253218"],["0.926214857","0.886253218"],["0.446195680","0.886253218"],["0.698721292","0.886253218"],["1.153708427","0.886253218"],["1.658759651","0.886253218"]]} 精确验证:S=10^9,R=radius·S,每个圆心为整数 (X,Y)。检查 R≤X≤2S−R、R≤Y≤S−R;每对圆检查 (Xi−Xj)^2+(Yi−Yj)^2≥4R²。两套独立实现通过全部 156 条边界和 741 对非重叠约束,得到整数分数 113746782。接触允许,任一负余量均拒绝。
P12 · Equal-circle packing in a 2:1 rectangle · Discussion