# What kind of algorithm to use when reversing state?

I'm not sure what algorithm to use in the kind of problem described below, any suggestion to put me on the right track, even at any way is desirable.

Thank you in advance.

• You have some 2D field in a form of two dimensional array (full of 0 & 1 values).
• There are certain rules, that describe how to get from previous array state to the current array state.
• Implement some solution so that you can find out all previous states that lead to the current state. If you have current state of the array.

I'm not looking for a coded solution of my problem or any shape of help like that. I just want to get on a right track and search for solutions in right area. For example: If you had some network and wanted to compute maximum flow, nice answer would be: "You should look up flow algorithms. For example: Ford–Fulkerson algorithm ... " etc. (obscure but it should do the thing).

If you need more specification for instance, if you need to know more about rules, feel free to ask!

EDIT 1:

Here are pattern details, and by the way, matrix won't be smaller than 2x2. You need to figure out for given matrix/2D grid what was it previous state if a current state is for example:

\begin{array}{cc} 1 & 0\\ 0 & 1 \end{array}

You know that 1 in the matrix cell is determined by 4 cells next to it.

• That cell
• the one below it
• the one to the right of it
• the one below and right to it

If only one of the cells has 1 in it, in the next state 1 would stay. But any other combination and zero would be next state. So for the matrix given above as example, next state would be \begin{array}{cc} 0 \end{array}

• This question seems hard to answer unless you tell us more about the rules. – Yuval Filmus May 9 '18 at 12:27
• @Yuval Filmus sure, I will update the question as soon as I get on computer. – Igor May 9 '18 at 13:19
• It might help to tell us how big the array is, too. Also, can you credit the source of this problem? Where did you see it? – D.W. May 9 '18 at 15:45
• Please don't use "EDIT:". Instead, revise the question to read well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755. Also, I wasn't asking how small the matrix could be; I was asking how large it could be. Also, something seems wrong with the end of your question. What do you mean by "next state would be 0"? Is part of the matrix missing? – D.W. May 9 '18 at 22:07