Pythonでライフゲームを実装！セルマトリクスの次の状態を求めるプログラム

問題の概要

2次元のバイナリ行列を考えます。「1」は生存しているセル（生きた細胞）、「0」は死んでいるセルを表します。あるセルの「近傍」とは、そのセルの上下左右および斜め方向に隣接する最大8個のセルのことです。

この記事では、以下のルールに従って行列全体の「次の状態」を求めるプログラムをPythonで実装します。このルールは、数学者ジョン・コンウェイが考案した有名な「ライフゲーム（Conway's Game of Life）」と同じものです。

セルの状態遷移ルール

• 生存しているセルは、隣接する生存セルが2つまたは3つの場合に限り、次の世代でも生存します。
• 死んでいるセルは、隣接する生存セルがちょうど3つの場合に新しいセルとして誕生します。
• 上記以外のすべてのセルは、過疎または過密により死滅します。

入力例と出力例

たとえば、次のような4×4の行列が入力として与えられたとします。

このとき、出力は次のようになります。右端の列の生存セルが消えているのが分かりますね。

解法アルゴリズム

この問題は、各セルについて近傍の生存セルの数を数え、ルールに従って次の状態を決定することで解けます。手順は以下の通りです。

1. 行数を n、列数を m とします。
2. 結果を格納するための n × m の行列 res を作成し、すべて0で初期化します。
3. i を 0 から n-1 まで、j を 0 から m-1 まで二重ループで走査します。
   • 変数 s を 0 で初期化します（近傍の生存セル数の合計）。
   • 現在のセルが死んでいる場合（matrix[i][j] == 0）：
     • k を i-1 から i+1 まで、h を j-1 から j+1 までループし、行列の範囲内（0 ≤ k < n かつ 0 ≤ h < m）であれば s += matrix[k][h] とします。
     • s == 3 のときだけ res[i][j] = 1 とします（誕生の条件）。
   • 現在のセルが生存している場合：
     • 同様にして近傍の合計 s を計算します。このとき自分自身（値が1）も合計に含まれる点に注意してください。
     • s が 3 または 4 のとき res[i][j] = 1 とします。自分自身の1を引くと近傍の生存セル数は 2 または 3 となり、生存条件を満たします。
4. 最後に res を返します。

なお、境界の外側を参照しないよう、インデックスの範囲チェック（0 ≤ k < n かつ 0 ≤ h < m）を必ず行うことが重要です。

Pythonでの実装例

それでは、上記のアルゴリズムを実際のコードで確認してみましょう。

class Solution:
    def solve(self, matrix):
        n, m = len(matrix), len(matrix[0])
        res = [[0 for j in range(m)] for i in range(n)]
        for i in range(n):
            for j in range(m):
                s = 0
                if matrix[i][j] == 0:
                    # 死んだセル：近傍の生存セルをカウント
                    for k in range(i - 1, i + 2):
                        for h in range(j - 1, j + 2):
                            if 0 <= k < n and 0 <= h < m:
                                s += matrix[k][h]
                    # 近傍がちょうど3つなら誕生
                    res[i][j] = [0, 1][s == 3]
                else:
                    # 生きたセル：自分自身も含めてカウント
                    for k in range(i - 1, i + 2):
                        for h in range(j - 1, j + 2):
                            if 0 <= k < n and 0 <= h < m:
                                s += matrix[k][h]
                    # 自分自身の1を含むため、sが3または4なら生存
                    if s in [3, 4]:
                        res[i][j] = 1
        return res

ob = Solution()
matrix = [
    [1, 1, 0, 0],
    [0, 1, 0, 0],
    [0, 1, 0, 1],
    [1, 1, 0, 1]
]

print(ob.solve(matrix))

入力

[[1, 1, 0, 0],
 [0, 1, 0, 0],
 [0, 1, 0, 1],
 [1, 1, 0, 1]]

出力

[[1, 1, 0, 0],
 [0, 1, 0, 0],
 [0, 1, 0, 0],
 [1, 1, 0, 0]]

コードのポイント

• [0, 1][s == 3] は、条件式 s == 3 が True（=1）/ False（=0）になる性質を利用した簡潔な書き方です。可読性を重視するなら res[i][j] = 1 if s == 3 else 0 としてもよいでしょう。
• range(i - 1, i + 2) は i-1、i、i+1 の3つの値を生成するため、3×3の近傍領域を効率よく走査できます。
• 生存セルの判定で s in [3, 4] としているのは、合計値に自分自身（1）が含まれるためです。4から1を引いた3、3から1を引いた2が、それぞれ近傍の生存セル数に対応します。

計算量

• 時間計算量： O(n × m)。各セルにつき最大9マス（自分＋近傍8つ）を参照します。
• 空間計算量： O(n × m)。結果を保存するための新しい行列が必要です。

このように、ライフゲームの次世代計算はシンプルな二重ループと近傍カウントだけで実装できます。ぜひご自身の環境でも動かしてみてください。