# Still Life

The maximum density still life problem aims to fill a given grid with live and dead cells with the maximum number of live cells which is stable under Conways game of Life, that is each live cell has 2 or 3 live neighbours, and each dead cell does not have exactly 3 live neighbours. See e.g. Neil Yorke-Smith's page on this

Our method is reported here.

• G. Chu, P.J. Stuckey, and M. Garcia de la Banda. Using relaxations in maximum density still life. In I. Gent, editor, Proceedings of the 15th International Co nference on Principles and Practice of Constraint Programming, volume 5732 of LNCS, page to appear. Springer-Verlag, 2009. LNCS, [PDF]
The results here were obtained using a strong mathematical proof of maximum density, and some very sophisticated lookahead search.

An optimal 69x69 maximal density still life

Note that the raw search space for 69x69 is 2^4761 or

• 159885601905968223810820371276001823211632449003523156243517984485496489191930378617690247544362806173077493423543719127007119866475407218431468665262141204317329369908102373325321958348792300953775141303887066104892715587626751331371614067273787247160719106225892831002158766460451699284334727610206474884397519442540225913173918317315842321623231007709677655020542557785850056387794760585470299307443607457326017164818049363906402358583853010433175271923097300840139400595117155022809775639245672681783143807796029972269629950237525207205174654684259000340271269121030540800249951408837538757876415509904310642441706835586181837186541870299145166985264012652164551160101184350405864045720781426444331891412153788971719461164978023188228874871441480093265336125589301872612533457751202895748795696267052487910880056768386984900659278408812501845751200552449684594326216404625377789802145720040476133729417945778746303467767258160510532961130721719933338603242473577376961308987654712512199969122005917860108289713712701494004754069672974248097904345693601287274199027410031936001631418583579496405953807693105672955164961732495982922628917658996092331069261447210916030154056988695637666936822145847637688981010025812472135178138310512098975816267120210256939629855611901906616976855964387953744528260022043000983400846041732079397023257499210274930282366753043312516552069852424217921408938615731162378726302164832056057402021117952