UnLife: a Life pattern precursor generator

 

Introduction

Read this first.

Given a pattern P and an integer n, UnLife attempts to find a pattern Q such that P is the nth-generation descendant of Q. The main advantage of the program is that it is very short: it is much simpler than others that perform the same task because all the complexity is devolved to a sophisticated general-purpose constraint satisfaction library. Despite this the performance of the program is surprisingly good.

History and motivation

The first version of the program, handling only the case n=1, was written to create a puzzle for Pablo’s Armchair Treasure Hunt 2014: see page 5 of the puzzle and page 5 of the solution PDF. The version of the code given here has been extended to cover general n.

Download

First install the PicoSAT library. On Linux machines running Debian or a derived distribution, this can be done using the following command.

sudo apt-get install picosat

Alternatively, the source code for the library can be downloaded here.

Download the source code (MIT licence). The comments in the code explain how to modify it to specify the desired result pattern P and the value of n.

Compile and run the program. On Linux machines the following commands can be used.

gcc unl-ng.c -l picosat
./a.out

The program outputs the result pattern Q and its subsequent generations to stderr, and a file containing Q suitable for loading into GtkLife or Golly to stdout. If it fails to find a solution it outputs Unsatisfiable to stderr. The source code explains the use of the single optional command-line argument.

Comments or questions? Please contact me at the e-mail address on the home page.