C++で変形ナイト（Modified Knight）が到達可能なすべてのマスを数える方法

問題の概要

本記事では、変形ナイト（Modified Knight）が到達できるすべての位置の数を求めるC++プログラムについて解説します。

前提として、8×8のチェス盤が与えられます。私たちのタスクは、指定された手数において、変形ナイトが到達できるマスの総数を計算することです。

変形ナイトの移動パターン

標準的なチェスのナイトは「縦2・横1」「縦1・横2」の8方向にしか移動できません。しかし、この記事で扱う変形ナイトは、それに加えて斜めに隣接するマス（例：左上・右下など）への移動も許容しており、合計12方向へ移動することができます。

アルゴリズムの考え方

この問題は深さ優先探索（DFS）を使って解くのが一般的です。処理の流れは以下のとおりです。

1. 現在位置から12方向すべての移動先に対して、再帰的に探索を実行します。
2. 盤面の外に出た場合、または指定された手数を超えた場合は、その経路の探索を打ち切ります（境界チェック）。
3. ちょうど指定した手数で到達したマスを、訪問管理用の2次元配列（visited）に記録します。
4. 最後にvisited配列全体を走査し、フラグが立っているマスの数を数えて答えとします。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

// 到達可能な位置を探索する関数
void findSteps(int current_row, int current_column, int curr, int board_size, int steps, int* visited) {
    // 境界チェック
    if (current_row >= board_size || current_row < 0
        || current_column >= board_size || current_column < 0
        || curr > steps) {
        return;
    }
    if (curr == steps) {
        *((visited + (current_row)*board_size) + current_column) = 1;
        return;
    }
    findSteps(current_row - 2, current_column - 1, curr + 1, board_size, steps, visited);
    findSteps(current_row - 2, current_column + 1, curr + 1, board_size, steps, visited);
    findSteps(current_row - 1, current_column - 2, curr + 1, board_size, steps, visited);
    findSteps(current_row - 1, current_column - 1, curr + 1, board_size, steps, visited);
    findSteps(current_row - 1, current_column + 1, curr + 1, board_size, steps, visited);
    findSteps(current_row - 1, current_column + 2, curr + 1, board_size, steps, visited);
    findSteps(current_row + 1, current_column - 2, curr + 1, board_size, steps, visited);
    findSteps(current_row + 1, current_column - 1, curr + 1, board_size, steps, visited);
    findSteps(current_row + 1, current_column + 1, curr + 1, board_size, steps, visited);
    findSteps(current_row + 1, current_column + 2, curr + 1, board_size, steps, visited);
    findSteps(current_row + 2, current_column - 1, curr + 1, board_size, steps, visited);
    findSteps(current_row + 2, current_column + 1, curr + 1, board_size, steps, visited);
    return;
}

int countSteps(int current_row, int current_column, int board_size, int steps) {
    int visited[board_size][board_size];
    for (int i = 0; i < board_size; i++) {
        for (int j = 0; j < board_size; j++) {
            visited[i][j] = 0;
        }
    }
    int answer = 0;
    findSteps(current_row, current_column, 0, board_size, steps, (int*)visited);
    for (int i = 0; i < board_size; i++) {
        for (int j = 0; j < board_size; j++) {
            if (visited[i][j] == 1) {
                answer++;
            }
        }
    }
    return answer;
}

int main() {
    int board_size = 8, steps = 1;
    int current_row = 4, current_column = 4;
    cout << countSteps(current_row, current_column, board_size, steps);
    return 0;
}

出力結果

12

コードの詳細解説

findSteps関数

この関数は、再帰的にナイトの移動をシミュレートします。まず、行・列が盤面の範囲内にあるか、そして現在の手数currが上限stepsを超えていないかを確認します。条件を満たさない場合は即座にreturnして探索を打ち切ります。currがstepsと一致した時点で、そのマスに対応するvisited配列の要素を1に設定します。それ以外の場合は、12方向それぞれの移動先に対して自分自身を再帰呼び出ししていきます。

countSteps関数

visited配列をすべて0で初期化した後、findStepsを呼び出して探索を実行します。探索完了後、visited配列を走査し、値が1になっているマス（＝ちょうど指定手数で到達できたマス）の個数をカウントして返します。

main関数

盤面サイズ8、手数1、開始位置(4, 4)を設定し、countStepsを呼び出して結果を出力します。この例では、盤面中央付近から1手で到達できるマスが12個あるため、出力は12となります。

計算量について

各手ごとに最大12方向の分岐が発生するため、時間計算量はO(12^steps)となり、手数が増えるほど指数関数的に増大します。一方、空間計算量はvisited配列と再帰スタックの分だけ必要となるため、O(board_size²)です。手数が大きいケースでは、メモ化（動的計画法）を組み合わせることで、同じ状態の再計算を避け、大幅な高速化が期待できます。