# Reverse Conway's Game of Life

Conway's Game of Life is a cellular automaton "played" on an infinite grid, filled with cells that are either alive or dead. Once given an initial state, the board evolves indefinitely according to the following rules:

• Any live cell with 2 or 3 living neighbours lives to the next state
• Any dead cell with exactly 3 living neighbours becomes a living cell
• Any other cell becomes a dead cell

# The Challenge

Given a state of the game, find the previous state.

## Rules

• All inputs are assumed to have a preceding state, that is, your code need not handle Gardens of Eden.
• There will be multiple solutions, output any of them.
• You may take input in any reasonable format. Standard I/O Rules apply.

## Test cases

> input
: output

> [(2, 2)]
: [(1, 1), (2, 2), (3, 3)]
> [(2, 2), (2, 4), (3, 3), (3, 4), (4, 3)]
: [(1, 3), (2, 4), (3, 2), (3, 3), (3, 4)]
> [(2, 2), (2, 3), (2, 4)]
: [(1, 3), (2, 3), (3, 3)]
> [(2, 2), (2, 3), (2, 4), (3, 2), (3, 4), (4, 2), (4, 3), (4, 4)]
: [(1, 3), (2, 3), (3, 2), (3, 4), (4, 3), (5, 3)]
> [(3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (5, 2), (5, 3), (5, 4)]
: [(2, 2), (2, 5), (3, 5), (4, 2), (4, 3), (5, 3), (5, 4)]
> [(2, 4), (2, 5), (4, 2), (4, 5), (5, 2), (5, 3), (5, 4)]
: [(2, 4), (2, 5), (3, 4), (3, 5), (4, 2), (4, 3), (4, 4), (5, 3)]
> [(1, 13), (1, 14), (1, 19), (1, 20), (2, 13), (2, 19), (3, 8), (3, 9), (3, 15), (3, 21), (3, 29), (3, 30), (4, 7), (4, 9), (4, 14), (4, 15), (4, 20), (4, 21), (4, 26), (4, 27), (4, 30), (5, 3), (5, 4), (5, 6), (5, 9), (5, 11), (5, 12), (5, 15), (5, 17), (5, 18), (5, 21), (5, 23), (5, 24), (5, 27), (5, 29), (6, 3), (6, 5), (6, 6), (6, 8), (6, 11), (6, 12), (6, 14), (6, 17), (6, 18), (6, 20), (6, 23), (6, 24), (6, 26), (6, 29), (6, 30), (7, 8), (7, 9), (7, 14), (7, 15), (7, 20), (7, 21), (7, 26), (7, 27), (7, 31), (8, 4), (8, 5), (8, 7), (8, 10), (8, 11), (8, 13), (8, 16), (8, 17), (8, 19), (8, 22), (8, 23), (8, 25), (8, 28), (8, 29), (8, 32), (9, 4), (9, 6), (9, 7), (9, 10), (9, 12), (9, 13), (9, 16), (9, 18), (9, 19), (9, 22), (9, 24), (9, 25), (9, 28), (9, 30), (9, 31), (9, 32), (10, 8), (10, 9), (10, 14), (10, 15), (10, 20), (10, 21), (10, 26), (10, 27), (11, 5), (11, 6), (11, 9), (11, 11), (11, 12), (11, 15), (11, 17), (11, 18), (11, 21), (11, 23), (11, 24), (11, 27), (11, 29), (11, 30), (12, 5), (12, 6), (12, 8), (12, 11), (12, 12), (12, 14), (12, 17), (12, 18), (12, 20), (12, 23), (12, 24), (12, 26), (12, 29), (12, 30), (13, 8), (13, 9), (13, 14), (13, 15), (13, 20), (13, 21), (13, 26), (13, 27), (13, 33), (13, 34), (14, 3), (14, 4), (14, 5), (14, 7), (14, 10), (14, 11), (14, 13), (14, 16), (14, 17), (14, 19), (14, 22), (14, 23), (14, 25), (14, 28), (14, 29), (14, 31), (14, 34), (15, 1), (15, 4), (15, 6), (15, 7), (15, 10), (15, 12), (15, 13), (15, 16), (15, 18), (15, 19), (15, 22), (15, 24), (15, 25), (15, 28), (15, 30), (15, 31), (15, 32), (16, 1), (16, 2), (16, 8), (16, 9), (16, 14), (16, 15), (16, 20), (16, 21), (16, 26), (16, 27), (17, 5), (17, 6), (17, 9), (17, 11), (17, 12), (17, 15), (17, 17), (17, 18), (17, 21), (17, 23), (17, 24), (17, 27), (17, 29), (17, 30), (18, 5), (18, 6), (18, 8), (18, 11), (18, 12), (18, 14), (18, 17), (18, 18), (18, 20), (18, 23), (18, 24), (18, 26), (18, 29), (18, 30), (19, 8), (19, 9), (19, 14), (19, 15), (19, 20), (19, 21), (19, 26), (19, 27), (20, 3), (20, 4), (20, 5), (20, 7), (20, 10), (20, 11), (20, 13), (20, 16), (20, 17), (20, 19), (20, 22), (20, 23), (20, 25), (20, 28), (20, 29), (20, 31), (21, 3), (21, 6), (21, 7), (21, 10), (21, 12), (21, 13), (21, 16), (21, 18), (21, 19), (21, 22), (21, 24), (21, 25), (21, 28), (21, 30), (21, 31), (22, 4), (22, 8), (22, 9), (22, 14), (22, 15), (22, 20), (22, 21), (22, 26), (22, 27), (23, 5), (23, 6), (23, 9), (23, 11), (23, 12), (23, 15), (23, 17), (23, 18), (23, 21), (23, 23), (23, 24), (23, 27), (23, 29), (23, 30), (23, 32), (24, 6), (24, 8), (24, 11), (24, 12), (24, 14), (24, 17), (24, 18), (24, 20), (24, 23), (24, 24), (24, 26), (24, 29), (24, 31), (24, 32), (25, 5), (25, 8), (25, 9), (25, 14), (25, 15), (25, 20), (25, 21), (25, 26), (25, 28), (26, 5), (26, 6), (26, 14), (26, 20), (26, 26), (26, 27), (27, 16), (27, 22), (28, 15), (28, 16), (28, 21), (28, 22)]
: [(1, 13), (1, 14), (1, 19), (1, 20), (2, 13), (2, 19), (3, 8), (3, 9), (3, 15), (3, 21), (3, 29), (3, 30), (4, 7), (4, 9), (4, 14), (4, 15), (4, 20), (4, 21), (4, 26), (4, 27), (4, 30), (5, 3), (5, 4), (5, 6), (5, 9), (5, 11), (5, 12), (5, 15), (5, 17), (5, 18), (5, 21), (5, 23), (5, 24), (5, 27), (5, 29), (6, 3), (6, 5), (6, 6), (6, 8), (6, 11), (6, 12), (6, 14), (6, 17), (6, 18), (6, 20), (6, 23), (6, 24), (6, 26), (6, 29), (6, 30), (7, 8), (7, 9), (7, 14), (7, 15), (7, 20), (7, 21), (7, 26), (7, 27), (7, 31), (8, 4), (8, 5), (8, 7), (8, 10), (8, 11), (8, 13), (8, 16), (8, 17), (8, 19), (8, 22), (8, 23), (8, 25), (8, 28), (8, 29), (8, 32), (9, 4), (9, 6), (9, 7), (9, 10), (9, 12), (9, 13), (9, 16), (9, 18), (9, 19), (9, 22), (9, 24), (9, 25), (9, 28), (9, 30), (9, 31), (9, 32), (10, 8), (10, 9), (10, 14), (10, 15), (10, 20), (10, 21), (10, 26), (10, 27), (11, 5), (11, 6), (11, 9), (11, 11), (11, 12), (11, 15), (11, 17), (11, 18), (11, 21), (11, 23), (11, 24), (11, 27), (11, 29), (11, 30), (12, 5), (12, 6), (12, 8), (12, 11), (12, 12), (12, 14), (12, 17), (12, 18), (12, 20), (12, 23), (12, 24), (12, 26), (12, 29), (12, 30), (13, 8), (13, 9), (13, 14), (13, 15), (13, 20), (13, 21), (13, 26), (13, 27), (13, 33), (13, 34), (14, 3), (14, 4), (14, 5), (14, 7), (14, 10), (14, 11), (14, 13), (14, 16), (14, 17), (14, 19), (14, 22), (14, 23), (14, 25), (14, 28), (14, 29), (14, 31), (14, 34), (15, 1), (15, 4), (15, 6), (15, 7), (15, 10), (15, 12), (15, 13), (15, 16), (15, 18), (15, 19), (15, 22), (15, 24), (15, 25), (15, 28), (15, 30), (15, 31), (15, 32), (16, 1), (16, 2), (16, 8), (16, 9), (16, 14), (16, 15), (16, 20), (16, 21), (16, 26), (16, 27), (17, 5), (17, 6), (17, 9), (17, 11), (17, 12), (17, 15), (17, 17), (17, 18), (17, 21), (17, 23), (17, 24), (17, 27), (17, 29), (17, 30), (18, 5), (18, 6), (18, 8), (18, 11), (18, 12), (18, 14), (18, 17), (18, 18), (18, 20), (18, 23), (18, 24), (18, 26), (18, 29), (18, 30), (19, 8), (19, 9), (19, 14), (19, 15), (19, 20), (19, 21), (19, 26), (19, 27), (20, 3), (20, 4), (20, 5), (20, 7), (20, 10), (20, 11), (20, 13), (20, 16), (20, 17), (20, 19), (20, 22), (20, 23), (20, 25), (20, 28), (20, 29), (20, 31), (21, 3), (21, 6), (21, 7), (21, 10), (21, 12), (21, 13), (21, 16), (21, 18), (21, 19), (21, 22), (21, 24), (21, 25), (21, 28), (21, 30), (21, 31), (22, 4), (22, 8), (22, 9), (22, 14), (22, 15), (22, 20), (22, 21), (22, 26), (22, 27), (23, 5), (23, 6), (23, 9), (23, 11), (23, 12), (23, 15), (23, 17), (23, 18), (23, 21), (23, 23), (23, 24), (23, 27), (23, 29), (23, 30), (23, 32), (24, 6), (24, 8), (24, 11), (24, 12), (24, 14), (24, 17), (24, 18), (24, 20), (24, 23), (24, 24), (24, 26), (24, 29), (24, 31), (24, 32), (25, 5), (25, 8), (25, 9), (25, 14), (25, 15), (25, 20), (25, 21), (25, 26), (25, 28), (26, 5), (26, 6), (26, 14), (26, 20), (26, 26), (26, 27), (27, 16), (27, 22), (28, 15), (28, 16), (28, 21), (28, 22)]


Visualize test cases (possible output followed by input)

This is , shortest answer in bytes wins.

• Is it possible that input is non-negative but output must have negative axis?
– l4m2
Jul 13, 2023 at 17:13
• @l4m2 you may assume both input and output will be in the first quadrant
– c--
Jul 13, 2023 at 17:19

# JavaScript (Node.js), 232 bytes

f=(x,u=[],i=0,j=0,...L)=>u.find(g=([x,y])=>(t[[k%3+x-1,(k/3|0)%3+y-1]]+=[k%9==4],++k%9?t[[x,y]].length%5-3:g(v)),k=t=[])||Object.keys(t).filter(i=>t[i][22]&&!t[i][28]).sort()!=x.sort()+''?f(x,...L,u,i+1,j,u,i,j+1,[...u,[i,j]],i,j):u


Nothing to Try it online!

f=(x,u=[],i=0,j=0,...L)=>                       // Init case
u.find(g=v=>(                                   // [i,j] exist?
t[[k%3+v[0]-1,(k/3|0)%3+v[1]-1]]+=[k%9==4],   // neighbors +=5('false'), self +=4('true')
++k%9?t[[x,y]].length%5-3:g(v)                // Repeat 9 times then return if dup
),k=t=[])||
Object.keys(t).filter(                          // 0    5   10   15   20   25 28
i=>t[i][22]&&!t[i][28]                        // undefinedfalsefalsefalsetrue
// falsefalsetrue | falsefalsefalse | falsefalsefalsetrue
).sort()!=x.sort()+''?
f(x,...L,u,i+1,j,u,i,j+1,[...u,[i,j]],i,j)      // Try next, push with next [i,j] and version with [i,j] pushed
:u