C++でN×Nチェス盤に配置できるビショップの最大数を求める方法

問題概要

チェス盤のサイズを表す整数 N が入力として与えられます。この問題では、任意の N に対して、N×N のチェス盤上に互いに攻撃し合わないようにビショップ（bishop）を最大何個配置できるかを求めます。

まず、具体例を使って理解していきましょう。

例1

入力： N = 2

出力： N×N チェス盤に配置できるビショップの最大数 ― 2

説明： 2×2 のチェス盤の場合、互いに干渉しない位置は図示された場所のみです。つまり、2×2 の盤面に配置できるビショップは最大 2 個となります。

例2

入力： N = 5

出力： N×N チェス盤に配置できるビショップの最大数 ― 8

プログラムで使用するアプローチ

• チェス盤のサイズとして整数値 N を入力として受け取ります。
• この N を引数として totalBishops(int n) 関数に渡します。
• N < 1 の場合は無効な入力とみなし、ビショップの数は 0 とします。
• N = 1 の場合、配置できるマスは 1 つだけなので、ビショップの数は 1 となります。
• それ以外の場合、ビショップの数は 2 × (N − 1) となります。
• 計算結果を変数 bishops に格納します。
• 結果を返します。

ポイント： ビショップは斜め方向にしか移動できないため、同じ色のマスに複数置くと衝突する可能性があります。しかし、盤面の外周（最外周の2列）をうまく利用することで、2 × (N − 1) 個まで衝突なく配置できることが数学的に証明されています。

コード例

#include <iostream>
// 配置可能なビショップの最大数を返す関数
int totalBishops(int n){
    int bishops = 0;
    if (n < 1)
        bishops = 0;
    else if (n == 1)
        bishops = 1;
    else
        bishops = 2 * (n - 1);
    return bishops;
}
int main(){
    int N = 15; // チェス盤のサイズ N×N
    printf("%d", totalBishops(N));
    return 0;
}

出力

上記のコードを実行すると、以下の出力が生成されます。

28

N = 15 の場合、2 × (15 − 1) = 28 となり、15×15 のチェス盤には最大 28 個のビショップを互いに攻撃し合わないように配置できることがわかります。このアルゴリズムの時間計算量は O(1)、空間計算量も O(1) と非常に効率的です。