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
Newer Results
We have now shown that all maximum-density still life problems can be solved in constant time. This requires strong upper bounds, and a very powerful search construction, that allows us to find periodic solutions to the problem.
This is a fairly surprising result given when we started this the best known solution was size 20 which required days of computer time to determine.
Zip file contains optimal solutions
for sizes up to 246 and a C++ file to verify them.
The largest solution for each size mod 54 is periodic.
The results are reported here:
-
G. Chu and P.J. Stuckey.
A complete solution to the maximum density still life problem.
Artificial Intelligence, 184-185:1-16, 2012.
[DOI]
[PDF]