Pythonでチェス盤が有効なNクイーン問題の解かどうかを判定する方法

n×n の行列が1つのチェス盤を表していると考えます。行列には「1」と「0」が含まれており、「1」はクイーンが置かれているセル、「0」は空のセルを表します。ここで、この盤面がNクイーン問題の有効な解となっているかどうかを判定する必要があります。

Nクイーン問題において有効な解とは、どの2つのクイーンも互いに攻撃し合っていない盤面のことです。つまり、同じ行・同じ列・同じ斜め線上に複数のクイーンが存在してはいけません。

例として、次のような入力が与えられた場合を考えてみましょう。

この場合、出力は True になります。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• n := 行列の行数とします。
• rows(行)、cols(列)、diags(右下がりの斜め)、rev_diags(右上がりの斜め)という4つの空の集合(set)を作成します。
• i を 0 から n-1 まで繰り返します。
  • j を 0 から n-1 まで繰り返します。
    • matrix[i][j] が 1(クイーンが存在する)の場合:
      • i を rows に追加
      • j を cols に追加
      • (i - j) を diags に追加
      • (i + j) を rev_diags に追加
• rows、cols、diags、rev_diags の4つの集合のサイズがすべて n と等しければ True を返し、そうでなければ False を返します。

ポイント解説

このアルゴリズムの鍵となるのは、斜め方向の衝突を効率的に検出する方法です。

• (i - j): 同じ右下がりの斜め線上にあるセルは、この差が一定になります。
• (i + j): 同じ右上がりの斜め線上にあるセルは、この和が一定になります。

クイーン同士が攻撃し合わないということは、各行・各列・各斜め線にクイーンがちょうど1個ずつ存在することを意味します。したがって、4つの集合のサイズがすべて n に一致していれば、その盤面は有効な解です。

実装例

以下のコードを見ると理解が深まります。

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

        rows = set()
        cols = set()
        diags = set()
        rev_diags = set()

        for i in range(n):
            for j in range(n):
                if matrix[i][j]:
                    rows.add(i)
                    cols.add(j)
                    diags.add(i - j)
                    rev_diags.add(i + j)

        return len(rows) == len(cols) == len(diags) == len(rev_diags) == n

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

入力

matrix = [
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 1, 0, 0],
    [1, 0, 0, 0, 0]
]

出力

True

計算量について

このアルゴリズムの計算量は以下の通りです。

• 時間計算量: O(n²) — 盤面上のすべてのセルを一度ずつ走査するためです。
• 空間計算量: O(n) — 各集合には最大 n 個の要素しか格納されません。

集合(set)を使用することで、要素の追加・重複チェックが O(1) で行えるため、非常に効率的に判定できます。