【C++】N個のナイトがいる変形チェスボードで、キングが有効な手を指せるかどうかを判定する方法

概要

通常のチェスと同じルールが適用される、無限に広がるチェスボードを考えます。ボード上にはN個のナイトが配置されており、それぞれの座標（-10^9 ≤ x, y ≤ 10^9）と、キングの座標が与えられます。このとき、キングがチェックメイトの状態にあるかどうかを判定するのが本記事の課題です。

入力例1

a1[] = { { 2, 1 }, { 1, 3 }, { 3, 6 }, { 5, 5 }, { 6, 1 }, { 7, 3 } }、king -> {4, 3}

出力：

Yes

キングはどの方向にも動くことができず、チェックメイトの状態です。

入力例2

a1[] = { { 1, 1 } }、king -> {3, 4}

出力：

No

キングは有効な手を指すことができます。

解法のアプローチ

チェスの駒の中でも、ナイトの動きは特に独特です。ナイトは「横に2マス・縦に1マス」、あるいは「縦に2マス・横に1マス」移動します。つまり、その移動は常に「L」字形となり、1手で到達できるマスは最大8か所です。

この性質を利用して、各ナイトが攻撃できる（移動できる）すべての座標を、ペアをキーとするハッシュマップ（map）に記録していきます。そのうえで、キングが周囲8マスのどこにも移動できない場合――すなわち、隣接するすべての座標がすでにナイトの移動範囲としてハッシュされている場合――「チェックメイト」と判定します。

C++による実装例

// 変形チェスボード上にN個のナイトがいるとき、
// キングが有効な手を指せるかどうかを検証するC++プログラム
#include <bits/stdc++.h>
using namespace std;

bool checkCheckMate1(pair<int, int> a1[], int n1, int kx1, int ky1) {
    // 座標を記録するためのハッシュマップ
    map<pair<int, int>, int> mpp1;

    // 与えられたN個のナイトについて処理
    for (int i = 0; i < n1; i++) {
        int x = a1[i].first;
        int y = a1[i].second;

        // ナイトが到達できる「L」字形の座標をすべて記録

        // 現在位置
        mpp1[{ x, y }] = 1;
        // 1番目の移動
        mpp1[{ x - 2, y + 1 }] = 1;
        // 2番目の移動
        mpp1[{ x - 2, y - 1 }] = 1;
        // 3番目の移動
        mpp1[{ x + 1, y + 2 }] = 1;
        // 4番目の移動
        mpp1[{ x + 1, y - 2 }] = 1;
        // 5番目の移動
        mpp1[{ x - 1, y + 2 }] = 1;
        // 6番目の移動
        mpp1[{ x + 2, y + 1 }] = 1;
        // 7番目の移動
        mpp1[{ x + 2, y - 1 }] = 1;
        // 8番目の移動
        mpp1[{ x - 1, y - 2 }] = 1;
    }

    // 周囲の座標をすべて確認
    for (int i = -1; i < 2; i++) {
        for (int j = -1; j < 2; j++) {
            int nx = kx1 + i;
            int ny = ky1 + j;
            if (i != 0 && j != 0) {
                // 移動可能なマスが存在するかどうかを検証
                if (!mpp1[{ nx, ny }]) {
                    return true;
                }
            }
        }
    }

    // 有効な手が存在しない
    return false;
}

// ドライバーコード
int main() {
    pair<int, int> a1[] = { { 2, 1 }, { 1, 3 }, { 3, 6 }, { 5, 5 }, { 6, 1 }, { 7, 3 } };
    int n1 = sizeof(a1) / sizeof(a1[0]);
    int x = 4, y = 3;
    if (checkCheckMate1(a1, n1, x, y))
        cout << "Not Checkmate!";
    else
        cout << "Yes its checkmate!";
    return 0;
}

出力

Yes its checkmate!

この実行結果から、キングは周囲のどのマスにも逃げることができず、チェックメイトであると判定されたことが分かります。

計算量

時間計算量はO(N)、空間計算量もO(N)です。各ナイトにつき定数個（最大9か所）の座標をハッシュマップに登録し、最後にキングの周囲を定数回走査するだけで済むため、ナイトの数Nに対して線形時間で判定できます。