C++でチェス盤に含まれる正方形の総数を求めるプログラム

この記事では、チェス盤のサイズ n が与えられたとき、その盤面に含まれるすべての正方形の総数をC++で求めるプログラムを解説します。

問題の概要

チェス盤に含まれる正方形の数を求めるには、盤面の内部に存在する正方形をすべてのサイズについて数える必要があります。具体的には、1×1、2×2、3×3 … n×n のように、各サイズごとの正方形の組み合わせをすべて合計します。

具体例

入力: n = 4

出力: 30

1×1 の正方形 → 16 個
2×2 の正方形 → 9 個
3×3 の正方形 → 4 個
4×4 の正方形 → 1 個
正方形の総数 = 16 + 9 + 4 + 1 = 30

なお、標準的な8×8のチェス盤の場合、この計算式により204個の正方形が存在することになります。

解法アプローチ：二乗和の公式を利用する

各サイズ k の正方形の数は (n − k + 1)² 個になります。したがって、総数は1から n までの平方数の和として表せます。

sum(1) = 1
sum(2) = 1 + 4 = 5
sum(3) = 1 + 4 + 9 = 14
sum(4) = 1 + 4 + 9 + 16 = 30

この規則性を一般化すると、次の有名な二乗和の公式が得られます。

sum = 1² + 2² + 3² + 4² + … + n²
sum = n × (n + 1) × (2n + 1) / 6

この公式を使えば、ループで毎回足し合わせることなく、O(1) の定数時間で答えを計算できます。

C++での実装例

#include <iostream>
using namespace std;

int calcSquaresCount(int n){
    int squareCount = ((n * (n + 1) * (2 * n + 1)) / 6);
    return squareCount;
}

int main() {
    int n = 6;
    cout << "サイズ " << n << "×" << n << " の盤面に含まれる正方形の総数は "
         << calcSquaresCount(n);
    return 0;
}

実行結果

サイズ 6×6 の盤面に含まれる正方形の総数は 91

まとめ

n×n のチェス盤に含まれる正方形の総数は、二乗和の公式 n(n+1)(2n+1)/6 を使うことで簡単かつ効率的に求められます。計算量は O(1)、空間計算量も O(1) であり、非常に効率的な解法です。ただし、大きな n を扱う場合はオーバーフローに注意し、必要に応じて long long 型などのより大きな整数型を使用することをおすすめします。