JavaScriptで隣接する2数の合計が完全平方数となる配列を構築する方法

本記事では、数値 n を受け取り、1からnまでの整数を隣り合う2つの数の合計が必ず完全平方数（平方数）になるように並べた配列を返すJavaScript関数を実装します。一見単純そうですが、すべての並び順を試すのは非現実的なため、ここでは「バックトラッキング」という手法を用いて効率的に解きます。

問題の定義

作成する関数は以下の条件を満たす必要があります。

• 戻り値の配列には、1からnまでの整数がそれぞれちょうど1回ずつ含まれること
• 隣接するどの2つの数を足しても、結果が平方数（1, 4, 9, 16, 25, …）になること
• 条件を満たす並びが存在しない場合は false を返すこと

なお、この条件を満たす並びが常に存在するとは限りません。例えば n = 2 の場合、1 + 2 = 3 は平方数ではないため解は存在せず、関数は false を返します。

アプローチ：バックトラッキング

この問題は、制約付きの順列生成と捉えることができます。以下の手順で探索を進めます。

1. 1からnまでの各数字を候補として順に試す
2. すでに使用済みの数字はスキップする
3. 現在の配列の先頭にある数字との合計が平方数にならない候補もスキップする
4. 条件を満たす数字を先頭に追加し、再帰的に残りの数字を処理する
5. すべての数字を使い切れたら成功として true を返す。途中で行き詰まったら、直前の選択を取り消して（バックトラックして）別の候補を試す

実装コード

const n = 15;

const buildSquaresArray = (n = 1, res = []) => {
  const helper = (res, set, n) => {
    // すべての数字を使い切ったら成功
    if (set.size === n) {
      return true;
    }
    for (let i = 1; i <= n; i++) {
      // 使用済みの数字はスキップ
      if (set.has(i)) {
        continue;
      }
      // 先頭の数字との合計が平方数にならない候補はスキップ
      if (res.length && Math.sqrt(res[0] + i) % 1 !== 0) {
        continue;
      }
      // 数字を選んで先頭に追加
      set.add(i);
      res.unshift(i);
      if (helper(res, set, n)) {
        return true;
      }
      // 行き詰まったら選択を取り消す（バックトラック）
      res.shift();
      set.delete(i);
    }
    return false;
  };
  return helper(res, new Set(), n) ? res : false;
};

console.log(buildSquaresArray(n));

出力結果

[
   9,
   7,
   2,
  14,
  11,
   5,
   4,
  12,
  13,
   3,
   6,
  10,
  15,
   1,
   8
]

コードのポイント解説

平方数の判定方法

ある数 x が平方数かどうかは、その平方根が整数であるかどうかで判定できます。コード内の Math.sqrt(res[0] + i) % 1 !== 0 は、「2数の合計の平方根に小数部分がある（＝平方数ではない）」場合にスキップするという意味になります。

Setによる使用済み数字の管理

Set を使うことで、ある数字が既に使われたかどうかを O(1) で確認・登録・削除できます。これにより同じ数字が複数回配列に入ることを防ぎます。

先頭への追加と取り消し

この実装では unshift() で新しい数字を配列の先頭に追加し、失敗時には shift() で取り除きます。これにより「直前の状態へ戻る」バックトラッキングが実現されています。

結果の検証

得られた配列の隣接する2数の和を実際に確かめてみましょう。

• 9 + 7 = 16（4²）
• 7 + 2 = 9（3²）
• 2 + 14 = 16（4²）
• 14 + 11 = 25（5²）
• 11 + 5 = 16（4²）
• 5 + 4 = 9（3²）
• 4 + 12 = 16（4²）
• 12 + 13 = 25（5²）
• 13 + 3 = 16（4²）
• 3 + 6 = 9（3²）
• 6 + 10 = 16（4²）
• 10 + 15 = 25（5²）
• 15 + 1 = 16（4²）
• 1 + 8 = 9（3²）

すべての隣接ペアの合計が平方数になっており、条件を正しく満たしていることが確認できます。

まとめ

本記事では、バックトラッキングを用いて「隣接する2数の合計が常に平方数となる配列」を構築する方法を紹介しました。「候補の選択 → 条件チェック → 再帰 → 失敗時の取り消し」という流れは、数独やNクイーン問題など、多くの組合せ探索問題にも応用できる基本的なパターンです。ぜひ他の問題にも活用してみてください。