|
Here is a collated summary of all the results I know for the maximum
density still life problem. If you have any further results I can include,
please do let me
know.
[ Problem Statement | Results | Rotational Symmetry | Bilateral
Symmetry | Bibliography ]
..OO.OO..
.O.O.O.O.
O..O.O..O
OOOO.OOOO
.........
OOOO.OOOO
O..O.O..O
.O.O.O.O.
..OO.OO..
A maximal density rotationally symmetric still life of size 9
Problem Statement
In a given, finite region of the board, construct a maximum density
still life, i.e. a pattern that does not change from one generation to
the next. We restrict our attention to square boards of size n.
Note the still life need not be connected (a `pseudo still life' in some
terminologies); a still life is also known as a `stable pattern'.
Results: Main Case
In the results tables, density for size n refers to the
value of the maximal pattern divided by n*n; external
density is the value divided by (n+1)*(n+1), i.e. the
external board. Solutions denotes the number of non-symmetric solutions;
the number of total solutions is in parenthesis. Times are approximate and
for indication only, and show the time to determine the optimal value with
the current best-known method.
| Size |
Value |
Density (external) |
Solutions (total) |
Time (s) |
Reference |
Date (proved optimal) |
Remarks |
| 1 |
0 |
0.0000 (0.0000) |
- |
- |
- |
- |
|
| 2 |
4 |
1.0000 (0.4444) |
1 (1) |
- |
- |
- |
|
| 3 |
6 |
0.6667 (0.3750) |
1 (2) |
- |
- |
- |
|
| 4 |
8 |
0.5000 (0.3200) |
2 |
- |
- |
- |
|
| 5 |
16 |
0.6400 (0.4444) |
1 (1) |
- |
- |
- |
|
| 6 |
18 |
0.5000 (0.3673) |
9 (48) |
- |
[14] |
September 1992 |
Attributed to Harold McIntosh |
| 7 |
28 |
0.5714 (0.4375) |
1 (2) |
- |
[14] |
September 1992 |
Attributed to Harold McIntosh |
| 8 |
36 |
0.5625 (0.4444) |
1 (1) |
- |
[1] |
May 1999 |
|
| 9 |
43 |
0.5309 (0.4300) |
10 (76) |
- |
[1] |
May 1999 |
|
| 10 |
54 |
0.5400 (0.4463) |
>100 (3590) |
- |
[1] |
May 1999 |
|
| 11 |
64 |
0.5289 (0.4444) |
1? (73) |
- |
[3] |
December 2001 |
First novel result by hybrid CP-IP |
| 12 |
76 |
0.5278 (0.4497) |
? (129126) |
- |
[3],[11] |
December 2001 |
Number of solutions by bucket elimination |
| 13 |
90 |
0.5325 (0.4592) |
? (1682) |
2 |
[3] |
December 2001 |
|
| 14 |
104 |
0.5306 (0.4622) |
>1 (11) |
2 |
[5] |
January 2002 |
|
| 15 |
119 |
0.5289 (0.4648) |
? |
58 |
[5] |
February 2002 |
|
| 16 |
136 |
0.531 (0.4710) |
? |
7 |
[11] |
July 2003 |
First novel result by hybrid BE |
| 17 |
152 |
0.526 (0.469) |
? |
1090 |
[11] |
July 2003 |
|
| 18 |
171 |
0.528 (0.474) |
? |
2030 |
[11] |
July 2003 |
|
| 19 |
190 |
0.526 (0.475) |
? |
56020 |
[11] |
July 2003 |
|
| 20 |
210 |
0.525 (0.476) |
? |
200000 |
[11] |
July 2003 |
|
(These results last updated 04aug03.) Top
OO..OO.OO.O.OO.OO.OO
O..O.O.O.OOO.O.OO.O.
.O.O.O.O.....O.....O
OO.O.O.OOOOOO.OOOOOO
.O.O.O......O.O.....
O..O.OOOOOO.O.O.OOOO
OOOO......O.O.O.O..O
....OOOOO.O.O.O.O.O.
OOOO....O.O.O.O.O.OO
O..O.OO.O.O.O.O.O.O.
.O.O.O.O.O.O.OO.O..O
OO.O.O.O.O.O....OOOO
.O.O.O.O.O.OOOOO....
O..O.O.O.O......OOOO
OOOO.O.O.OOOOOO.O..O
.....O.O......O.O.O.
OOOOOO.OOOOOO.O.O.OO
O.....O.....O.O.O.O.
.O.OO.O.OOO.O.O.O..O
OO.OO.OO.O.OO.OO..OO
A maximal density still life of size 20 (due to Larrosa et al)
Rotationally Symmetric Case
First, with 90 degree rotational symmetry. Times are approximate and
for indication only, and show the time to determine the optimal value with
the method that first solved the instance.
| Size |
Value |
Density (external) |
Solutions |
Time (s) |
Reference |
Date (proved optimal) |
Remarks |
| 1 |
0 |
0.0000 (0.0000) |
- |
- |
- |
- |
|
| 2 |
4 |
1.0000 (0.4444) |
1 |
- |
- |
- |
Identical to main case |
| 3 |
4 |
0.4444 (0.2500) |
1 |
- |
- |
- |
|
| 4 |
8 |
0.5000 (0.3200) |
1 |
- |
- |
- |
Unique, unlike main case |
| 5 |
16 |
0.6400 (0.4444) |
1 |
- |
- |
- |
Identical to main case |
| 6 |
18 |
0.5000 (0.3673) |
1 |
- |
- |
- |
Unique, unlike main case |
| 7 |
28 |
0.5714 (0.4375) |
1 |
- |
- |
- |
Identical to main case |
| 8 |
36 |
0.5625 (0.4444) |
1 |
2 |
[1] |
May 1999 |
Identical to main case |
| 9 |
40 |
0.4939 (0.4000) |
? |
? |
|
? |
|
| 10 |
52 |
0.5200 (0.4298) |
? |
? |
|
? |
|
| 11 |
64 |
0.5289 (0.4444) |
1? |
? |
|
? |
Identical to main case |
| 12 |
76 |
0.5278 (0.4497) |
? |
? |
|
? |
Value as main case |
| 13 |
88 |
0.5207 (0.4490) |
? |
? |
[1] |
May 1999 |
|
| 14 |
104 |
0.5306 (0.4622) |
? |
? |
|
? |
Value as main case |
| 15 |
116 |
0.5156 (0.4531) |
? |
? |
[1] |
May 1999 |
|
| 16 |
136 |
0.5313 (0.4706) |
? |
? |
|
? |
|
| 17 |
148 |
0.5121 (0.4568) |
? |
? |
|
? |
|
| 18 |
168 |
0.5185 (0.4653) |
>1 |
19,900 |
[15] |
January 2002 |
|
| 19 |
188 |
0.5208 (0.4700) |
? |
3,860 |
[17] |
April 2002 |
|
| 20 |
208 |
0.5200 (0.4717) |
? |
11,500 |
[17] |
April 2002 |
|
| 21 |
232 |
0.5261 (0.4793) |
? |
33,500 |
[17] |
April 2002 |
|
| 22 |
252 |
0.5207 (0.4764) |
? |
98,300 |
[17] |
April 2002 |
|
| 23 |
276 |
0.5217 (0.4792) |
? |
332,000 |
[17] |
September 2002 |
|
| 24 |
>295 |
? |
? |
|
|
|
|
(These results last updated 23oct02.) Top
Second, with 180 degree rotational symmetry (all results up to size 16
due to Bob Bosch):
| Size |
Value |
Density (external) |
Solutions |
Time (s) |
Reference |
Date (proved optimal) |
Remarks |
| 10 |
54 |
0.5400 (0.4463) |
? |
? |
[6] |
October 2002 |
|
| 11 |
64 |
0.5289 (0.4444) |
1? |
? |
[6] |
October 2002 |
Also has 90 degree rotational |
| 12 |
76 |
0.5278 (0.4497) |
? |
? |
[6] |
October 2002 |
Value as main case |
| 13 |
90 |
0.5325 (0.4592) |
? |
? |
[6] |
October 2002 |
|
| 14 |
104 |
0.5306 (0.4622) |
? |
? |
[6] |
October 2002 |
Value as main case; also has 90 degree |
| 15 |
119 |
0.5289 (0.4648) |
? |
? |
[6] |
October 2002 |
|
| 16 |
136 |
0.5313 (0.4706) |
? |
? |
[6] |
October 2002 |
Value as 90 degree rotational |
| 17 |
152 |
0.5260 (0.4691) |
? |
1,000,000 |
[17] |
November 2002 |
|
(These results last updated 27nov02.) Top
OO.OO.OO.O.OO.O.OO.OO.O
.O.OO.O.OOO.O.OO.O.O.OO
O.....O.....O....O.O...
OOOOOO.OOOOO.OOOOO.O.OO
.....O.O...O.O.....O.OO
OOOO.O..OO.O.O.OOOOO...
O..O.OO.O.O.O.O.O...OOO
.O.O.O..O.O.O.O...OO..O
OO.O..OOO.O.O.OOOO.O.O.
...OOO...O.O.O...O.O.OO
OOO...OOO..O..OOO..O.O.
O..OOO...OO.OO...OOO..O
.O.O..OOO..O..OOO...OOO
OO.O.O...O.O.O...OOO...
.O.O.OOOO.O.O.OOO..O.OO
O..OO...O.O.O.O..O.O.O.
OOO...O.O.O.O.O.OO.O..O
...OOOOO.O.O.OO..O.OOOO
OO.O.....O.O...O.O.....
OO.O.OOOOO.OOOOO.OOOOOO
...O.O....O.....O.....O
OO.O.O.OO.O.OOO.O.OO.O.
O.OO.OO.O.OO.O.OO.OO.OO
A maximal density 90 degree rotationally symmetric still life of size 23
Bilaterally Symmetric Case
With horizontal (or vertical, but not necessarily both) symmetry.
| Size |
Value |
Density (external) |
Solutions (total) |
Time (s) |
Reference |
Date (proved optimal) |
Remarks |
| 1 |
0 |
0.0000 (0.0000) |
- |
- |
- |
- |
|
| 2 |
4 |
1.0000 (0.4444) |
1 (1) |
- |
- |
- |
Identical to main case |
| 3 |
4 |
0.4444 (0.2500) |
1 (1) |
- |
- |
- |
|
| 4 |
8 |
0.5000 (0.3200) |
1 |
- |
- |
- |
Unique, unlike main case |
| 5 |
16 |
0.6400 (0.4444) |
1 |
- |
- |
- |
Identical to main case |
| 6 |
16 |
0.4444 (0.3265) |
? |
- |
- |
- |
|
| 7 |
26 |
0.5306 (0.4063) |
? |
- |
- |
- |
|
| 8 |
36 |
0.5625 (0.4444) |
1 |
2 |
- |
- |
Identical to main case |
| 9 |
43 |
0.5309 (0.4300) |
1 |
51 |
- |
- |
Unique, unlike main case |
| 10 |
52 |
0.5200 (0.4298) |
? (133) |
4.5 |
[10] |
- |
|
| 11 |
64 |
0.5289 (0.4444) |
1? |
373 |
[3] |
December 2001 |
Identical to main case |
| 12 |
76 |
0.5278 (0.4497) |
? (8) |
30,360 |
[10] |
- |
|
| 13 |
90 |
0.5325 (0.4592) |
? |
? |
- |
- |
|
| 14 |
104 |
0.5306 (0.4622) |
1 |
? |
[3],[10] |
December 2001 |
Value as main case |
| 15 |
119 |
0.5289 (0.4648) |
? |
? |
[3] |
December 2001 |
Value as main case |
| 16 |
136 |
0.5313 (0.4706) |
? (3) |
? |
[3] |
December 2001 |
|
| 17 |
152 |
0.5260 (0.4691) |
? |
? |
[3] |
December 2001 |
Greater than rotational case |
| 18 |
170 |
0.5247 (0.4709) |
? (4) |
? |
[3],[10] |
December 2001 |
Greater than rotational case |
| 19 |
189 |
0.524 (0.472) |
? |
? |
[11] |
July 2003 |
|
| 20 |
208 |
0.52 (0.4717) |
? (1813) |
? |
[10] |
March 2003 |
First novel result by bucket elimination |
| 21 |
232 |
0.526 (0.479) |
? |
? |
[11] |
July 2003 |
|
| 22 |
252 |
0.5207 (0.4764) |
? (635) |
? |
[10] |
March 2003 |
|
| 23 |
? |
? (?) |
? |
? |
- |
|
|
| 24 |
300 |
0.5208 (0.48) |
? (5363) |
? |
[10] |
March 2003 |
|
| 25 |
? |
? (?) |
? |
? |
- |
|
|
| 26 |
350 |
0.5178 (0.4801) |
? (55246) |
? |
[10] |
March 2003 |
|
| 27 |
? |
? (?) |
? |
? |
- |
|
|
| 28 |
406 |
0.5179 (0.4828) |
? (12718) |
? |
[10] |
March 2003 |
|
(These results last updated 04aug03.) Top
O.OO.OO.O.OO.OO.OO.O.OO.OO.O
OO.O.O.OOO.O.OO.O.OOO.O.O.OO
...O.O.....O....O.....O.O...
OO.O.OOOOOO.OOOO.OOOOOO.O.OO
OO.O......O.O..O.O......O.OO
...OOOOOO.O.O..O.O.OOOOOO...
OOO.....O.O.OOOO.O.O.....OOO
O..OOOO.O.O......O.O.OOOO..O
.O.O..O.O.OOOOOOOO.O.O..O.O.
OO.O..O.O..........O.O..O.OO
.O.OOOO.OOOOOOOOOOOO.OOOO.O.
O......O............O......O
OOOOOO.O.OOOOOOOOOO.O.OOOOOO
.....O.O.O........O.O.O.....
OOOO.O.O.O.OOOOOO.O.O.O.OOOO
O..O.O.O.O.O....O.O.O.O.O..O
.O.O.O.O.O.O.OO.O.O.O.O.O.O.
OO.O.O.O.O.O.OO.O.O.O.O.O.OO
...O.O.O.O.O....O.O.O.O.O...
OOOO.O.O.O.OOOOOO.O.O.O.OOOO
O....OO.O.O......O.O.OO....O
..OOO...O.O.OOOO.O.O...OOO..
.OO..OOOO.O.O..O.O.OOOO..OO.
O...O.....O.O..O.O.....O...O
OOOO.OOOOOO.OOOO.OOOOOO.OOOO
...O.O.....O....O.....O.O...
OO.O.O.OOO.O.OO.O.OOO.O.O.OO
O.OO.OO.O.OO.OO.OO.O.OO.OO.O
A maximal density bilaterally symmetric still life of size 28 (due to
Larrosa et al)
Bibliography
-
R. Bosch, Integer Programming and Conway's Game of Life.
SIAM Review 41(3), 596-604, (1999).
Online
-
R. Bosch, Maximum Density Stable Patterns in Variants of Conway's Game of Life.
Operations Research Letters 27(1), 7-11, (2000).
PDF
-
R. Bosch and M. Trick, Constraint Programming and Hybrid Formulations
for Life. Proceedings of Formul'01 Workshop, CP'01, (2001).
Postscript
- R. Bosch and M. Trick, Constraint Programming and Hybrid Formulations
for Three Life Designs. Proceedings of CP-AI-OR'02, 77-91,
(2002).
PDF
-
R. Bosch and M. Trick, CP/IP
Life page.
-
R. Bosch, private communication, October 2002.
-
M. Cook, Still Life Theory. New Constructions in Cellular
Automata, 93-118, OUP (2003). Postscript.
- N. D. Elkies, The still-life density problem and its
generalizations. Voronoi's Impact on Modern Science, Book I,
228-253, (1998). Online
- I. Gent, T. Walsh and B. Selman, CSPlib problem 32.
-
J. Larrosa and E. Morancho, Solving 'Still life' with Soft
Constraints and Bucket Elimination. Proceedings of CP'03,
466-479, (2003).
Postscript | Online.
-
J. Larrosa, E. Morancho and D. Niso, On the Practical Use of Bucket
Elimination: 'Still life' as a Case Study. JAIR 23:421--440.
PDF.
- M. D. Niemiec, Mark
D. Niemiec's Life Page.
- K. Petrie, B. Smith and N. Yorke-Smith,
Dynamic Symmetry Breaking in Constraint Programming and Linear
Programming Hybrids. APES Technical Report 81, (2004). Proceedings of
STAIRS'04, Valencia, Spain, August 2004. Online.
-
S. Silver, Dense
Stable Patterns.
-
B. M. Smith, A Dual Graph Translation of a Problem in 'Life'.
Proceedings of CP'02, 402-414, LNCS 2470, (2002). Postscript | Online
- E. Weisstein, Density,
Eric Weisstein's Treasure Trove of Life C.A.
-
N. Yorke-Smith, Symmetric Still Life with a Hybrid Model.
Working paper, IC-Parc (2002).
- Kenil C.K. Cheng and Roland H.C. Yap,
Search Space Reduction and Russian Doll Search.
AAAI'07.
|