C++でチェスのナイトの有効な移動手を数える方法

問題の概要

本記事では、m×n のチェス盤が与えられたとき、ナイト(騎士)がその位置から移動できる有効なマスの総数を求める方法を解説します。

盤面は二次元配列 board で表され、駒が置かれている位置は 1 で示されます。つまり board[i][j] = 1 ならば、そのマスには何らかの駒が存在します。さらに、ナイトの現在位置も与えられます。ここではすべての駒が同じ色である、すなわち攻撃(相手の駒を取る動き)は発生しないものと仮定します。

ナイトの移動ルール

ナイトはチェスの駒の中でも特殊な動きをする駒で、次の2パターンのいずれかで移動します。

• 横方向に2マス、縦方向に1マス移動
• 縦方向に2マス、横方向に1マス移動

これにより、ナイトは最大8方向へ移動できることになります。

入力例と出力例

具体的な例を使って問題を確認しましょう。

入力:

board[][] = {
    { 0, 1, 0, 0 },
    { 0, 0, 1, 1 },
    { 0, 1, 1, 0 },
    { 0, 0, 0, 1 }
};
Position : (1,1)

出力:

4

解法のアプローチ

この問題を解く鍵は、「有効な移動」とは何かを正しく判定することです。ナイトの移動先が有効であるための条件は次の2つです。

• 移動先がチェス盤の範囲内にあること
• 移動先に他の駒が存在しないこと(該当マスの値が 0 であること)

アルゴリズムの手順は以下の通りです。

1. ナイトが取り得る8方向の移動オフセット(Xmoves・Ymoves)を配列として定義します。
2. 現在位置に各オフセットを加算し、移動先の座標を計算します。
3. 各移動先について、盤面の範囲内かつ駒が存在しないかどうかをチェックします。
4. 条件を満たす移動ごとにカウントを増やし、最終的な合計を返します。

この方法なら、計算量は O(8) = O(1) と一定であり、非常に効率的です。

C++による実装例

上記の解法を実装したプログラムが以下です。

#include <bits/stdc++.h>
#define N 8
#define M 8
using namespace std;
int countPossibleMoves(int mat[N][M], int p, int q){
    int Xmoves[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
    int Ymoves[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
    int count = 0;
    for (int i = 0; i < 8; i++) {
        int x = p + Xmoves[i];
        int y = q + Ymoves[i];
        if (x>=0 && y>=0 && x<N && y<M && mat[x][y]==0)
            count++;
    }
    return count;
}
int main(){
    int mat[N][M] = { { 0, 1, 0, 0 },
        { 0, 0, 1, 1 },
        { 0, 1, 1, 0 },
        { 0, 0, 0, 1 }};
    int position[2] = {1,1};
    cout<<"Total number of moves possible for Knight from position ("<<position[0]<<" , "<<position[1]<<") are : ";
    cout<<countPossibleMoves(mat, position[0], position[1]);
    return 0;
}

実行結果

Total number of moves possible for Knight from position (1 , 1) are : 4

まとめ

このプログラムでは、ナイトの8つの移動候補をすべて列挙し、盤面の境界チェックと駒の有無チェックを行うことで、有効な移動手のみをカウントしています。位置 (1,1) からは4つの有効な移動が存在するため、出力は 4 となります。

同様の考え方は、チェス盤サイズや初期位置が変わってもそのまま適用でき、盤上ゲームのAI開発や経路探索問題の基礎としても応用できる汎用的な手法です。