P89 · 装箱与覆盖 · 经典问题 · 难

等腰直角三角形装入正方形 · n = 6

把 n 个直角边为 1 的等腰直角三角形(七巧板的小三角形)装入正方形,允许接触但内部不能重叠,最小化容器正方形边长。

子题n = 6
目标最小化 容器正方形边长

纪录对比

容器正方形边长 · 越小越好
纪录数值 / 区间作者 / 持有人来源
外部已知最好[1.937, 1.938)Maurizio MorandiErich Friedman ↗
本站纪录1.937914814邱仲普纪录详情 ↓

在公布精度内匹配已知最好;不代表精确相等或已证明最优。

严格定义

  • 容器编辑器与证书将容器统一归一化为单位正方形 [0,1]²;公开得分按文献的单位直角边长规范折算。允许接触边界。
  • 提交提交 {radius, placements:[{x,y,turn,quarter},…]},其中 x、y、turn 为最多九位小数的十进制字符串。radius 为单位正方形容器内零件的直角边长,对应容器正方形边长 = 1/radius。x、y 为零件轴对齐外接框的中心;quarter 为 0–3 的整数,表示先绕中心旋转 quarter 个直角,再旋转由 turn = tan(θ/2) 给出的有理角。坐标与 turn 的范围限于 [−4, 4],且 0 < radius ≤ 4。
  • 约束恰好 n 个全等图形完全位于容器内,任意两图形内部互不重叠。每个图形允许任意角度独立旋转。
  • 精度输入的十进制小数按精确有理数解析,可行性检验不设浮点容差。
  • 目标容器正方形边长 = 1/r(其中 r 为零件直角边在单位正方形容器内的长度),越小越好。页面、排行榜与文献纪录统一使用该单位并自动换算。
放大编辑并提交 ↗

当前展示:本站纪录

已验证构造已验证构造

帮助理解

文献来源与坐标证书

文献目标值按原始发表精度换算,九位小数坐标证书单独存储并与文献目标对照展示。

查看来源
等腰直角三角形装入正方形 n = 6 的当前纪录构型,1.937914814
构型与历史

纪录详情

查看构型、求解笔记与纪录历史。

纪录保持者邱仲普
解题方式AI · OpenAI: GPT-5.6 Sol
挑战这个纪录 ↗提交证明 / 思路 ↓在讨论区分享最优性证明或关键界限思路,经审核采纳后可获证明分。
纪录保持者的求解笔记公开方法与可复现线索(点击展开)+

P89, n=6: fixed-orientation refinement on the 10^-9 grid. Start from the public certificate with leg length 0.516018553 and stored container-side score 1937914817570522508. Preserve all six triangle turns and quarter-turns; adjust only centres and common leg length. Scale coordinates by Q=10^9. Use integer centre displacements in [-L,L] and a radius increment in [1,L], with L=2,10,100,1000 in sequence. Impose all vertex-in-square inequalities and one exact linearized separating-axis constraint per currently separating triangle pair. Solve with SciPy/HiGHS MILP, zero relative MIP gap and a five-second limit; accept only strict improvements that pass both exact verifiers. The search increased the leg length to 0.516018554, reducing the stored score to 1937914813815008676. Replaying from the supplied starting certificate reproduced identical coordinates; continuation at L=2,10,100,1000,10000 found no further improvement with these fixed separation directions. This is a certified grid refinement and not a global optimality claim. The integer homogeneous-coordinate separating-axis verifier and independent rational polygon-clipping verifier certify all 18 triangle vertices and all 15 triangle pairs with zero intersection area. Candidate certificate: {"placements":[{"quarter":2,"turn":"0.414213559","x":"0.483981443","y":"0.603082668"},{"quarter":3,"turn":"-0.413423643","x":"0.510104571","y":"0.000730886"},{"quarter":3,"turn":"0.000000000","x":"0.258009277","y":"0.741990723"},{"quarter":2,"turn":"0.058838192","x":"0.713514129","y":"0.225972167"},{"quarter":2,"turn":"0.000000000","x":"0.741990723","y":"0.709953614"},{"quarter":3,"turn":"0.093928203","x":"0.324552917","y":"0.301541334"}],"radius":"0.516018554"}

在讨论区查看与回复 →
历史纪录(2 次易主)
  1. 邱仲普AI · OpenAI: GPT-5.6 Sol
    1.937914818→1.937914814
  2. 匿名人工
    1.937914833→1.937914818
ANSWER FORMAT

答案怎么写

单位正方形 [0,1]²

提交 {radius, placements:[{x,y,turn,quarter},…]},其中 x、y、turn 为最多九位小数的十进制字符串。radius 为单位正方形容器内零件的直角边长,对应容器正方形边长 = 1/radius。x、y 为零件轴对齐外接框的中心;quarter 为 0–3 的整数,表示先绕中心旋转 quarter 个直角,再旋转由 turn = tan(θ/2) 给出的有理角。坐标与 turn 的范围限于 [−4, 4],且 0 < radius ≤ 4。

当前第一名的答案

{
  "placements": [
    {
      "quarter": 2,
      "turn": "0.414213559",
      "x": "0.483981443",
      "y": "0.603082668"
    },
    {
      "quarter": 3,
      "turn": "-0.413423643",
      "x": "0.510104571",
      "y": "0.000730886"
    },
    {
      "quarter": 3,
      "turn": "0.000000000",
      "x": "0.258009277",
      "y": "0.741990723"
    },
    {
      "quarter": 2,
      "turn": "0.058838192",
      "x": "0.713514129",
      "y": "0.225972167"
    },
    {
      "quarter": 2,
      "turn": "0.000000000",
      "x": "0.741990723",
      "y": "0.709953614"
    },
    {
      "quarter": 3,
      "turn": "0.093928203",
      "x": "0.324552917",
      "y": "0.301541334"
    }
  ],
  "radius": "0.516018554"
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "n": 6,
  "sides": 5
}

当前第一名的答案

{
  "placements": [
    {
      "quarter": 2,
      "turn": "0.414213559",
      "x": "0.483981443",
      "y": "0.603082668"
    },
    {
      "quarter": 3,
      "turn": "-0.413423643",
      "x": "0.510104571",
      "y": "0.000730886"
    },
    {
      "quarter": 3,
      "turn": "0.000000000",
      "x": "0.258009277",
      "y": "0.741990723"
    },
    {
      "quarter": 2,
      "turn": "0.058838192",
      "x": "0.713514129",
      "y": "0.225972167"
    },
    {
      "quarter": 2,
      "turn": "0.000000000",
      "x": "0.741990723",
      "y": "0.709953614"
    },
    {
      "quarter": 3,
      "turn": "0.093928203",
      "x": "0.324552917",
      "y": "0.301541334"
    }
  ],
  "radius": "0.516018554"
}

提交 {radius, placements:[{x,y,turn,quarter},…]},其中 x、y、turn 为最多九位小数的十进制字符串。radius 为单位正方形容器内零件的直角边长,对应容器正方形边长 = 1/radius。x、y 为零件轴对齐外接框的中心;quarter 为 0–3 的整数,表示先绕中心旋转 quarter 个直角,再旋转由 turn = tan(θ/2) 给出的有理角。坐标与 turn 的范围限于 [−4, 4],且 0 < radius ≤ 4。 · 验证器 v1.0.0

DISCUSSION

讨论区

欢迎交流解题思路、分享构造方法或探讨卡壳之处。所有登录用户均可发帖;发言使用与排行榜一致的公开署名,并附带唯一注册编号(#UID)以防冒名。新发言经审核后公开。