Pythonでチェス盤上のナイト（騎士）同士が互いに攻撃しているか判定する方法

ここでは、二次元のバイナリ行列を扱います。この行列は長方形のチェス盤を表しており、0 は空きマス、1 はナイト（騎士）がいるマスを意味します。ナイトは、実際のチェスと同じように、水平方向に2マス・垂直方向に1マス、あるいは垂直方向に2マス・水平方向に1マス移動できます。

この問題の目的は、盤上に存在するどれか2つのナイトが互いに攻撃し合っているかどうかを判定することです。

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

この場合、2つのナイトが互いに攻撃可能な位置にあるため、出力は True になります。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

• まず、行列の行数と列数を取得します。
• すべてのマスを順番に走査します。
• ナイトが存在するマスを見つけたら、その下方4方向、つまり (r+1, c-2)、(r+1, c+2)、(r+2, c-1)、(r+2, c+1) の位置に別のナイトがいないかを確認します。
• 攻撃関係にあるナイトのペアが1組でも見つかれば、True を返します。
• 最後まで見つからなければ、False を返します。

ここで重要なポイントは、上方のマスをチェックしていない点です。これは、すでに走査済みのペアを二重に確認する無駄を避けるためです。各ナイトのペアは必ず一度だけ評価されるため、計算量を半分に抑えることができます。

それでは、実際の実装例を見てみましょう。

実装例

class Solution:
   def solve(self, A):
      row, col = len(A), len(A[0])
      for r in range(row):
         for c in range(col):
            if A[r][c]:
               for nr, nc in ((r+1, c-2), (r+1, c+2), (r+2, c-1), (r+2, c+1)):
                  if 0 <= nr < row and 0 <= nc < col and A[nr][nc]:
                     return True
      return False

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

入力

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

出力

True

このコードでは、盤面全体を一度だけ走査し、各ナイトについて下方4方向のみを確認するため、時間計算量は O(行数 × 列数) となり、非常に効率的です。チェス盤のようなグリッド問題において、対称性を利用して探索範囲を絞るテクニックは、他の多くの問題にも応用できます。