algorithm - 生命游戏中合法的前一步步数

Question

给定康威生命游戏(或任何其他细胞自动化游戏)中游戏的当前滴答声，如何找到可以计算为提供的滴答声的合法先前滴答声的数量？

例如，假设人生游戏可以表示为:

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 是网格中的单元格总数)。

缓存当然可以在某些地方提供帮助，但它究竟适合什么地方呢？

任何帮助将不胜感激

Answer 1

对于 m*m 板，您可以使用动态编程在 O(m*8^m) 中完成。

想法是从板的顶部开始向下工作，为 i-1 的每对行计算，第 i 位置的所有行都可以在i+1 位置给出正确的 i 输出行。

这比 2^O(n) = 2^(O(m*m)) 好，但速度很慢。

我不认为你会做得比这更好。