P96 · Consecutive L shapes in a square · Discussion

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

邱仲普

P96 n=48:公开构造边长 343.764616265 精修为 343.764616224,缩短 41 个 1e-9 网格单位。这是有限网格改进,未证明全局最优。 方法:固定每块的 quarter 和 turn。先精确计算全部顶点,将最小 x、y 向下取整到网格,统一平移裁掉边缘空白。再用整数平移 dx、dy 和正整数边长缩减量 d 建立 HiGHS MILP,最大化 d。保留所有顶点包含约束;每对 L 分成两个矩形,对四个跨块矩形对各选当前合法、归一化余量最大的边法向作为分离轴并保持分离。平移及 d 的上限依次为 [2, 10, 100, 1000, 10000],每轮 5 秒、相对 MIP 间隙 0。浮点优化只生成候选,须经两套精确验证才接受。接受的局部步骤:L=1000: 343.764616262, L=10000: 343.764616224。 无需重跑优化器的确定性复现:起始 side=343.764616265;以下各行按短边 k=1..48 排列,格式 [x,y,quarter,turn]: [["187.610219598","216.052413610",0,"0.001065175"],["339.506659690","265.652508626",0,"-0.000097049"],["186.533899417","214.996625065",0,"0.000203079"],["97.517576514","221.074215103",0,"0.000092665"],["337.499835481","263.651974152",0,"-0.000451177"],["182.692779645","211.978278671",0,"0.000199314"],["221.181403366","111.358431495",3,"-0.000289340"],["221.327407292","103.351640499",1,"0.000027982"],["20.977375207","235.224646293",2,"0.001034408"],["10.428967780","235.022102896",0,"0.004767490"],["332.295608176","258.637362848",0,"-0.001085513"],["176.220675174","205.811645628",0,"-0.000619264"],["120.000000512","108.073476241",2,"-0.000000018"],["106.000000084","101.888626892",0,"-0.000000003"],["31.978372106","326.638188113",2,"0.018967446"],["16.000000000","326.068261274",0,"0.000000000"],["84.017664016","326.612253403",2,"-0.000874703"],["65.034784543","325.777563111",0,"0.018967446"],["209.115122051","159.092926002",3,"-0.016958589"],["208.623039780","139.098113736",1,"-0.016958589"],["21.709295135","289.037877536",3,"0.001471847"],["22.017017354","267.038712322",1,"0.000729265"],["320.722584020","246.572030402",0,"-0.006218739"],["164.081528262","193.151817438",0,"-0.000049687"],["210.081073621","318.764616265",3,"0.000000000"],["210.764615745","292.764616265",1,"-0.000000010"],["71.865628487","281.004338449",3,"0.018966261"],["72.890955802","253.041637413",1,"0.000772566"],["219.147940071","237.764616097",3,"-0.000000010"],["219.114597817","207.781866731",1,"-0.016958589"],["243.245072775","64.319040694",3,"-0.000470152"],["243.764611765","32.000120627",1,"-0.000001125"],["308.726584788","67.989661411",3,"0.004979778"],["309.764616265","34.000000000",1,"0.000000000"],["308.764616265","308.050143781",2,"-0.000000000"],["272.764616265","307.764616238",0,"0.000000000"],["306.117431511","138.945114919",2,"-0.008824289"],["267.350325269","138.841251393",0,"0.001544821"],["171.944444480","80.149069231",3,"-0.001870367"],["171.794815803","40.149348935",1,"-0.001870365"],["142.175024777","302.560224374",3,"-0.001333548"],["142.875796604","259.770466358",1,"0.008368116"],["88.159321483","44.111388739",2,"-0.001397360"],["44.010718773","44.000000000",0,"0.000000000"],["45.916974354","179.999871715",3,"0.000772566"],["46.000000000","134.000000000",1,"0.000000000"],["296.781098274","223.536495007",0,"-0.013242782"],["140.000002345","169.073483772",0,"0.000000107"]] 对对应原点加入下列 [dx,dy]×1e-9,保留全部朝向,side 设为 343.764616224: [[-11000,-11000],[-11000,-11000],[-11000,-11000],[-127,-54],[-11000,-11000],[-11000,-11000],[-11000,-11000],[-11000,-11000],[-11000,-11000],[-9000,-173],[-11000,-11000],[-11000,-11000],[0,-43],[0,-9000],[-417,10813],[0,-175],[-11000,-11000],[10,-41],[-8797,262],[162,8],[-9172,-202],[10192,-145],[-11000,-11000],[-11000,-11000],[-11000,-41],[-50,-41],[-69,-44],[-64,-44],[-65,-41],[-57,-35],[-11000,-11000],[-41,-11000],[-208,-1],[-41,0],[-41,-11000],[-41,-78],[-42,-78],[-39,-79],[0,-28],[0,-39],[-11000,-11000],[-60,33],[-11000,-11000],[-11000,0],[11000,17],[0,0],[-50,-78],[160,-43]] 精确验证:小数按 10^9 网格解析,令 t 为 turn 表示的有理数,以 cos=(1−t²)/(1+t²)、sin=2t/(1+t²) 计算旋转,再叠加 quarter×90°。第一实现将每块分成两矩形,清分母后用整数分离轴检验;第二实现将每块分成三正方形,用有理数多边形裁剪检验交面积为零。全部 48 块的顶点包含和 1128 对块约束均通过;接触允许,正面积重叠拒绝。