Как в игре «Жизнь» определить предыдущее состояние клеток по текущему? (Одномерное поле)?
Обозначим текущее состояние как C[1..N], предыдущее как P[1..N], С[0] = P[0] = C[N+1] = P[N+1] = 0 - клетки за пределами поля.
На текущем шаге клетка жива тогда и только тогда, когда на предыдущем шаге у неё был ровно один сосед, то есть C[i] = P[i-1] xor P[i+1] => P[i+1] = C[i] xor P[i-1].
1. P[0] = 0, C[1] известна => P[2] = P[0] xor C[1]. Теперь, зная P[2] можно найти P[4] = P[2] xor C[3] или в общем случае:для i от 1 до N с шагом 2
    P[i+1] = P[i-1] xor C[i];Получили все предыдущие значения чётных ячеек.
2a. Для чётных N обратным ходом можно восстановить нечётные ячейки:для i от N до 1 с шагом -2
    P[i-1] = P[i+1] xor C[i];
2b. Для нечётных N однозначного решения нет. В зависимости от значения P[1] будет получен один из двух вариантов решения:P[1] = 0; // или 1
для i от 2 до N с шагом 2
    P[i+1] = P[i-1] xor C[i];
Верно так:// Инициализируем C, надо заменить на ввод исходных данных
$C = array(1, 1, 1, 0, 0, 1, 1, 1, 0, 1);
$N = count($C);

// Добавляем в начало и конец нули
array_unshift($C, 0);
$C[] = 0;

// Создаём массив P, заполняем 0 и N+1 элементы нулями
$P[0] = 0;
$P[$N+1] = 0;

// Заполняем чётные ячейки
for ($i = 1; $i <= $N; $i += 2)
    $P[$i+1] = $P[$i-1] ^ $C[$i];

// Заполняем нечётные ячейки
if (($N&1) == 0) {
    // Вариант с чётным количеством ячеек
    for ($i = $N; $i >= 1; $i -= 2)
        $P[$i-1] = $P[$i+1] ^ $C[$i];
} else {
    // Вариант с нечётным количеством ячеек
    $P[1] = 0;
    for ($i = 1; $i <= $N; $i -= 2)
        $P[$i-1] = $P[$i+1] ^ $C[$i];
}

// Выводим результат
for ($i = 1; $i <= $N; $i++)
    print $P[$i];
Получаем 0110100111.
Проверяем, (0110100111) даёт по правилам (1110011101)