B4-S4 is a SAT-based oscillator finder of Conway's game of life under rule B4/S4.
Given a
- if there are exactly 4 of a cell's neighbors are alive at
$t$ , then the cell is alive at$t+1$ . - otherwise, the cell is dead at
$t+1$ .
where the neighbors of a cell at coordinate
we call the initial state
-
$O_0$ is nonempty -
$O_0=O_t$ for some positive integer$t$
if such
And the problem we interests is to find out all oscillator or find a general way to construct oscillator.
Given boolean variables
and to find an assignment of
- Unlike original Game of Life, the rule ensure the cells won't exceed the original margin, namely
$n\times m$ . - Unlike original Game of Life, there is no Still lifes, namely oscillator with period
$1$ .
The smallest oscillator is in size
fire0 | fire1 |
---|---|
For
time 0 | time 1 | |
---|---|---|
Crystal | ||
Currency | ||
Face | ||
Robot |
For
time 0 | time 1 | |
---|---|---|
Deer | ||
Shuriken |
And further we have some complicated and not well-symmetrical oscillators. The number of oscillator increases rapidly when the size comes to
time 0 | time 1 | |
---|---|---|
Girrafe | ||
Parallelogram | ||
Tilt |
There are infinitely many oscillators, since we can repeat this pattern for any finite times
time 0 | time 1 |
---|---|
- all oscillators are with period 2