Pythonで各行・各列に重複しない数字が入るよう正方形マトリクスを埋められるか判定するプログラム

問題の概要

n × n の行列が与えられ、各セルには 0 から n までの値が入っているものとします。ここで 0 は「未記入のマス」を表します。この課題では、空きマスを適切に埋めて、各行および各列に 1 から n までの数字がそれぞれちょうど1回ずつ現れるようにできるかどうかを判定します。

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

この場合の出力は True になります。実際、次のようにマスを埋めることが可能だからです。

この種の問題は数独（ナンプレ）によく似ていますが、3×3 のブロック制約がない点が異なります。行と列の制約だけで成立するため、「ラテン方陣（Latin Square）」を完成させる問題として知られています。

解法の考え方：バックトラッキング

この問題はバックトラッキング（探索の巻き戻し）という手法で解くのが定番です。大まかな流れは以下の通りです。

1. find_empty_cell() 関数を定義します。引数は matrix と n です。

   • i を 0 から n-1 まで順に調べます。
   • j を 0 から n-1 まで順に調べます。
   • matrix[i][j] が 0 なら、その座標 (i, j) を返します。

   空きマスが見つからなければ (-1, -1) を返します。

2. is_feasible() 関数を定義します。引数は matrix、i、j、x で、値 x を (i, j) に入れても矛盾しないかを判定します。

   • x が i 行目にすでに存在する場合は False を返します。
   • x が j 列目にすでに存在する場合も False を返します。
   • どちらにも存在しなければ True を返します。

3. is_complete() 関数を定義します。引数は matrix と n で、行列全体が完成しているかを確認します。

   • 各行について、1〜n 以外の値や重複があれば False を返します。
   • 各列についても同様に、重複があれば False を返します。
   • すべて問題なければ True を返します。

4. メインの solve メソッドでは以下を実行します。

   • n := 行列の行数
   • (i, j) = find_empty_cell(matrix, n)
   • (i, j) が (-1, -1) の場合（＝空きマスなし）：
     • is_complete(matrix, n) が真なら True を返す
     • そうでなければ False を返す
   • x を 1 から n まで順に試します：
     • is_feasible(matrix, i, j, x) が真なら：
       • matrix[i][j] := x と仮置きする
       • solve(matrix) が真を返せば、そのまま True を返す
       • 失敗したら matrix[i][j] := 0 に戻し（バックトラック）、次の候補へ進む
   • すべて試しても解が見つからなければ False を返します。

実装例

それでは、実際の Python コードを見てみましょう。

class Solution:
   def solve(self, matrix):
      n = len(matrix)
      def find_empty_cell(matrix, n):
         for i in range(n):
            for j in range(n):
               if matrix[i][j] == 0:
                  return (i, j)
         return (-1, -1)
      def is_feasible(matrix, i, j, x):
         if x in matrix[i]:
            return False
         if x in [row[j] for row in matrix]:
            return False
         return True
      def is_complete(matrix, n):
         for row in matrix:
            if set(row) != set(range(1, n + 1)):
               return False
         for col in range(n):
            if set(row[col] for row in matrix) != set(range(1, n + 1)):
               return False
         return True
      (i, j) = find_empty_cell(matrix, n)

      if (i, j) == (-1, -1):
         if is_complete(matrix, n):
            return True
         else:
            return False
      for x in range(1, n + 1):
         if is_feasible(matrix, i, j, x):
            matrix[i][j] = x
            if self.solve(matrix):
               return True
            matrix[i][j] = 0
      return False
ob = Solution()
matrix = [
   [0, 0, 2],
   [2, 0, 1],
   [1, 2, 3]
]
print(ob.solve(matrix))

入力

matrix = [
   [0, 0, 2],
   [2, 0, 1],
   [1, 2, 3]
]

出力

True

まとめ

このアルゴリズムは最悪ケースで非常に大きな計算量になりますが、is_feasible() による枝刈りの効果で、実際には大幅に高速化されます。バックトラッキングは数独ソルバーなど、同じ構造を持つ多くのパズル問題に応用できる強力なテクニックなので、仕組みをしっかり理解しておくと役立ちます。