Some notes about the script:

- It does a brute force search, and thus finds all strict still lifes

- The way in which it filters out pseudo still lifes is based on the definition that if it can be split up into two stable subpatterns, then it is pseudo. I realize that there are pseudos that it may miss (see this page for some discussion), but I can't see that being an issue for still lifes that can realistically be computed using this script.

- It filters out different reflections/rotations of the same still lifes.

- Realistically, it's fast enough to enumerate still lifes up to 9 or maybe 10 cells.

Note: If you use Windows, there is a compiled (ie. executable) version of this program attached at the bottom of this post.

EnumStillLifes.c

`/*`

* EnumStillLifes.c

* v1.03

* Calculates the number of still lifes in a Life-like cellular automaton

* given a rulestring and a number of cells

* Does a brute-force search, so it is very slow for even moderately large n

*

* Created by Nathaniel Johnston (nathaniel@nathanieljohnston.com)

* Created: March 19, 2009

* Modified: March 28, 2009

*/

#include <math.h>

#include <stdio.h>

#include <string.h>

// If needed, change 10000 to a number larger than the number of still lifes that will be found

unsigned char foundSL[10000][16][16],islandCount=0,numIsl;

unsigned char group1[20][20],group2[20][20];

unsigned char birth23,n,u,uInc,curStep,islArr[16][20][20],been[20][20],tempB[20][20],tempC[20][20],xp[18],yp[18],minX,minY,maxX,maxY;

unsigned int i,j,survive=0,birth=0;

unsigned long int total=0;

char fName[50];

FILE *file;

int max(int mA, int mB)

{

if(mA >= mB) return mA;

return mB;

}

int min(int mA, int mB)

{

if(mA <= mB) return mA;

return mB;

}

unsigned char numNeighbours(unsigned char x, unsigned char y, unsigned char bArr[20][20]){

char nI,nJ;

unsigned char res=0;

for(nI=x-1;nI<=x+1;++nI){

for(nJ=y-1;nJ<=y+1;++nJ){

res+=bArr[nI][nJ];

}

}

return res;

}

void getMinMax()

{

unsigned char mI;

minX = u+2;

minY = u+2;

maxX = 2;

maxY = 2;

for (mI=1;mI<=n;mI++){

minY=min(yp[mI],minY);

minX=min(xp[mI],minX);

maxY=max(yp[mI],maxY);

maxX=max(xp[mI],maxX);

}

}

void printSL(unsigned char pArr[20][20])

{

unsigned char pI,pJ,pK;

printf("Still lifes found so far: %d\n",total+1);

file = fopen(fName,"a+");

for(pI=2;pI<=maxY+1;++pI){

for(pJ=2;pJ<=maxX;++pJ){

if(pArr[pJ][pI]==1){

fprintf(file,"*");

}else{

fprintf(file," ");

}

}

fprintf(file,"\n");

}

fprintf(file,"\n");

fclose(file);

}

unsigned char checkPreviousSL(unsigned char bArr[20][20])

{

unsigned char cI,cJ;

unsigned int cK;

unsigned char match;

for(cI=2;cI<=34;++cI){

for(cJ=2;cJ<=34;++cJ){

foundSL[total][cI-2][cJ-2] = bArr[cI][cJ];

}

}

for(cK=0;cK<total;++cK){

match=1;

for(cI=2;cI<=maxX;++cI){

for(cJ=2;cJ<=maxY;++cJ){

if(foundSL[cK][maxX-cI][maxY-cJ]!=bArr[cI][cJ]){

cJ=maxY;

cI=maxX;

match=0;

}

}

}

if(match==1){return 0;}

match=1;

for(cI=2;cI<=maxX;++cI){

for(cJ=2;cJ<=maxY;++cJ){

if(foundSL[cK][cI-2][maxY-cJ]!=bArr[cI][cJ]){

cJ=maxY;

cI=maxX;

match=0;

}

}

}

if(match==1){return 0;}

match=1;

for(cI=2;cI<=maxX;++cI){

for(cJ=2;cJ<=maxY;++cJ){

if(foundSL[cK][maxX-cI][cJ-2]!=bArr[cI][cJ]){

cJ=maxY;

cI=maxX;

match=0;

}

}

}

if(match==1){return 0;}

match=1;

for(cI=2;cI<=maxX;++cI){

for(cJ=2;cJ<=maxY;++cJ){

if(foundSL[cK][maxY-cJ][maxX-cI]!=bArr[cI][cJ]){

cJ=maxY;

cI=maxX;

match=0;

}

}

}

if(match==1){return 0;}

match=1;

for(cI=2;cI<=maxX;++cI){

for(cJ=2;cJ<=maxY;++cJ){

if(foundSL[cK][cJ-2][maxX-cI]!=bArr[cI][cJ]){

cJ=maxY;

cI=maxX;

match=0;

}

}

}

if(match==1){return 0;}

match=1;

for(cI=2;cI<=maxX;++cI){

for(cJ=2;cJ<=maxY;++cJ){

if(foundSL[cK][maxY-cJ][cI-2]!=bArr[cI][cJ]){

cJ=maxY;

cI=maxX;

match=0;

}

}

}

if(match==1){return 0;}

match=1;

for(cI=2;cI<=maxX;++cI){

for(cJ=2;cJ<=maxY;++cJ){

if(foundSL[cK][cJ-2][cI-2]!=bArr[cI][cJ]){

cJ=maxY;

cI=maxX;

match=0;

}

}

}

if(match==1){return 0;}

}

return 1;

}

unsigned char isStillLife(unsigned char beenArr[20][20], unsigned char forceY)

{

char sI,sJ,sRes;

getMinMax();

if(minY>forceY){

return 0;

}

for(sI=1;sI<=u+2;sI++){

for(sJ=1;sJ<=u+2;sJ++){

if(beenArr[sI][sJ]==1){

if((survive & (1 << (numNeighbours(sI,sJ,beenArr)-1))) == 0){

return 0;

}

}else if((birth & (1 << numNeighbours(sI,sJ,beenArr))) > 0){

return 0;

}

}

}

if(forceY==2){

sRes = checkPreviousSL(beenArr);

}else{

sRes = 1;

}

return sRes;

}

void fillOutIsland(unsigned char xC, unsigned char yC)

{

unsigned char fI, fJ;

for(fI=xC-1;fI<=xC+1;++fI){

for(fJ=yC-1;fJ<=yC+1;++fJ){

if((been[fI][fJ]==1)&(tempB[fI][fJ]==0)){

tempB[fI][fJ]=1;

tempC[fI][fJ]=1;

islArr[numIsl][fI][fJ]=1;

islandCount++;

fillOutIsland(fI,fJ);

}

}

}

}

void resetIslArr()

{

unsigned char iaI;

for(iaI=0;iaI<=15;++iaI){

for(i=0;i<=19;i++){

for(j=0;j<=19;j++){

islArr[iaI][i][j]=0;

}

}

}

}

void resetTempB()

{

for(i=0;i<=19;i++){

for(j=0;j<=19;j++){

tempB[i][j]=0;

}

}

}

void resetTempC()

{

for(i=0;i<=19;i++){

for(j=0;j<=19;j++){

tempC[i][j]=0;

}

}

}

void clearGroups()

{

for(i=0;i<=19;i++){

for(j=0;j<=19;j++){

group1[i][j]=0;

group2[i][j]=0;

}

}

}

unsigned char findIsland()

{

unsigned char iI,start;

for(iI=1;iI<=n;++iI){

if(tempC[xp[iI]][yp[iI]] == 0){

start=iI;

break;

}

}

resetTempB();

tempB[xp[start]][yp[start]]=1;

tempC[xp[start]][yp[start]]=1;

islArr[numIsl][xp[start]][yp[start]]=1;

islandCount++;

fillOutIsland(xp[start],yp[start]);

return (1-isStillLife(tempB,u+1));

}

unsigned char firstCellsCheck(unsigned char fPos){

return (birth & (1 << (been[2][fPos]+been[2][fPos-1]+been[2][fPos-2])));

}

unsigned char firstRowCheck(){

unsigned char fI;

unsigned long int tNum=0,rNum=0;

for(fI=0;fI<u;++fI){

rNum += ((long)been[2][fI+2] << ((u-1)-fI));

tNum += ((long)been[2][fI+2] << fI);

}

return (rNum >= tNum);

}

void combGroup(unsigned char groupArr[20][20], unsigned char islTArr[20][20]){

for(i=0;i<=19;i++){

for(j=0;j<=19;j++){

groupArr[i][j]=max(groupArr[i][j],islTArr[i][j]);;

}

}

}

unsigned char checkPseudo(){

unsigned int psI,psJ,psLim;

psLim = (1 << numIsl);

for(psI=psLim/2;psI<psLim-1;++psI){

clearGroups();

for(psJ=0;psJ<numIsl;++psJ){

if(psI & (1 << psJ)){

combGroup(group1,islArr[psJ]);

}else{

combGroup(group2,islArr[psJ]);

}

}

if(isStillLife(group1,u+1)&&isStillLife(group2,u+1)){return 0;}

}

return 1;

}

void getNextStep(char curM)

{

unsigned char m,cx,cy,isSL;

unsigned char lim = min(u*u - (u-curStep), curM + 2*(u+2));

if(curM==-1)lim=ceil(n/3.0001)-1;

m=curM+1;

if(!(birth23&&m<u&&firstCellsCheck(m))&&!(m==u&&(firstRowCheck()==0))){

curStep++;

while(m<=lim)

{

cx=floor(m/u)+2;

cy=(m%u)+2;

xp[curStep]=cx;

yp[curStep]=cy;

been[cx][cy]=1;

if(curStep==n){

islandCount=0;

isSL = isStillLife(been,2);

if(isSL==1){

numIsl=0;

isSL=0;

resetTempC();

resetIslArr();

while(islandCount<n){

isSL=max(findIsland(),isSL);

numIsl++;

}

if(numIsl==1){

isSL=1;

}else{

if(isSL==1){

isSL=checkPseudo();

}

}

}

if(isSL==1){

printSL(been);

}

total+=isSL;

}else{

getNextStep(m);

}

been[cx][cy]=0;

if(m==curM+u+2){m+=uInc;}

else{m++;}

}

curStep--;

}

}

void setVariables()

{

for(i=0;i<=19;i++){

for(j=0;j<=19;j++){

been[i][j]=0;

tempC[i][j]=0;

}

}

curStep=0;

total=0;

}

int main()

{

unsigned char foundSlash = 0;

char rs[19];

setVariables();

printf("This tool will calculate the number of still lifes in a Life-like cellular automaton.\nPlease enter the rulestring in S/B format (eg. 23/3 for Conway's Game of Life): ");

scanf("%s",&rs);

for(i=0;i<strlen(rs);i++){

if(foundSlash==0){

if(rs[i]=='/'){

foundSlash = 1;

}else{

survive += (1 << (rs[i]-16));

}

}else{

birth += (1 << (rs[i]-16));

}

}

if(birth & 1){

printf("There are no still lifes in any rule with \"0\" in the birth list.");

}else if(birth & 2){

printf("There are no still lifes in any rule with \"1\" in the birth list.");

}else if(!(survive & 1)&&!(survive & 2)&&!(survive & 4)&&!(survive & 8)&&!(survive & 16)){

printf("There are no still lifes in this rule because all cells with 4 or fewer neighbours die.");

}else{

birth23=((birth & 4)||(birth & 8));

printf("Enter the number of cells (1 <= n <= 16): ");

scanf("%d",&n);

u = n;

if(!(survive & 2)){ // if "1" is not in the survival list

u = min(max(n - 2, min(n, 4)), u);

}

uInc = max(u-4,1);

printf("Please enter an output file name (eg. \"output.txt\"): ");

scanf("%s",&fName);

getNextStep(-1);

file = fopen(fName,"a+");

fprintf(file,"Number of %d-cell still lifes in \"%s\": %d\n",n,rs,total);

fclose(file);

printf("Total number of %d-cell still lifes in \"%s\": %d",n,rs,total);

}

return 0;

}