The best known packings of unequal circles with integer radii in a circle (complete up to N = 200)

(a.k.a. Al Zimmermann's Programming Contests — Circle Packing)

Last update: 01-Jun-2024

Overview    Download    Results    History of updates    References

Overview

5-16   17-28   29-40   41-52   53-64   65-76   77-88   89-100   101-112   113-124   125-136   137-148   149-160   161-172   173-184   185-196   197-199  

Download

You may download ASCII files which contain all the values of radius, ratio etc. by using the links given in the table header below.
All coordinates of all packings are packed as ASCII files here.
All packings are stored as nice PDF files here.
All contact graphs of all packings are stored as nice PDF files here.
  For industrial applications, for instance if a machine has to do an important job at every circle center,
it is useful to know a tour visiting each of the circle centers once which is of minimal length.
This problem is known as the "Traveling Salesman Problem" (TSP). Thus (very near) optimal tours are provided for every packing.
All optimal TSP tours of all packings are stored as nice PDF files here.

Results

The table below summarizes the current status of the search.
Please use the links in the following table to view a picture for a certain configuration.
Furthermore, note that for certain values of N several distinct optimal configurations exist; however, only one is shown here.
Proven optimal packings are indicated by a radius in bold face type.

Legend:
N
the number of circles; colors correspond to active researchers in the past, see "References" at the bottom of the page
radius
of the circles in the container circle, the latter has always a *radius* of 1
ratio
= 1/radius, that is the radius of the circumcircle if r1=1
density
ratio of total area occupied by the circles to container area
contacts
number of contacts between circles and container and between the circles themselves, respectively
loose
number of circles that have still degrees of freedom for a movement inside the container (so called "rattlers")
boundary
number of circles that have contact to the container (rattlers too if possible)
symmetry group
of the packing (Schönfliess notation); if field is empty then the packing has symmetry element C1
reference
for the best known packing so far
records
the sequence of N 's that establish density records

N radius ratio density contacts loose boundary symmetry group reference
5 0.555469288332912726151680670796 9.0013977460502193186724442369 0.678801486618359574874925328840 6 2 3 [1]
6 0.542640687119285146405066172629 11.0570403997020210854826907276 0.744326702607593955856345537543 6 3 3 [2]
7 0.519977897050211400703405101999 13.4621106776083764315332377163 0.772505752630743560253951417467 10 2 5 [3]
8 0.493165141800723187457958263481 16.2217466765577238862694843261 0.775237794465856115965982966557 12 2 6 [3]
9 0.467941000491664114240991109597 19.2331939080861235778775740411 0.770445707200305981724184447115 12 3 6 [3]
10 0.454541466713966414248671660658 22.0001930127373705480969665696 0.795440588105562775239159646548 10 5 5 [4]
11 0.440693929195813169647285638219 24.9606342889111573930522301689 0.812155673143821999571809733927 14 4 7 [3]
12 0.422961308500480205032821823426 28.3713894364084035738803015551 0.807517878593645503862777325949 12 6 5 [4]
13 0.412098358011784183482521850271 31.5458670175731632372815314804 0.822998351583734223662462586187 16 5 8 [4]
14 0.398909868871450694437712843067 35.0956471435694689934204714083 0.824061325180018150758827180416 22 3 8 [5]
15 0.386219726423057712445676696713 38.8379955082079014895321489365 0.822068620342639618860726645080 14 8 6 [5]
16 0.376841964344851976863372323169 42.4581164356691300262522275884 0.829870154970956586622391362763 18 7 8 [5]
17 0.367239298376272037806176780909 46.2913421171550719193324546440 0.832987866973478766427625311970 16 9 8 [5]
18 0.359139769580141767404896552932 50.1197626234576999176979901660 0.839573203593855160813591562608 20 8 8 [6]
19 0.350293089176941293991678913509 54.2402935914121110891998555840 0.839562225382431103658456789154 20 9 9 [5]
20 0.342462425680645332532671642332 58.4005674790451137175957605817 0.841487680797038211616426398803 28 6 9 [7]
21 0.335683774638203635767197094004 62.5588770938767424283505524151 0.846021288423517960375027297964 26 8 8 [6]
22 0.329537232965746151587437705236 66.7602862414238840346547484610 0.851481859754512636177852613321 26 9 8 [5]
23 0.323036150563399487834699570817 71.1994616078920572697738619542 0.852967072144088217800948114383 30 8 12 [6]
24 0.316835269443004585524303028344 75.7491425818594156785683988320 0.853966112879868827578707216532 26 11 8 [11]
25 0.311387317984121974663661276624 80.2858644399730530763868433683 0.857144626323887082150972473282 34 8 12 [7]
26 0.305960855060902876640212799372 84.9781910657315417438460174133 0.858710488148435305960837487471 34 9 9 [27]
27 0.300832427788693775910674291185 89.7509626820049367574045052549 0.860310064186599190989539212196 32 11 10 [11]
28 0.296215183170731171241142692466 94.5258771015174002402895866014 0.863332723968201257707616656901 28 14 8 [11]
29 0.291506764758227393371207455091 99.4831115636451565653560844725 0.864413006911845332486123253826 38 10 11 [11]
30 0.286970495600954771173459073685 104.5403637651876706526971386013 0.865154197601446248693893845556 46 7 17 [28]
31 0.282771273549458347189500637659 109.6292406611024402846984210880 0.866658816020869491478987777092 38 12 12 [27]
32 0.278746094616351172986469308201 114.7998146630280658706319765668 0.868047819744773082420385262311 40 12 14 [28]
33 0.274849612282160404130602734329 120.0656596383415122093683784325 0.869118084589028194674566946998 42 12 12 [11]
34 0.271203877317730414753088529664 125.3669392055450240112052104274 0.870720473133783950653740933380 34 17 8 [11]
35 0.267483732648500407269287295755 130.8490787587198728562644440850 0.870835860590020359724510341041 46 12 12 [29]
36 0.264107928757250450076964537585 136.3079108203854190329810808949 0.872235405952007494910898227277 44 14 17 [27]
37 0.260960824665625021137105202555 141.7837334297549560117945821974 0.874263843373715273023256453093 40 17 15 [27]
38 0.257710780360268649583517595600 147.4521164651227438870763146764 0.874753436318585896667640957548 48 14 12 [11]
39 0.254569617067667141722997522171 153.1997433520647173486889022157 0.875153761501592507856961370018 42 18 12 [30]
40 0.251644994145 158.9540858378 0.876262497596 48 16 11 [33]
41 0.248777002524725865680996353728 164.8062304148271232722632734814 0.877026542643754002760280829193 60 11 15 [30]
42 0.246048849400964322773103897565 170.6978110332727782855530366578 0.878070764466559246567182029286 52 16 14 [30]
43 0.243305345567353410740085259165 176.7326562420160752816061674124 0.878325566834702973893786280211 38 24 10 [30]
44 0.240736277435061192530713372670 182.7726193525985544027347875604 0.879187844202763123397055915046 60 14 15 [30]
45 0.238139377033909560837998028693 188.9649690046526026113116134280 0.879220663239616505802911665142 56 17 16 [30]
46 0.235651027881733206951683866339 195.2039013514769789307222793032 0.879448477326981018315769207397 58 17 16 [30]
47 0.233266603646794826811708073584 201.4861933308120086082237696547 0.879874773754303487919544684269 58 18 16 [30]
48 0.230990400293647676448562117446 207.8008434072574668445413186071 0.880568588809814251644358466490 66 15 15 [30]
49 0.228778537726880973280327441828 214.1809301119709366011234455489 0.881228284544309554433452513741 50 24 11 [30]
50 0.226690133359610792105167039311 220.5654002624026944333044663742 0.882339112379809818448104632137 62 19 16 [11,31]
51 0.223998263732029545238980636133 227.6803362235503898278720057038 0.878230359026795515865271143888 80 11 22 [27]
52 0.221804895915532620814052495305 234.4402714167434577378062928804 0.877511528708134436196831868011 54 25 13 [32]
53 0.219795841971804108543734892774 241.1328600419973183491019909887 0.877787439596505586107339837983 70 18 18 [32]
54 0.217914784274885969409700339306 247.8032877837345492569112470252 0.878653348664792240089678994920 75 16 19 [27]
55 0.215922488044482425717581803335 254.7210366928959729595317834267 0.878198756248712067034042323983 60 25 17 [32]
56 0.214034517772483646638471230653 261.6400409747337483944173416281 0.878176191888570355653964759721 64 24 13 [32]
57 0.212350545023433518009226761652 268.4240814814479494389540549061 0.879440552606922812366923327092 62 26 14 [32]
58 0.210548052519558969324317420171 275.4715577082436336145285732304 0.879348621102684411022284471618 70 23 15 [32]
59 0.208972369704959474221258739212 282.3339759380628391493504329348 0.880790627917397533197925791873 68 25 16 [32]
60 0.207366869873858936411521890104 289.3422658908722553442353546198 0.881640331060505654579232865264 90 15 24 [27]
61 0.205582562111718452777242136082 296.7177730125337648410607680065 0.880619431020590319060509873080 72 25 16 [32]
62 0.204096589402254819447858477219 303.7777367156485959947507254618 0.881818320482141612740903663775 76 24 18 [32]
63 0.202622167430488774360968197387 310.9235322024312853301599978185 0.882807081861940534587063201642 73 26 14 [32]
64 0.200916052386177175678554020608 318.5409987898166381923676085252 0.881456968730578357944238462642 80 24 15 [32]
65 0.199651070037238199332104498903 325.5680021543407397697474529152 0.883677726373345410127411671569 76 27 15 [32]
66 0.198053534066926058398855912479 333.2432330023323084306203797106 0.882666106560282455298791997174 74 29 16 [32]
67 0.196639430013694699419877082587 340.7251536242444937738302490381 0.882994180854469040856740025573 76 29 16 [32]
68 0.195295102320946233231796918719 348.1910155035501357785275192200 0.883674247773672456787189383571 80 28 17 [32]
69 0.194034910001329766207838193104 355.6061123203403295238763915214 0.884855278964857253510405525763 80 29 17 [32]
70 0.192552171910498202942558970150 363.5378365533954593350583850241 0.883741020958291624377750846008 76 32 16 [32]
71 0.191191206408750053729835507028 371.3559913849187110024199816846 0.883476011720916721570337014134 82 30 17 [32]
72 0.189996868920531123438231196159 378.9536133362019661537206617564 0.884504411950981630820478138874 84 30 16 [32]
73 0.188739638141125287630464929595 386.7761998431728344658266704012 0.884710496893569940498359386410 86 30 19 [32]
74 0.187500297289706179390529919916 394.6660409058595206063958513400 0.884847611668159048595691435765 84 32 19 [32]
75 0.186406648378084928421127250593 402.3461644344303601194164628631 0.886136899798682643665429417062 96 27 20 [32]
76 0.185280198375231132026673282640 410.1895435478977263885368811835 0.886901373358108940725956596748 84 34 17 [32]
77 0.183968479619359094486378186501 418.5499611635495179390770180490 0.885668428692454067206426939714 86 34 15 [32]
78 0.182929348986534629998269369195 426.3941266512764700317401197985 0.886844890547148296152163277536 94 31 21 [32]
79 0.181706101899453091310309540319 434.7680081966349111453925952814 0.886028706722635345237232150522 86 36 15 [32]
80 0.180701463717905454763536397156 442.7191587384630140672045981652 0.887141709678952192744941813626 90 35 20 [32]
81 0.179639258753198135759083382760 450.9036641666611690342820254354 0.887498640067152244053157660482 90 36 18 [32]
82 0.178497436226775607972191466453 459.3903516676927152275741515560 0.886871909060748670745793526762 92 36 15 [32]
83 0.177471742758796632858723468704 467.6800864732928869824737129588 0.887206760713257905309547212587 92 37 21 [32]
84 0.176543806733083628986407120643 475.8025872128128510207244939620 0.888341738036284609593240986601 92 38 17 [32]
85 0.175446697376529908570913746635 484.4776292230778363640636240442 0.887594863687446059863495044565 100 35 19 [32]
86 0.174540925344543629086093274608 492.7211187303841642025994357569 0.888607966216220728038409117065 106 33 21 [32]
87 0.173528350098608401146085643836 501.3589995557601432480942145286 0.888364290487272369881051534392 98 38 21 [32]
88 0.172577066504650922452977829834 509.9171157694259163752229012521 0.888577916087923660972934217326 98 39 18 [32]
89 0.171693075819886936860330496081 518.3668565257963131777239181128 0.889323657122077506694349210558 100 39 18 [32]
90 0.170809424642629805220272403379 526.9030101137535669028620171307 0.889917745545291031502339287286 122 29 23 [32]
91 0.169895251200599345620743093499 535.6241528643678535590317420655 0.890038420260707670452444053354 110 36 21 [32]
92 0.168977286396454159032792220507 544.4518725679485154427501877036 0.889963637109835806629332310671 120 32 22 [32]
93 0.168087147161939870910835629844 553.2844216244636015218820442983 0.890029237927230520079949426587 106 40 18 [32]
94 0.167174325043186127840030589593 562.2873008502770311329457755812 0.889703834561512864549369739804 96 46 17 [32]
95 0.166382367168049267942202242093 570.9739656729865073658827386586 0.890521362854521223413750344043 112 39 18 [32]
96 0.165530158046802785451622203372 579.9547413762300804891230833975 0.890555149596829525921836816624 109 41 16 [32]
97 0.164657504589081561683264767060 589.1016036109177711983594305787 0.890226998028333799093604373175 104 45 20 [32]
98 0.163855665395018858400491966273 598.0873457365311078098833861767 0.890526850573318971401386244807 106 45 18 [32]
99 0.163039975380447727469396721496 607.2130455674271093583099369802 0.890542875562178992932562555493 112 43 23 [32]
100 0.162372551557881277240466883341 615.8676392071894887456814587267 0.892054547472767887904850105175 118 41 19 [28]
101 0.161493306774669352809107295892 625.4129165917984282603968074403 0.891112714327161149966655511141 116 43 20 [32]
102 0.160629554949310542914898684997 635.0014480970695501976183464657 0.890206120242899736820026473348 112 46 22 [32]
103 0.159931395292599705321671960387 644.0261451577918125917540113425 0.891010171907312291849912161430 112 47 17 [32]
104 0.159204266087822373963681790035 653.2488265272372617539574979273 0.891374893563519813648330454894 114 47 21 [32]
105 0.158428886629058542612733670962 662.7579239753441568668801030169 0.891079621020456050205947954795 110 50 18 [32]
106 0.157646311711543566482577359427 672.3912462598908170110769872145 0.890581961569505864263502998419 116 48 17 [32]
107 0.156942707373990424018455503477 681.7774574579101633508313936363 0.890860017287736583101002795971 120 47 22 [32]
108 0.156290367089652046082601493612 691.0214750346610349704106289711 0.891611473335208766425102065480 126 45 24 [32]
109 0.155653446430991443774946045125 700.2736045958665644815970033303 0.892434875909814449074203430384 126 46 19 [32]
110 0.154907761883765549002649519476 710.0999889375335650861631031844 0.891903104250702156127562101843 116 52 17 [32]
111 0.154252639408152395753712400510 719.5987078463796227902745662858 0.892306105205994116180476220223 136 43 25 [32]
112 0.153639142040238393756653774162 728.9808997414667905078714368615 0.893090428880103344942089801734 116 54 18 [32]
113 0.152853875340193788780116557097 739.2681392506769670306716493628 0.891772185678773130814413337317 132 47 22 [32]
114 0.152219799068987927259290890583 748.9170311434570106890700679547 0.892112263838101649686787830900 124 52 20 [32]
115 0.151606970137029639151555721088 758.5403223615477134388502310703 0.892604794592917034094364347241 120 55 17 [32]
116 0.151030342058714713213707280191 768.0575864345438553061315746924 0.893430871934041940374431426216 130 51 19 [32]
117 0.150370098093992424309675510680 778.0802266077285737601760603592 0.893173282470225286608031740017 140 47 23 [32]
118 0.149754708202015871454976798364 787.9551929734359004192171090928 0.893352835517522526763245366108 128 54 20 [32]
119 0.149147113725694399724035407690 797.8699488537216701522852806655 0.893533093498579377203142863951 132 53 18 [32]
120 0.148458017355288646476407312073 808.3093263519535863540317755865 0.892641818950666023212272540916 126 57 23 [32]
121 0.147877008758280712284387475684 818.2475492034479461814314197649 0.892957517545823563994801776282 124 59 18 [32]
122 0.147313773519162609015717031409 828.1642448330210777980530337141 0.893401800568163231357071515980 126 59 19 [32]
123 0.146793659942018469461181952020 837.9108474343057689911070421553 0.894286910210663079694511954100 124 61 21 [32]
124 0.146180614363539976748841836691 848.2656919994980323017541472777 0.893955684124629628733954343108 149 48 23 [32]
125 0.145590955732923961835066207778 858.5698154856777285528163510522 0.893823558465227440159012430437 142 54 21 [32]
126 0.145036770954044133419738233510 868.7452097228773725958507425194 0.894043584426583542196896104288 142 55 23 [32]
127 0.144496938462873834662786708845 878.9113551539405680086390801494 0.894360211218747244022372795009 142 56 19 [32]
128 0.143915900018767396636262101281 889.4083279422782412361148939844 0.894085742814528100162600965602 144 56 24 [32]
129 0.143432226491456715962201821053 899.3794710959440783646856914637 0.894943536288507010292791568908 148 55 21 [32]
130 0.142854790445996395362997325791 910.0149851057608702971664589775 0.894554525672894929101201511691 142 59 24 [32]
131 0.142336141694855824893466215873 920.3565478179213230874047305112 0.894823769982417869364617867081 162 50 23 [32]
132 0.141782453512935231524481490546 931.0037788840863201028410160249 0.894576135171191377397473263032 162 51 24 [32]
133 0.141253016258578375668721204892 941.5728139675943711561701323059 0.894558257688705503545292304234 156 55 23 [32]
134 0.140832231734117076230320027312 951.4867324760149676444961069296 0.895847575669932462218599582626 142 63 20 [32]
135 0.140241267997571856942184185744 962.6267783198979313923848929833 0.894900683859299949450713008968 148 61 22 [32]
136 0.139694915221171401997622554160 973.5501094272368996612307654397 0.894446259724091394903305797117 148 62 16 [32]
137 0.139276536530620094081803264127 983.6545581378698693144469887988 0.895562457641456906733972572937 136 69 16 [32]
138 0.138750642787200714390900360404 994.5899869570192816938328096755 0.895229201529329068638471858585 156 60 24 [32]
139 0.138290013064586770786968753575 1005.1340434473864567912402934442 0.895669578519836720557153837767 152 63 26 [32]
140 0.137762197050335797560917427721 1016.2439551457396545532588891290 0.895171541848364990194337133347 155 62 22 [32]
141 0.137291384180533210348747066903 1027.0127352972863455709129761410 0.895346178137031966982587005517 164 59 23 [32]
142 0.136797147115220453755256246596 1038.0333434906893719787665047725 0.895149108269920746050888446222 168 57 22 [32]
143 0.136439103124116589388224567789 1048.0866315129253078805628167282 0.896674486690392705287522667515 160 63 25 [32]
144 0.135898981009612304667247606122 1059.6105940618841000819126297050 0.895745228030315651198725291774 152 68 23 [32]
145 0.135476035343384304070783668757 1070.2999953643150313991821222386 0.896296188378446253391936395646 180 55 23 [32]
146 0.134954038383758364261613338643 1081.8498041891202156369455226204 0.895473254038189318700631469079 164 64 21 [32]
147 0.134587673422287313255026671901 1092.2248394826419731952148783902 0.896655708178244121749469053755 157 68 19 [32]
148 0.134103401194930744147248210408 1103.6259981569696574586674554048 0.896209075506514184041922693956 166 65 21 [32]
149 0.133684695234017038983906262138 1114.5628879893341058330188951043 0.896578477215401575038870182262 167 65 21 [32]
150 0.133219386721164320165499114919 1125.9622468759629450602504885456 0.896263671756225256104119844993 162 68 22 [32]
151 0.132869815888846604016964384489 1136.4507355554730249977134451975 0.897450874774854873261343665336 198 52 30 [32]
152 0.132360230129877160524338299387 1148.3812006888436991610145347427 0.896419837957662889986328050134 182 61 26 [32]
153 0.131977546290039391201943750952 1159.2881084768827478403940104940 0.897049719259513748476220180589 172 65 23 [32]
154 0.131622973236294295159957515929 1170.0085191323984274421779364630 0.898010883406075423905042082167 162 73 24 [32]
155 0.131099686403160624530194896929 1182.3064131773786863025237091178 0.896613646378755334752275230216 175 67 21 [32]
156 0.130738721958733468419841232901 1193.2195577775345896611235787241 0.897380465857781675893699875707 168 72 24 [32]
157 0.130264188979871321073347855719 1205.2429852709553895823110714659 0.896534110377014025227772599652 182 66 25 [32]
158 0.129879275755952840013071801276 1216.5143290211046994210542750330 0.896866423978598065679590963578 172 71 19 [32]
159 0.129581929384707749906847164831 1227.0229402739850057573345015205 0.898361589762217203424420594861 168 75 26 [32]
160 0.129143332827059797391742072651 1238.9334896154601237700260736224 0.897849728520244124091004036958 182 69 27 [32]
161 0.128692648957193324525056640535 1251.0427076029259386031668839607 0.897114530731035517484911704903 207 56 27 [32]
162 0.128287399746944292237512475141 1262.7896451214704437174200657334 0.896959234639676093732078611458 170 77 26 [32]
163 0.127956003172316505277990998442 1273.8753630846866111745839706131 0.897788582381221742477159493649 186 70 25 [32]
164 0.127524654986691462509567699955 1286.0258278457222483256200889249 0.897166519528489470248569361469 176 76 19 [32]
165 0.127166905849772709644114868383 1297.5073891859963888258092197161 0.897530252628614894282309652667 194 68 27 [32]
166 0.126800820942490971425718910680 1309.1397892075742754478435990339 0.897729500389611959206708820963 197 67 23 [32]
167 0.126414229048950522527458226970 1321.0538185170098636340881883560 0.897590584015928952764467286819 184 75 23 [32]
168 0.126051280677346592986388921683 1332.7909014270908137950040706756 0.897740045685333570343896074242 184 75 25 [32]
169 0.125694928810895513702096327724 1344.5252055813305588170612891751 0.897937640898783164531357300036 202 68 26 [32]
170 0.125352179372426606907439900141 1356.1790536957705112819893371726 0.898284892331195621567967064951 198 71 28 [32]
171 0.124969070585008889203312044438 1368.3385752931486968232420896899 0.898008166175013237681761867980 181 80 26 [32]
172 0.124607557201400145694765616993 1380.3336158977950964145892539760 0.897995717111266465733998140241 180 82 25 [32]
173 0.124292372480062058398122471861 1391.8794576694656894079865750932 0.898608092371089005585847691389 192 77 24 [32]
174 0.123969922667450810222682501234 1403.5662542660030582978075853678 0.899074411806571663660991011877 200 74 27 [32]
175 0.123588466515828274481244282088 1415.9897353980626161867216160193 0.898641296216213324931793093536 189 80 25 [32]
176 0.123206367490535413545088119265 1428.4975978495603241892600040631 0.898153073406713832040689872242 194 79 28 [32]
177 0.122863416111476869905296191556 1440.6241141740982770801479192737 0.898191645747825943217180748934 193 79 26 [32]
178 0.122525630041295760269892150741 1452.7572716011114081324691251900 0.898263769360865167874005577489 188 84 25 [32]
179 0.122199906679333233044598532686 1464.8129025967001568196057468391 0.898471738338293727512431856593 186 86 24 [32]
180 0.121904492604172466745295738175 1476.5657618908712677031238014664 0.899086431595715378714091202050 209 75 28 [32]
181 0.121556667930141056680657910577 1489.0174523706193214071173329317 0.898888369943455691224182415367 196 83 23 [32]
182 0.121245439762024708950127481691 1501.0873840469522574198685671551 0.899191394515458139752291600408 211 76 29 [32]
183 0.120870519781739939722653380815 1514.0168200686933621954275020051 0.898508782688755632419952176640 204 81 30 [32]
184 0.120585744278797836519611514194 1525.8851790522311932901280931310 0.899126831013711496111767724941 202 83 24 [32]
185 0.120334876375475070406978065268 1537.3764080062166263572563590318 0.900216372507742083110000079063 234 68 26 [32]
186 0.119937387748624434484926121579 1550.8091637766492842941855489096 0.899073951012061876142837498257 198 87 26 [32]
187 0.119639537227291634715466688660 1563.0284463967518472735820894710 0.899385142772919176354621213564 214 79 24 [32]
188 0.119304315355531672198182260048 1575.8021781504920132068791465547 0.899096610380055912212311830231 218 78 30 [32]
189 0.118991640252963767529175746769 1588.3468754460883995208657440120 0.899109649480630250932274039614 202 88 24 [32]
190 0.118700300161507570136237414528 1600.6699203075282082772017839825 0.899408786436276001110731872289 214 83 27 [32]
191 0.118391871742731808035718705143 1613.2864291143844970942714588340 0.899412995667145809788702947156 221 80 31 [32]
192 0.118068399897810202904002670910 1626.1760146337089092237744970350 0.899151585832781086089778998516 230 77 26 [32]
193 0.117756301627260061796338742344 1638.9781042114637506274176245146 0.899026410710239516742009053928 208 89 25 [32]
194 0.117491404843022711966554467719 1651.1846143911419121226099637727 0.899587528118795958067912840743 217 82 29 [32]
195 0.117221906665761418759282254385 1663.5115870961709635769605117377 0.900045633277770345255290967854 223 83 25 [32]
196 0.116886629337379723364390840747 1676.8384982192333679503620802129 0.899458488850658500679380364381 225 83 25 [32]
197 0.116642480098270235423909681748 1688.9215647166390857154097344312 0.900239987364981833627041136534 227 83 27 [32]
198 0.116354188738006755500522958298 1701.7006619833350185606280832852 0.900308162125594939845834821986 230 83 24 [32]
199 0.116055554722143450265025240402 1714.6960391205705342951402257877 0.900182214566818882090816904251 233 82 27 [32]
200 0.115859958962875338092411801136 1726.2219129914020157496856407510 0.901624957379125803883622701788 228 86 24 [26,31]



Updates

Please note that the results are taken from a running search. For updates look at the list below.

23-Mar-2011: First complete presentation from N=1 to N=100.
31-Mar-2011: André Müller [26] sent me three excellent packings for N=60, 100 and 200. The last is the densest circle packing I have ever seen!
19-Jan-2012: What a surprise! Tao Ye [27] sent me twelve improved packings for N=26, 31, 32, 35, 36, 37, 39, 40, 43, 44, 47 and 48. After the long time since Al Zimmermann's contest has been finished it is unbelievable that such improvements are possible. Great result!
20-Jan-2012: Some of the new record packings, namely for N=35, 36, 37, 39 and 40, could be improved by applying simple exchange heuristics. Nevertheless, the credits should be given to Tao Ye and Wenqi Huang. For comparison, see here.
08-Mar-2012: Better packings were found for N=58, 63, 64, 67, 69, 71, 75, 78, 79, 80, 81, 82, 83, 84, 86, 88, 94 and 99 by Eckard Specht [31].
08-Mar-2012: Zhanghua Fu and Wenqi Huang [28] sent me two nice improvements for N=30 and 100.
08-Mar-2012: Unbelievable how some packings of this old famous contest can be improved nowadays, today for N=35, 36, 37, 39, 40, 42 and 46 by Tao Ye and Wenqi Huang [27].
09-Mar-2012: Some minor improvements for N=52, 54, 61, 63, 70, 78, 79, 84 and 85 by Eckard Specht [31].
09-Mar-2012: Further astonishing improvements for N=32, 36, 37, 41 and 60 by Zhanghua Fu and Wenqi Huang [28].
09-Mar-2012: A tiny improvement for N=60. The credits should be given to Zhanghua Fu and Wenqi Huang [28].
11-Mar-2012: Three new records for N=40, 43 and 45 by Tao Ye and Wenqi Huang [27].
13-Mar-2012: Nearly all of the packings in the range 51 ≤ N ≤ 100, namely for N=51, 52, 53, 55, 56, 57, 58, 59, 62, 64, 65, 66, 67, 68, 70, 72, 73, 74, 75, 76, 77, 83, 85, 86, 87, 88, 89, 90, 91, 92, 93, 95, 96, 97, 98 and 99, could be improved by Zhanghua Fu and Wenqi Huang [28]. That's great!
14-Mar-2012: But all these packings are still far from the putative optima, so improvements were found for N= 51, 52, 53, 55, 56, 57, 60, 62, 63, 64, 65, 66, 67, 68, 70, 72, 73, 74, 77, 79, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 96, 97, 98 and 99 by Eckard Specht [31].
14-Mar-2012: Again, three new records for N=41, 46 and 48 by Tao Ye and Wenqi Huang [27]. Tao Ye was the first who sent me the coordinates in the new format right off, thanks!
22-Mar-2012: Yet another record for N=36 by Tao Ye and Wenqi Huang [27], but ...
23-Mar-2012: ... this was not the last word: a better packing by Tao Ye and Wenqi Huang [27].
18-Apr-2012: An essential improvement for N=35 by Tao Ye and Wenqi Huang [27].
24-Sep-2012: Four new record packings for N=41, 42, 45 and 46 by Tao Ye and Wenqi Huang [27].
27-Sep-2012: More new record packings for N=35, 37, 39 and 44 by Zhizhong Zeng, Wenqi Huang and Zhanghua Fu [29].
02-Oct-2012: Motivated by a question Tao Ye and Wenqi Huang [27] came up with 48 new record packings for N=51–99 (except N=58). Great!
17-Dec-2012: Two new record packings for N=41 and 43 went to Zhizhong Zeng, Wenqi Huang and Zhanghua Fu [29].
05-Feb-2013: Five new record packings for N=37, 39, 43, 44 and 49 by Tao Ye and Wenqi Huang [27].
06-Mar-2013: Four new record packings for N=45, 46, 47 and 48 by Zhizhong Zeng, Wenqi Huang and Zhanghua Fu [29].
21-Mar-2013: A new record packing once more for N=48 by Zhizhong Zeng, Wenqi Huang and Zhanghua Fu [29].
25-Mar-2013: Four new record packings for N=45, 46, 47 and 48 by Tao Ye and Wenqi Huang [27].
17-Jul-2014: After 16 months, all packings for N=39–49 are completely better than before. They are found by Zhizhong Zeng, Kun He, Xinguo Yu, Wenqi Huang, Zhanghua Fu (their work is partly inspired by Tao Ye et el.) [30].
16-Jun-2015: Some small improvements by rearrangements of circles for N=55, 56, 59, 68, 69, 72, 74, 75, 76, 78, 79, 81, 86, 87, 88, 90, 91, 93, 95, 96, 97, 98, 99 and 100 by Eckard Specht [31].
21-Oct-2015: What a sensation! André Müller [33] found lots of new records, namely for N=52, 53, 55–59, 61–99, 101–199, which are not only a little bit better than the previous, but significantly better. It seems that all other people will have no chance to beat these results for years (except for small improvements by rearrangements). So, congratulation André, for these milestones!
01-Jun-2024: Significant improvement for N= 40 by Jianrong Zhou, Jiyao He, and Kun He [33].

References

[1]   Klaus Nagel, Hugo Pfoertner, Al Zimmermann's Programming Contests — Circle Packing.
[2]   Fred Mellender, Al Zimmermann's Programming Contests — Circle Packing.
[3]   Gerrit de Blaauw, Al Zimmermann's Programming Contests — Circle Packing.
[4]   Steve Trevorrow, Al Zimmermann's Programming Contests — Circle Packing.
[5]   Tomas Rokicki, Al Zimmermann's Programming Contests — Circle Packing.
[6]   Boris von Loesch, Al Zimmermann's Programming Contests — Circle Packing.
[7]   Bernardetta Addis, Marco Locatelli, Fabio Schoen, Al Zimmermann's Programming Contests — Circle Packing.
[8]   Tobias Baumann, Al Zimmermann's Programming Contests — Circle Packing.
[9]   François Glineur, Al Zimmermann's Programming Contests — Circle Packing.
[10]   Paul Khuong, Joonas Pihlaja, Barkley Vowk, Al Zimmermann's Programming Contests — Circle Packing.
[11]   André Müller, Johannes Josef Schneider, Elmar Schömer, Packing a multidisperse system of hard discs in a circular environment, Phys. Rev. E 79, 021102 (2009).
[12]   Wenqi Huang, Ruchu Xu, Two personification strategies for solving circles packing problem, Science in China (Series E) 42 (1999), 595–602.
[13]   Huaiqing Wang, Wenqi Huang, Quan Zhang, Dongmin Xu, An improved algorithm for the packing of unequal circles within a larger containing circle, European Journal of Operational Research 141 (2002), 440–453.
[14]   Wenqi Huang and Yan Kang, A Short Note on a Simple Search Heuristic for the Diskspacking Problem, Annals of Operations Research 131 (2004), 101–108.
[15]   De-fu Zhang, Xin Li, A Personified Annealing Algorithm for Circles Packing Problem, Acta Automatica Sinica 31 (2005), 590–595.
[16]   De-fu Zhang, An-sheng Deng, An effective hybrid algorithm for the problem of packing circles into a larger containing circle, Computers & Operations Research 32 (2005), 1941–1951.
[17]   Hakim Akeb, Yu Li, A hybrid heuristic for packing unequal circles into a circular container, Service Systems and Service Management, 2006 Int. Conf. on (2006), 922–927.
[18]   Wen Qi Huang, Yu Li, Chu Min Li, Ru Chu Xu, New heuristics for packing unequal circles into a circular container, Computers & Operations Research 33 (2006), 2125–2142.
[19]   Zhipeng Lü, Wenqi Huang, PERM for solving circle packing problem, Computers & Operations Research 35 (2008), 1742–1755.
[20]   Ignacio Castillo, Frank J. Kampas, János D. Pintér, Solving circle packing problems by global optimization: Numerical results and industrial applications, European Journal of Operational Research 191 (2008), 786–802.
[21]   Mhand Hifi, Rym M'Hallah, Adaptive and restarting techniques-based algorithms for circular packing problems, Comput. Optim. Appl. 39 (2008), 17–35.
[22]   Bernardetta Addis, Marco Locatelli, Fabio Schoen, Efficiently packing unequal disks in a circle, Operations Research Letters 36 (2008), 37–42.
[23]   A. Grosso, A. R. M. J. U. Jamali, M. Locatelli, F. Schoen, Solving the problem of packing equal and unequal circles in a circular container, J. Glob. Optim. 47 (2010) 1, 63–81.
[24]   Jingfa Liu, Shengjun Xue, Zhaoxia Liu, Danhua Xu, An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle, Computers & Industrial Engineering 57 (2009), 1144–1149.
[25]   I. Al-Mudahka, Mhand Hifi, Rym M'Hallah Packing circles in the smallest circle: an adaptive hybrid algorithm, J. Operational Research Society 62 (2010), 1917–1930.
[26]   , private communication, March 2011.
[27]   , private communication, January 2012–February 2013.
[28]   , private communication, March 2012.
[29]   , private communication, September 2012–March 2013.
[30]   Zhizhong Zeng, Kun He, Xinguo Yu, Wenqi Huang, Zhanghua Fu, private communication, July 2014.
[31]   , program ccin, 2005–2024.
[32]   , private communication, October 2015.
[33]   , Solution-Hashing Search Based on Layout-Graph Transformation for Unequal Circle Packing, submitted to European Journal of Operational Research, under review, May 2024.
[34]   Eckard Specht, A precise algorithm to detect voids in polydisperse circle packings, Proc. R. Soc. A 471 (2015), 20150421.

Datenschutzerklärung der Otto-von-Guericke-Universität Magdeburg nach DSGVO

©  E. Specht    01-Jun-2024