What approach should I use to solve cellular automaton puzzles? (Find the previous state of a game of life grid)

Question

There's a type of puzzle where you're in front of a grid (two colors, 6x6) that is a cellular automaton. There's a grid you can interact with, and one that shows what you need to obtain. So you have to:

1. Figure out the rules (basically variants of the Game of Life)

2. Find a state that leads to the given grid

Finding the rules isn't that complicated, but I have troubles finding something for stage 2.

I could give you the one I'm stuck on, but I'd be stuck on the next one, what I need is a method or some kind of lead to try and crack it.

---

I'm thinking of filling a grid, counting the number of neighbors, and basically tick white or black when I'm sure, and then cover more and more of the grid like in Minesweeper, but it doesn't seem to work, I'm stuck at step one with no clue.

TL;DR: Given a Game of Life grid at state n, how can I find a possible n-1 grid?

---

EDIT: Here's a screenshot of the puzzle, maybe it'll help. The rules are: "A cell will be red at the next iteration if it touches at least 5 red cells (including itself)". The grid is toroidal.

The input is the same as the goal because I found it to be good starting point.

Here's the source. (in French, but you don't really need to read anything. The cellular automaton puzzles are on col 0, row 1-2)

Answer 1

There are different patterns that can evolve into the same one, so the answer is only going to be unique if the pattern was especially designed to only have one possible predecessor. (As an interesting aside, since the grid size doesn’t change, this also proves that not every pattern has a possible predecessor.)

That said, if you know the parameters, you can approach the puzzle as ”fuzzy minesweeper” with 4 possible cases:

• A live square was either
  • a live square with the right number of neighbours to survive or
  • an empty square with the right number of neighbours to born
• An empty square was either
  • empty, and didn’t have the right number of neighbours to born, or
  • alive, and didn’t have the right number of neighbours to survive

This gives you a pattern much resembling minesweeper, for which you have to find a possible pattern of live squares, satisfying all the conditions at once.

Checking if a minesweeper pattern is consistent is known to be NP-complete, and this puzzle isn’t any easier, so the only solution method guaranteed to always work is the brute force search through every possible pattern.

For well designed patterns, though, there will be shortcuts. I would start a manual solve at the corners, because those cells have the fewest possible neighbours.