给定康威生命游戏(或任何其他细胞自动化游戏)中游戏的当前滴答声，如何找到可以计算为提供的滴答声的合法先前滴答声的数量？
例如，假设人生游戏可以表示为:
0 0 0 0 0 ...
X 0 X 0 0 ...
0 X 0 0 0 ...
0 0 0 0 X ...
...
其中 X 是“alive/on/true”，0 是“dead/off/false”，或者更简单地说是 boolean[][ ]，如何计算出以下内容:
public static int numberOfValidPreviousTicks(boolean[][] current) {
return -1; // return answer
}
很明显，我们可以从网格大小中找到所有 可能的先前游戏状态，并确定是否可以使用正常规则将其评估为当前状态。
但是，必须有一些明显的方法来加快这个过程，使其不是O(2^n)(其中 n 是网格中的单元格总数)。
缓存当然可以在某些地方提供帮助，但它究竟适合什么地方呢？
任何帮助将不胜感激
最佳答案
对于 m*m 板，您可以使用动态编程在 O(m*8^m) 中完成。
想法是从板的顶部开始向下工作，为 i-1 的每对行计算，第 i 位置的所有行都可以在i+1 位置给出正确的 i 输出行。
这比 2^O(n) = 2^(O(m*m)) 好，但速度很慢。
我不认为你会做得比这更好。
关于algorithm - 生命游戏中合法的前一步步数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41858877/