Still life with all 3x3 windows

[pcallahan]

I don't know if this has been constructed before. It's not an intrinsically interesting pattern, but it satisfied my curiosity and was a good SAT solver application. It's a 14x14 still life that uses all 51 3x3 still life neighborhoods up to D4 symmetry. It's not proven minimal so maybe someone can improve it. This was the first size where the solver finished in a few minutes.

Code: Select all

x = 14, y = 14, rule = B3/S23
10bob2o$2ob2o3b3ob2o$bobo3bo$o2bo2bo2b2ob2o$2obobob2obobo$3bo2bo5bo$2o
2bobob2o2b2o$ob3obo2bo3bo$bo5bo2b3o$2b4ob2obo$5bobo2bo$2b2obobobob2o$b
obob2o2bo3bo$b2o6b2ob2o!

Screenshot 2026-07-14 224515.png (5.28 KiB) Viewed 306 times

You can verify for yourself that all are present, but here is the breakdown generated by a script that Claude wrote. I have only spot checked it.

all_51_orbits (1).png (114.46 KiB) Viewed 306 times

I actually didn't use Claude to generate the SAT problem. I tried but it was easier to implement my idea than explain it. I'll post more when I have time. The idea is:

• For each cell position, 259x9 clauses representing how each of the 259 windows (ignoring symmetry) constrains the cell.
• For each cell position, a clause of 259 terms indicating that at least one window is present (which must be unique)
• For each symmetry orbit over every cell position, a clause indicating that at least one member of the orbit is represented.

Update Here is a 13x13 that works

Code: Select all

x = 13, y = 13, rule = B3/S23
2ob2o$2obo3bo3b2o$3bo2bobobobo$3bobob2ob2o$b2o2bo3bo$2bobob2obo$bo2bob
o2b3o$ob3obobo3bo$bo3b2o2bobo$3bo3b3ob2o$2b3obo5bo$bo5b3obo$b2o6b2o!

And another 14x14.

Code: Select all

x = 14, y = 14, rule = B3/S23
12b2o$2ob2o3b2obobo$bobobobobob2o$o2bo2b2o$2obo5bob2o$bob8o2bo$o11b2o$
b5obob3o$5bob2o2bo$3bobo4bo$2bobob2ob2obo$bobo2bo4bobo$obo3bob2obobo$
2o3b2ob2ob2o!

I'm looking for a 12x12 but kissat has been running nearly an hour so I am not optimistic. There 13x13 took just a few minutes. I'll make another post if I have something significantly smaller or I can set a lower bound.

[pcallahan]

Here are two 13x13 periodic still life patterns with this property. I have one running for 12x12 but it has been going for days. It seems to make some progress so I might keep it running until my laptop restarts.

I haven't looked for a 12x12 finite pattern because I thought the periodic one would be easier to find. Apparently not.

Code: Select all

x = 13, y = 13, rule = B3/S23:T13,13
2o3b2ob4o$2o2bobobo2bo$4b2o3bobo$b3o6bobo$bo3b3o3b2o$2b3obobo$2o6bo2b
2o$3b2obobobo$3obob2obob2o$2bo6bo2bo$2bo2b4obo$3b3o3bo$7bo!

Code: Select all

x = 13, y = 13, rule = B3/S23:T13,13
2o3b2ob2o$6bobobo$3bo2bobo2bo$2bobobob2obo$3b2obo3bo$6b4o$b4o5b3o$bo2b
ob2obo2bo$bo4b2ob2obo$o3bo7bo$3bob3ob3o$o3bo3b2o2bo$bo4bo5bo!

[pcallahan]

I was planning to kill the 12x12 periodic search when after a week or so it came back unsatisfiable. Take that with a grain of salt. It never even looked at 12x13, and because it's periodic, it does not rule out smaller sizes either.

This isn't very meaningful without the instance. I can post that if anyone wants. It's big, needless to say.

Code: Select all

s UNSATISFIABLE
c
c --- [ run-time profiling ] -------------------------------------------------
c
c process time taken by individual solving procedures
c (percentage relative to process time for solving)
c
c    546476.81   95.76% search
c    254240.67   44.55% unstable
c    232568.19   40.75% stable
c     59667.94   10.46% walk
c     24193.31    4.24% simplify
c     12343.60    2.16% vivify
c      4263.41    0.75% factor
c      3463.77    0.61% probe
c      1061.68    0.19% backbone
c       820.02    0.14% sweep
c       431.04    0.08% subsume
c        97.86    0.02% congruence
c        74.71    0.01% elim
c        73.88    0.01% ternary
c         1.28    0.00% preprocess
c         0.04    0.00% parse
c         0.03    0.00% fastelim
c         0.01    0.00% lucky
c   =================================
c    570670.13  100.00% solve
c
c last line shows process time for solving
c (percentage relative to total process time)
c
c --- [ statistics ] ---------------------------------------------------------
c
c chronological:         229379118        30.58 %  of conflicts
c conflicts:             750038645      1314.31    per second
c backbone:            11610934737   4628433.57 %  of vars
c decisions:            1742138312      3052.79    per second
c eliminated:               152902        60.95 %  of all variables
c factored:                 213421       352.93 %  of variables
c fixed:                     41883        16.70 %  of all variables
c learned:               733889887        97.85 %  per conflict
c learned_lits:       315928829581       100.00 %  learned literals
c minimized:                     0         0.00 %  learned literals
c shrunken:           249044404698        78.83 %  learned literals
c minishrunken:        30126701294         9.54 %  learned literals
c otfs:                     877329         0.12 %  of conflict
c propagations:      2945217494257         5.16 M  per second
c reduced:               494361531        65.91 %  per conflict
c rephased:                   1224    612776.67    interval
c restarts:               24280265        30.89    interval
c stabilizing:                 170        46.49 %  of conflicts
c substituted:                2153         0.86 %  of all variables
c sweep equivs:                 22         0.01 %  of swept variables
c subsumed:              227523549        29.16 %  of all clauses
c strengthened:            3801775         0.49 %  of all clauses
c ticks:            32227202003439        11.75    propagation
c vivified:                2354439         0.30 %  of all clauses
c walked:                      407   1842846.79    interval
c weakened:                3215595         2.01    average size
c
c seconds are measured in process time for solving
c
c --- [ glue usage ] ---------------------------------------------------------
c
c focused glue 1 used 9035798995 clauses 588.2% accumulated 588.2% tier1
c focused glue 2 used 603261004 clauses 39.27% accumulated 627.4% tier2
c
c stable glue 1 used 9622580317 clauses 334.2% accumulated 334.2% tier1
c stable glue 2 used 524303032 clauses 18.21% accumulated 352.4% tier2
c
c
c --- [ resources ] ----------------------------------------------------------
c
c total process time since initialization:    570670.17    seconds
c total real time since initialization:       597752.69    seconds
c maximum resident set size of process:      1813024.00    MB
c
c --- [ shutting down ] ------------------------------------------------------
c
c exit 20