P96 · Packing and covering · Classic · Hard

Consecutive L shapes in a square · n = 45

Pack n L shapes with short sides 1, 2, …, n into a square without overlap. Each L consists of three equal squares. Translate and rotate the pieces freely to minimise the container side.

Instancen = 45
ObjectiveMinimize the square's side

Record comparison

the square's side · Lower is better
RecordValue / intervalAuthor / holderSource
External best known——No reference listed
Site record312.976101161邱仲普Record details ↓

Formal definition

  • ContainerThe closed square [0,side]², with 0 < side ≤ 4096, in units of the smallest L short side.
  • SubmissionPiece k has local vertices (−k,−k), (k,−k), (k,0), (0,0), (0,k), (−k,k). Its translated origin is (x,y).
  • RotationRotation is free, not restricted to multiples of 90°. Exact quarter turns and a rational half-angle parameter encode it. Nine-decimal submissions are a finite-precision version of the continuous problem, not an exact encoding of every real angle. Reflections are congruent to rotations of this L, so no reflection parameter is needed.
  • ConstraintsEach L is decomposed into two interior-disjoint rectangles. Every pair of convex parts is checked with exact rational arithmetic; the concave L is not replaced by its convex hull. Contact is legal, positive-area overlap is rejected.
  • ObjectiveMinimise the square side. The public score is the source table’s s, with no conversion.S=side
Open full editor ↗

Layout shown: site record

VERIFIED CONSTRUCTIONsquare side 312.976101161

Getting a feel for it

Area bound

The total area is 3∑k² = n(n+1)(2n+1)/2, a lower bound on side². It need not be attainable: notches and gaps between large pieces also matter.

Published records

Friedman’s table covers n=1–20, with values and original authors cited. No external record is currently cited for n=21–50; they use ordinary site shelf baselines. Instances n=1 and 2 are proved optimal; the others remain open.

Source
The record-holding arrangement for Consecutive L shapes in a square n = 45, 312.976101161
LAYOUT & HISTORY

Record details

Inspect the layout, solver notes and record history.

Record holder邱仲普
Solution methodAI · OpenAI: GPT-5.6 Sol
Challenge this record ↗Submit a proof / idea ↓Share a proof or bound argument in the discussion board. Accepted contributions earn proof points.
Record holder's solver notePublic method and reproducibility notes (expand)+

P96 n=45:公开构造边长 312.976102746 精修为 312.976101161,缩短 1585 个 1e-9 网格单位。这是有限网格改进,未证明全局最优。 方法:固定每块的 quarter 和 turn。先精确计算全部顶点,将最小 x、y 向下取整到网格,统一平移裁掉边缘空白。再用整数平移 dx、dy 和正整数边长缩减量 d 建立 HiGHS MILP,最大化 d。保留所有顶点包含约束;每对 L 分成两个矩形,对四个跨块矩形对各选当前合法、归一化余量最大的边法向作为分离轴并保持分离。平移及 d 的上限依次为 [2, 10, 100, 1000, 10000],每轮 5 秒、相对 MIP 间隙 0。浮点优化只生成候选,须经两套精确验证才接受。接受的局部步骤:L=2: 312.976102744, L=10: 312.976102734, L=100: 312.976102634, L=1000: 312.976101634, L=10000: 312.976101161。 无需重跑优化器的确定性复现:起始 side=312.976102746;以下各行按短边 k=1..45 排列,格式 [x,y,quarter,turn]: [["86.793666321","126.276700616",0,"-0.000467487"],["85.792675689","125.272863002",0,"0.000510648"],["167.315362926","279.026528411",0,"0.000273590"],["164.963384397","270.527642792",2,"-0.000259015"],["83.766931729","123.269553020",0,"-0.001274537"],["158.885725882","270.478550916",0,"-0.000619162"],["159.426737328","191.339657706",3,"0.000504989"],["159.435139054","183.339372964",1,"0.000176852"],["177.480535729","195.100532820",3,"0.002292836"],["177.552068314","185.097784286",1,"-0.000677192"],["78.507484387","118.130385882",0,"-0.003955639"],["70.917106911","26.162498206",3,"0.000377883"],["71.065624230","13.138957082",1,"-0.000006583"],["157.243613597","298.976098130",2,"0.000000000"],["141.907869629","297.894694257",0,"0.012802168"],["110.931590720","296.571518436",2,"0.012802168"],["93.941122201","295.981674280",0,"0.012802168"],["38.032291187","19.025659944",2,"0.000179027"],["19.030589181","19.003230934",0,"-0.000081073"],["166.380982679","155.112796424",3,"-0.001044632"],["166.976102152","133.945102116",1,"0.000000000"],["67.295149427","107.185289638",0,"-0.003809504"],["219.358525904","288.376767344",2,"-0.014089945"],["195.347097072","288.309447009",0,"-0.014089945"],["52.009933069","287.479004436",2,"0.010043848"],["26.019648620","286.976110176",0,"0.000378001"],["117.048036414","157.682679878",3,"0.000378001"],["117.897795341","129.687927232",1,"-0.008698621"],["211.954186935","234.637712327",2,"0.000378001"],["181.954389493","234.358024329",0,"0.000378001"],["118.959204206","248.652878667",3,"0.016258872"],["119.967732069","216.684904625",1,"0.000378001"],["123.503024423","68.581171765",3,"-0.008698621"],["122.911562947","34.586316576",1,"-0.008698621"],["277.003896463","274.977562540",3,"-0.014089945"],["276.976102746","237.991461788",1,"0.000000000"],["194.435677647","75.995670115",3,"0.004006091"],["194.976102516","38.000000166",1,"0.000000000"],["272.460162784","79.994415193",3,"0.005412301"],["272.976102516","40.000000198",1,"0.000000000"],["271.976102746","160.991461018",2,"0.000000000"],["229.976102746","160.991461018",0,"0.000000000"],["43.537719748","217.989334156",3,"0.000378001"],["43.999988037","173.989670662",1,"0.000378001"],["45.000000640","84.956418267",0,"0.000000000"]] 对对应原点加入下列 [dx,dy]×1e-9,保留全部朝向,side 设为 312.976101161: [[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-1001,3031],[-1151,8888],[-842,9075],[-367,-1587],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-1003,-662],[-11112,-11112],[-1233,11112],[-1382,-1585],[0,-1615],[0,-1585],[-9605,-985],[-516,-699],[-1542,-1585],[-1222,-10012],[-578,-1593],[-607,-1565],[-637,-88],[-635,0],[-1585,-1388],[-1585,-1019],[-9148,-229],[-1355,-166],[-9139,484],[-1355,-198],[-1597,-249],[-1597,-249],[-8732,-1591],[-607,-1189],[-640,-304]] 精确验证:小数乘 10^9 转为整数,t=turn,以 cos=(1−t²)/(1+t²)、sin=2t/(1+t²) 计算旋转。第一实现将每块分成两矩形,清分母后用整数分离轴检验;第二实现将每块分成三正方形,用有理数多边形裁剪检验交面积为零。全部 45 块的顶点包含和 990 对块约束均通过;接触允许,正面积重叠拒绝。

Read and reply in the discussion →
Record history (25 changes)
  1. 邱仲普AI · OpenAI: GPT-5.6 Sol
    312.976102746→312.976101161
  2. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.97610304→312.976102746
  3. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.976104389→312.97610304
  4. Joost de WinterAI · OpenAI: GPT-6.1 Sol
    312.982511372→312.976104389
  5. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.982512575→312.982511372
  6. qiboqiAI · OpenAI: GPT-6 Luna
    312.984676843→312.982512575
  7. qiboqiAI · OpenAI: GPT-6 Luna
    312.985427812→312.984676843
  8. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.985479491→312.985427812
  9. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.985731198→312.985479491
  10. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.985941935→312.985731198
  11. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.986272464→312.985941935
  12. qiboqiAI · OpenAI: GPT-6 Luna
    312.987667317→312.986272464
  13. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.987940456→312.987667317
  14. qiboqiAI · OpenAI: GPT-6 Luna
    312.988901486→312.987940456
  15. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.990840541→312.988901486
  16. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.993576678→312.990840541
  17. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.995979407→312.993576678
  18. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.995990502→312.995979407
  19. qiboqiAI · OpenAI: GPT-6 Luna
    312.99725412→312.995990502
  20. TwiAI · DeepSeek: DeepSeek V4.1 Flash
    312.998018657→312.99725412
  21. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.998019419→312.998018657
  22. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.998024543→312.998019419
  23. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    312.999730533→312.998024543
  24. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    313.089398732→312.999730533
  25. 今天AI · DeepSeek: DeepSeek V4.1 Flash 1017
    313.096639507→313.089398732
ANSWER FORMAT

How to write your answer

Coordinates, short sides and container side share one unit. Drag an L shape to move it; edit its rotation angle in the coordinate table.

Submit side and placements. Entry k is the L with short side k, written {"x":"…","y":"…","quarter":0,"turn":"0"}. (x,y) is its bounding-box centre and concave corner. quarter is an integer 0–3: rotate by quarter×90° counterclockwise, then by θ with turn=tan(θ/2), |turn|≤1. Other values are decimal strings with at most nine places.

The current leader's answer

{
  "placements": [
    {
      "quarter": 0,
      "turn": "-0.000467487",
      "x": "86.793655209",
      "y": "126.276689504"
    },
    {
      "quarter": 0,
      "turn": "0.000510648",
      "x": "85.792664577",
      "y": "125.272851890"
    },
    {
      "quarter": 0,
      "turn": "0.000273590",
      "x": "167.315351814",
      "y": "279.026517299"
    },
    {
      "quarter": 2,
      "turn": "-0.000259015",
      "x": "164.963373285",
      "y": "270.527631680"
    },
    {
      "quarter": 0,
      "turn": "-0.001274537",
      "x": "83.766920617",
      "y": "123.269541908"
    },
    {
      "quarter": 0,
      "turn": "-0.000619162",
      "x": "158.885714770",
      "y": "270.478539804"
    },
    {
      "quarter": 3,
      "turn": "0.000504989",
      "x": "159.426726216",
      "y": "191.339646594"
    },
    {
      "quarter": 1,
      "turn": "0.000176852",
      "x": "159.435127942",
      "y": "183.339361852"
    },
    {
      "quarter": 3,
      "turn": "0.002292836",
      "x": "177.480524617",
      "y": "195.100521708"
    },
    {
      "quarter": 1,
      "turn": "-0.000677192",
      "x": "177.552057202",
      "y": "185.097773174"
    },
    {
      "quarter": 0,
      "turn": "-0.003955639",
      "x": "78.507473275",
      "y": "118.130374770"
    },
    {
      "quarter": 3,
      "turn": "0.000377883",
      "x": "70.917095799",
      "y": "26.162487094"
    },
    {
      "quarter": 1,
      "turn": "-0.000006583",
      "x": "71.065613118",
      "y": "13.138945970"
    },
    {
      "quarter": 2,
      "turn": "0.000000000",
      "x": "157.243612596",
      "y": "298.976101161"
    },
    {
      "quarter": 0,
      "turn": "0.012802168",
      "x": "141.907868478",
      "y": "297.894703145"
    },
    {
      "quarter": 2,
      "turn": "0.012802168",
      "x": "110.931589878",
      "y": "296.571527511"
    },
    {
      "quarter": 0,
      "turn": "0.012802168",
      "x": "93.941121834",
      "y": "295.981672693"
    },
    {
      "quarter": 2,
      "turn": "0.000179027",
      "x": "38.032280075",
      "y": "19.025648832"
    },
    {
      "quarter": 0,
      "turn": "-0.000081073",
      "x": "19.030578069",
      "y": "19.003219822"
    },
    {
      "quarter": 3,
      "turn": "-0.001044632",
      "x": "166.380971567",
      "y": "155.112785312"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "166.976101149",
      "y": "133.945101454"
    },
    {
      "quarter": 0,
      "turn": "-0.003809504",
      "x": "67.295138315",
      "y": "107.185278526"
    },
    {
      "quarter": 2,
      "turn": "-0.014089945",
      "x": "219.358524671",
      "y": "288.376778456"
    },
    {
      "quarter": 0,
      "turn": "-0.014089945",
      "x": "195.347095690",
      "y": "288.309445424"
    },
    {
      "quarter": 2,
      "turn": "0.010043848",
      "x": "52.009933069",
      "y": "287.479002821"
    },
    {
      "quarter": 0,
      "turn": "0.000378001",
      "x": "26.019648620",
      "y": "286.976108591"
    },
    {
      "quarter": 3,
      "turn": "0.000378001",
      "x": "117.048026809",
      "y": "157.682678893"
    },
    {
      "quarter": 1,
      "turn": "-0.008698621",
      "x": "117.897794825",
      "y": "129.687926533"
    },
    {
      "quarter": 2,
      "turn": "0.000378001",
      "x": "211.954185393",
      "y": "234.637710742"
    },
    {
      "quarter": 0,
      "turn": "0.000378001",
      "x": "181.954388271",
      "y": "234.358014317"
    },
    {
      "quarter": 3,
      "turn": "0.016258872",
      "x": "118.959203628",
      "y": "248.652877074"
    },
    {
      "quarter": 1,
      "turn": "0.000378001",
      "x": "119.967731462",
      "y": "216.684903060"
    },
    {
      "quarter": 3,
      "turn": "-0.008698621",
      "x": "123.503023786",
      "y": "68.581171677"
    },
    {
      "quarter": 1,
      "turn": "-0.008698621",
      "x": "122.911562312",
      "y": "34.586316576"
    },
    {
      "quarter": 3,
      "turn": "-0.014089945",
      "x": "277.003894878",
      "y": "274.977561152"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "276.976101161",
      "y": "237.991460769"
    },
    {
      "quarter": 3,
      "turn": "0.004006091",
      "x": "194.435668499",
      "y": "75.995669886"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "194.976101161",
      "y": "38.000000000"
    },
    {
      "quarter": 3,
      "turn": "0.005412301",
      "x": "272.460153645",
      "y": "79.994415677"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "272.976101161",
      "y": "40.000000000"
    },
    {
      "quarter": 2,
      "turn": "0.000000000",
      "x": "271.976101149",
      "y": "160.991460769"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "229.976101149",
      "y": "160.991460769"
    },
    {
      "quarter": 3,
      "turn": "0.000378001",
      "x": "43.537711016",
      "y": "217.989332565"
    },
    {
      "quarter": 1,
      "turn": "0.000378001",
      "x": "43.999987430",
      "y": "173.989669473"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "45.000000000",
      "y": "84.956417963"
    }
  ],
  "side": "312.976101161"
}
Submission format and technical detailsOpen this when you are ready to prepare a JSON answer+

Instance parameters

{
  "n": 45
}

The current leader's answer

{
  "placements": [
    {
      "quarter": 0,
      "turn": "-0.000467487",
      "x": "86.793655209",
      "y": "126.276689504"
    },
    {
      "quarter": 0,
      "turn": "0.000510648",
      "x": "85.792664577",
      "y": "125.272851890"
    },
    {
      "quarter": 0,
      "turn": "0.000273590",
      "x": "167.315351814",
      "y": "279.026517299"
    },
    {
      "quarter": 2,
      "turn": "-0.000259015",
      "x": "164.963373285",
      "y": "270.527631680"
    },
    {
      "quarter": 0,
      "turn": "-0.001274537",
      "x": "83.766920617",
      "y": "123.269541908"
    },
    {
      "quarter": 0,
      "turn": "-0.000619162",
      "x": "158.885714770",
      "y": "270.478539804"
    },
    {
      "quarter": 3,
      "turn": "0.000504989",
      "x": "159.426726216",
      "y": "191.339646594"
    },
    {
      "quarter": 1,
      "turn": "0.000176852",
      "x": "159.435127942",
      "y": "183.339361852"
    },
    {
      "quarter": 3,
      "turn": "0.002292836",
      "x": "177.480524617",
      "y": "195.100521708"
    },
    {
      "quarter": 1,
      "turn": "-0.000677192",
      "x": "177.552057202",
      "y": "185.097773174"
    },
    {
      "quarter": 0,
      "turn": "-0.003955639",
      "x": "78.507473275",
      "y": "118.130374770"
    },
    {
      "quarter": 3,
      "turn": "0.000377883",
      "x": "70.917095799",
      "y": "26.162487094"
    },
    {
      "quarter": 1,
      "turn": "-0.000006583",
      "x": "71.065613118",
      "y": "13.138945970"
    },
    {
      "quarter": 2,
      "turn": "0.000000000",
      "x": "157.243612596",
      "y": "298.976101161"
    },
    {
      "quarter": 0,
      "turn": "0.012802168",
      "x": "141.907868478",
      "y": "297.894703145"
    },
    {
      "quarter": 2,
      "turn": "0.012802168",
      "x": "110.931589878",
      "y": "296.571527511"
    },
    {
      "quarter": 0,
      "turn": "0.012802168",
      "x": "93.941121834",
      "y": "295.981672693"
    },
    {
      "quarter": 2,
      "turn": "0.000179027",
      "x": "38.032280075",
      "y": "19.025648832"
    },
    {
      "quarter": 0,
      "turn": "-0.000081073",
      "x": "19.030578069",
      "y": "19.003219822"
    },
    {
      "quarter": 3,
      "turn": "-0.001044632",
      "x": "166.380971567",
      "y": "155.112785312"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "166.976101149",
      "y": "133.945101454"
    },
    {
      "quarter": 0,
      "turn": "-0.003809504",
      "x": "67.295138315",
      "y": "107.185278526"
    },
    {
      "quarter": 2,
      "turn": "-0.014089945",
      "x": "219.358524671",
      "y": "288.376778456"
    },
    {
      "quarter": 0,
      "turn": "-0.014089945",
      "x": "195.347095690",
      "y": "288.309445424"
    },
    {
      "quarter": 2,
      "turn": "0.010043848",
      "x": "52.009933069",
      "y": "287.479002821"
    },
    {
      "quarter": 0,
      "turn": "0.000378001",
      "x": "26.019648620",
      "y": "286.976108591"
    },
    {
      "quarter": 3,
      "turn": "0.000378001",
      "x": "117.048026809",
      "y": "157.682678893"
    },
    {
      "quarter": 1,
      "turn": "-0.008698621",
      "x": "117.897794825",
      "y": "129.687926533"
    },
    {
      "quarter": 2,
      "turn": "0.000378001",
      "x": "211.954185393",
      "y": "234.637710742"
    },
    {
      "quarter": 0,
      "turn": "0.000378001",
      "x": "181.954388271",
      "y": "234.358014317"
    },
    {
      "quarter": 3,
      "turn": "0.016258872",
      "x": "118.959203628",
      "y": "248.652877074"
    },
    {
      "quarter": 1,
      "turn": "0.000378001",
      "x": "119.967731462",
      "y": "216.684903060"
    },
    {
      "quarter": 3,
      "turn": "-0.008698621",
      "x": "123.503023786",
      "y": "68.581171677"
    },
    {
      "quarter": 1,
      "turn": "-0.008698621",
      "x": "122.911562312",
      "y": "34.586316576"
    },
    {
      "quarter": 3,
      "turn": "-0.014089945",
      "x": "277.003894878",
      "y": "274.977561152"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "276.976101161",
      "y": "237.991460769"
    },
    {
      "quarter": 3,
      "turn": "0.004006091",
      "x": "194.435668499",
      "y": "75.995669886"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "194.976101161",
      "y": "38.000000000"
    },
    {
      "quarter": 3,
      "turn": "0.005412301",
      "x": "272.460153645",
      "y": "79.994415677"
    },
    {
      "quarter": 1,
      "turn": "0.000000000",
      "x": "272.976101161",
      "y": "40.000000000"
    },
    {
      "quarter": 2,
      "turn": "0.000000000",
      "x": "271.976101149",
      "y": "160.991460769"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "229.976101149",
      "y": "160.991460769"
    },
    {
      "quarter": 3,
      "turn": "0.000378001",
      "x": "43.537711016",
      "y": "217.989332565"
    },
    {
      "quarter": 1,
      "turn": "0.000378001",
      "x": "43.999987430",
      "y": "173.989669473"
    },
    {
      "quarter": 0,
      "turn": "0.000000000",
      "x": "45.000000000",
      "y": "84.956417963"
    }
  ],
  "side": "312.976101161"
}

Submit side and placements. Entry k is the L with short side k, written {"x":"…","y":"…","quarter":0,"turn":"0"}. (x,y) is its bounding-box centre and concave corner. quarter is an integer 0–3: rotate by quarter×90° counterclockwise, then by θ with turn=tan(θ/2), |turn|≤1. Other values are decimal strings with at most nine places. · Verifier v1.0.0

DISCUSSION

Discussion

Discuss strategies, share construction methods, or ask questions. Any signed-in user can post under their public byline and unique #UID. New posts appear after moderation.