6
$\begingroup$

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.

image desc

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)

||improve this question
$\endgroup$
  • $\begingroup$ Welcome to Puzzling SE! Do you have the source of this challenge? $\endgroup$ – North Mar 13 '18 at 20:16
  • $\begingroup$ @North Yes but it's in French, and you'll need to spend time unlocking stuff to reach the problem I'm on, I figured it wasn't necessary. Maybe a screenshot would be useful? $\endgroup$ – Teleporting Goat Mar 13 '18 at 20:19
  • $\begingroup$ Are you looking for approaches that you could carry out with pencil and paper, or is using a computer search OK? Because if it's the latter, I could just link you to LLS (and a bunch of other similar programs, but LLS seems to be the current cutting edge for general-purpose solvers). $\endgroup$ – Ilmari Karonen Mar 13 '18 at 20:23
  • $\begingroup$ @IlmariKaronen Ideally pen and paper, I don't think those puzzles are meant to be done with a software. It'd be like plugging a sudoku grid in a sudoku solver. I'll give it a look though. $\endgroup$ – Teleporting Goat Mar 13 '18 at 20:25
  • $\begingroup$ @TeleportingGoat it is curtesy of Puzzling SE that you site the source of anything that is not of your own creation. $\endgroup$ – North Mar 13 '18 at 20:37
1
$\begingroup$

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.

||improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.