P96 · Consecutive L shapes in a square · Discussion

P96 · n = 39 · Solver note / 求解记录

邱仲普

P96 n=39:公开构造边长 252.965715662 精修为 252.965715645,缩短 17 个 1e-9 网格单位。这是有限网格改进,未证明全局最优。 方法:固定每块的 quarter 和 turn。先精确计算全部顶点,将最小 x、y 向下取整到网格,统一平移裁掉边缘空白。再用整数平移 dx、dy 和正整数边长缩减量 d 建立 HiGHS MILP,最大化 d。保留所有顶点包含约束;每对 L 分成两个矩形,对四个跨块矩形对各选当前合法、归一化余量最大的边法向作为分离轴并保持分离。平移及 d 的上限依次为 [2, 10, 100, 1000, 10000],每轮 5 秒、相对 MIP 间隙 0。浮点优化只生成候选,须经两套精确验证才接受。接受的局部步骤:L=2: 252.965715657, L=10: 252.965715647, L=100: 252.965715646, L=1000: 252.965715645。 无需重跑优化器的确定性复现:起始 side=252.965715662;以下各行按短边 k=1..39 排列,格式 [x,y,quarter,turn]: [["75.775229843","143.111862051",0,"-0.059469057"],["74.655938576","142.107212148",0,"-0.026917669"],["80.950739250","189.770564728",0,"-0.011031816"],["198.399541855","236.268429812",3,"-0.038802936"],["72.520968693","140.062932896",0,"-0.007583786"],["199.776854829","229.961727426",1,"-0.000786609"],["186.896359330","231.588592221",1,"-0.046374690"],["187.042375991","240.977075287",3,"-0.001181369"],["67.441962694","135.105567387",0,"-0.005792929"],["88.577939204","177.022805669",3,"0.036656659"],["89.345760259","166.063419502",1,"0.011582910"],["190.989747737","211.973216648",3,"-0.000779340"],["191.965715658","198.953977845",1,"0"],["130.320639758","172.141747585",2,"0.007870533"],["115.230976689","171.804057774",0,"0.011208041"],["236.694479980","163.712497043",2,"-0.008549514"],["219.697507694","164.010196690",0,"-0.012074157"],["184.779033040","167.808326525",2,"-0.012074157"],["58.001308376","126.000966670",0,"-0.000005696"],["164.784863597","168.291222403",0,"-0.012074157"],["123.213087625","44.067002578",3,"-0.001569840"],["123.423756645","22.000215580",1,"-0.000003719"],["228.786995000","229.373503537",3,"-0.000018514"],["228.965715661","205.371540089",1,"0"],["52.551523691","171.987829915",2,"-0.011031816"],["26.000000009","172.000000009",0,"0"],["27.524776614","224.975267661",0,"-0.009815363"],["56.009253261","224.918616926",2,"-0.000841758"],["107.151924383","126.465234697",3,"0.011582910"],["108.296601559","96.500416815",1,"-0.005105549"],["148.002388833","220.763739097",2,"-0.000841758"],["116.002434177","220.817611568",0,"-0.000841758"],["68.654425774","33.987019679",2,"-0.009916366"],["34.000000003","34.000000003",0,"0"],["217.695940888","35.998322279",2,"-0.003860127"],["181.424773031","36.000000003",0,"0"],["215.286707979","109.987303281",2,"-0.009262219"],["176.601362560","110.000000006",0,"0"],["39.000000006","107.000000006",0,"0"]] 对对应原点加入下列 [dx,dy]×1e-9,保留全部朝向,side 设为 252.965715645: [[-1114,-1115],[-1114,-1115],[33,1109],[-1114,-1115],[-1114,-1115],[-1114,-1115],[-1114,-1115],[-1114,-1115],[-1114,-1115],[1106,1109],[1110,1109],[-1114,-1115],[-13,142],[1086,1085],[1110,1109],[1110,1109],[1110,1105],[1088,118],[-1114,-1115],[985,123],[-1114,-1115],[-1114,-1115],[-1114,-1115],[-16,-1115],[-11,71],[-9,-9],[-2,-82],[-5,-17],[1110,1105],[1106,1092],[-9,1031],[-6,686],[1039,-27],[-3,-3],[-1114,-1115],[-1114,-3],[1106,-8],[1104,-6],[-6,-6]] 精确验证:小数乘 10^9 转为整数,t=turn,以 cos=(1−t²)/(1+t²)、sin=2t/(1+t²) 计算旋转。第一实现将每块分成两矩形,清分母后用整数分离轴检验;第二实现将每块分成三正方形,用有理数多边形裁剪检验交面积为零。全部 39 块的顶点包含和 741 对块约束均通过;接触允许,正面积重叠拒绝。