【Python】N×N行列の空セル選択パターン数を数えるプログラムの書き方

問題概要

N × N の2値行列を考えます。ここで 0 は空のセル、1 はブロックされたセルを表します。このとき、「すべての行とすべての列に、選ばれたセルが少なくとも1つ含まれる」ように N 個の空のセルを選ぶ方法の数を求めます。答えが非常に大きくなる可能性があるため、結果は 10^9 + 7 で割った余りとして返します。

例えば、入力が次のような行列だったとします。

この場合、出力は 4 になります。以下の4通りの配置(x が選択されたセルを表す)が存在するためです。

アプローチ:ビットマスクを使った再帰探索

この問題は、行ごとに順番に処理を進めていく再帰的な探索で解くことができます。ポイントは、すでに使用済みとなった列をビットマスク(整数のビット列)で管理することです。

具体的な手順は以下の通りです。

• n := 行列のサイズとする
• 関数 f(i, bs) を定義する(i は現在の行番号、bs は使用済み列のビットマスク)
• i >= n の場合(すべての行を処理し終えた場合)、1 を返す
• ans := 0 で初期化する
• j を 0 から n-1 までループする
  • matrix[i][j] が 0(空セル)であり、かつ (2^j AND bs) == 0(列 j が未使用)の場合
    • ans := ans + f(i + 1, bs OR 2^j)
• ans を返す
• メイン処理から f(0, 0) を呼び出して結果を返す

このアルゴリズムでは、各行について「どの列のセルを選ぶか」を再帰的に試していきます。ビット演算(<<:シフト、&:AND、|:OR)を活用することで、使用済みの列の集合を1つの整数で効率的に表現できるのが特徴です。

実装例(Python)

class Solution:
    def solve(self, matrix):
        n = len(matrix)

        def f(i, bs):
            if i >= n:
                return 1
            ans = 0
            for j in range(n):
                if matrix[i][j] == 0 and ((1 << j) & bs == 0):
                    ans += f(i + 1, bs | (1 << j))
            return ans

        return f(0, 0)

ob = Solution()
matrix = [
    [0, 0, 0],
    [0, 0, 0],
    [0, 1, 0]
]
print(ob.solve(matrix))

入力

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

出力

4

計算量に関する補足

この手法の計算量は最悪の場合 O(n!) 程度に達するため、n が大きくなると処理時間が急増します。そのようなケースでは、メモ化(結果のキャッシュ)や動的計画法(DP)との組み合わせを検討するとよいでしょう。一方、小規模な行列に対しては、このシンプルな再帰的アプローチでも十分に実用的で、ロジックも理解しやすくなっています。