Pythonで無限チェス盤上のN個のナイト配置からキングがチェックメイトかどうかを判定する方法

問題の概要

通常のチェスと同じルールが適用される無限チェス盤を考えます。盤上には N 個のナイト(騎士)が配置されており、これらの座標とキングの座標が与えられたとき、そのキングがチェックメイトの状態にあるかどうかを判定します。盤面が無限であるため、座標は非常に大きな値になる可能性があります(−10⁹ ≤ x, y ≤ 10⁹)。

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

• ナイトの位置:[[2,1], [1,3], [3,6], [5,5], [6,1], [7,3]]
• キングの位置:[4,3]

この場合、キングには安全な移動先が一切存在しないため、出力は True(チェックメイト)になります。

解法のアプローチ

この問題は、各ナイトの攻撃範囲をあらかじめハッシュマップ(辞書)に記録しておき、キングの移動候補マスがすべて攻撃範囲内に含まれているかを確認することで効率的に解けます。具体的な手順は以下のとおりです。

1. 新しい辞書(my_dict)を用意します。
2. 各ナイトの座標 (x, y) について、ナイト自身の位置と、ナイトが攻撃できる 8 マス((x±2, y±1)、(x±1, y±2))をすべて辞書に登録します。
3. キングの周囲のマスを順に調べます(i、j を −1〜1 の範囲で動かし、i ≠ 0 かつ j ≠ 0 のマスを対象とします)。
4. 調査中のマスが辞書に存在しない(=どのナイトにも攻撃されていない)場合、キングはそこへ逃げられるため False を返します。
5. すべてのマスが攻撃範囲内であれば、キングには有効な手が残っていないため True(チェックメイト)を返します。

ナイトの攻撃範囲の登録は O(N)、キング周辺の確認は高々 8 マス程度の定数時間で済むため、全体の計算量は O(N) となります。そのため、座標が ±10⁹ という巨大な値になるケースでも、盤面を実際に展開することなく現実的な時間で処理できます。

実装例(Python)

理解を深めるために、実際のコードを見てみましょう。なお、未登録のキーへアクセスした際に KeyError が発生しないよう、ここでは collections.defaultdict を使用しています。

from collections import defaultdict

def is_checkmate(a, n, king_pos):
    my_dict = defaultdict(int)
    # 各ナイトの位置と、そのナイトが攻撃できる8マスを記録
    for i in range(n):
        x = a[i][0]
        y = a[i][1]
        my_dict[(x, y)] = 1
        my_dict[(x - 2, y + 1)] = 1
        my_dict[(x - 2, y - 1)] = 1
        my_dict[(x + 1, y + 2)] = 1
        my_dict[(x + 1, y - 2)] = 1
        my_dict[(x - 1, y + 2)] = 1
        my_dict[(x + 2, y + 1)] = 1
        my_dict[(x + 2, y - 1)] = 1
        my_dict[(x - 1, y - 2)] = 1

    # キングの周囲のマスに安全な場所があるか確認
    for i in range(-1, 2):
        for j in range(-1, 2):
            nx = king_pos[0] + i
            ny = king_pos[1] + j
            if i != 0 and j != 0:
                if not my_dict[(nx, ny)]:
                    return False
    return True

a = [[2,1],[1,3],[3,6],[5,5],[6,1],[7,3]]
n = len(a)
pos = [4, 3]
print(is_checkmate(a, n, pos))

入力

[[2,1],[1,3],[3,6],[5,5],[6,1],[7,3]], 6, [4, 3]

出力

True

まとめ

本記事では、無限チェス盤上に配置された N 個のナイトに対して、キングがチェックメイトの状態かどうかを判定する方法を解説しました。ポイントは、各ナイトが攻撃可能な 8 マスを辞書に事前登録しておくことで、巨大な座標空間でも高速に判定できる点です。この手法は、盤面を明示的にメモリ上に保持できない大規模なグリッド問題全般に応用できる有用なテクニックです。