Учитывая текущий тик игры в игре жизни Конвея (или любой другой игре с сотовой автоматизацией), как можно найти количество легальных предыдущих тиков, которые можно было бы оценить в предоставленном тике?
Например, предполагая, что игра жизни может быть представлена как:
0 0 0 0 0 ...
X 0 X 0 0 ...
0 X 0 0 0 ...
0 0 0 0 X ...
...
где X — «активен/включен/истинен», а 0 — «мертв/выключен/ложь», или, проще говоря, как boolean[][], как можно решить следующее:
public static int numberOfValidPreviousTicks(boolean[][] current) {
return -1; // return answer
}
Понятно, что можно найти каждое возможное предыдущее состояние игры по размеру сетки и определить, будет ли оно оцениваться как текущее состояние, используя обычные правила.
Однако должны быть какие-то очевидные способы ускорить этот процесс, чтобы он не был O(2^n) (где n — общее количество ячеек в сетке).
Кэширование, конечно, может помочь в некоторых местах, но где именно оно подходит?
Любая помощь будет оценена
