P96 · Consecutive L shapes in a square · Discussion

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

邱仲普

P96 n=35:公开构造边长 215.992687512 精修为 215.992686915,缩短 597 个 1e-9 网格单位。这是有限网格改进,未证明全局最优。 方法:固定每块的 quarter 和 turn。先精确计算全部顶点,将最小 x、y 向下取整到网格,统一平移裁掉边缘空白。再用整数平移 dx、dy 和正整数边长缩减量 d 建立 HiGHS MILP,最大化 d。保留所有顶点包含约束;每对 L 分成两个矩形,对四个跨块矩形对各选当前合法、归一化余量最大的边法向作为分离轴并保持分离。平移及 d 的上限依次为 [2, 10, 100, 1000, 10000, 100000, 1000000],每轮 5 秒、相对 MIP 间隙 0。浮点优化只生成候选,须经两套精确验证才接受。接受的局部步骤:L=2: 215.992687510, L=10: 215.992687500, L=100: 215.992687400, L=1000: 215.992686915。 无需重跑优化器的确定性复现:起始 side=215.992687512;以下各行按短边 k=1..35 排列,格式 [x,y,quarter,turn]: [["67.009955189","67.128400575",2,"-0.000580385"],["66.017161463","66.113121389",0,"0.003544533"],["162.392915969","74.917828486",1,"-0.008814509"],["64.021323319","64.098947561",0,"0.002286230"],["144.770170904","170.819623712",3,"0.001246317"],["145.599030087","164.821681069",1,"0.000331116"],["208.945533678","207.589294545",2,"-0.003379591"],["60.029371573","60.080665729",0,"0.001643524"],["196.415037616","207.012746361",0,"0.033400955"],["149.498864796","148.818984657",3,"0.001573445"],["150.012329747","137.822359884",1,"-0.007507177"],["202.038498675","186.341915134",3,"0.033400965"],["202.826881388","173.406870636",1,"-0.006418620"],["79.731685850","185.992687411",0,"-0.000000000"],["79.736195269","200.992687511",2,"-0.000000000"],["171.152894652","197.045833917",3,"0.005373471"],["52.054408359","52.054408359",0,"0.001602816"],["171.477275798","179.048280522",1,"0.005372736"],["135.195205942","195.494264763",2,"-0.022088598"],["115.085619973","193.456648913",0,"-0.022088657"],["43.971411668","194.232412596",2,"0.018448263"],["22.000000001","193.457849063",0,"0.000000000"],["116.269748676","149.978450162",2,"-0.010909203"],["91.548927694","147.993976393",0,"0.005182335"],["190.000480758","52.441373152",3,"-0.008828149"],["189.992687511","26.000000001",1,"0.000000000"],["187.994994442","133.593982734",3,"-0.006418618"],["187.635566906","105.596289498",1,"-0.006418615"],["97.097971864","95.048644973",3,"0.005182335"],["100.000000530","30.000000001",0,"0.000000000"],["128.096307080","95.369940537",1,"0.005182332"],["131.999977163","32.038730184",2,"-0.000605526"],["33.340308670","138.345570284",3,"0.005183196"],["33.998173802","104.350563150",1,"0.005182334"],["35.000000001","35.000000001",0,"0.000000000"]] 对对应原点加入下列 [dx,dy]×1e-9,保留全部朝向,side 设为 215.992686915: [[1088,1088],[1088,1088],[-299,-102],[1088,1088],[1088,1088],[1088,1088],[-1112,1088],[888,888],[-569,-596],[1088,1088],[1088,1088],[-500,-491],[-597,-398],[1088,-511],[-181,-596],[-476,-495],[-101,-101],[-406,-395],[-306,1088],[-206,1085],[-106,88],[-1,-40],[1088,-184],[899,-412],[-399,-100],[-596,-1],[-557,-298],[-608,-197],[-98,-322],[-530,-1],[-200,-97],[-496,0],[0,59],[0,-100],[-1,-1]] 精确验证:小数乘 10^9 转为整数,t=turn,以 cos=(1−t²)/(1+t²)、sin=2t/(1+t²) 计算旋转。第一实现将每块分成两矩形,清分母后用整数分离轴检验;第二实现将每块分成三正方形,用有理数多边形裁剪检验交面积为零。全部 35 块的顶点包含和 595 对块约束均通过;接触允许,正面积重叠拒绝。