問題概要

特定形状を持つ 10 マスの格子（図参照）に、0 から 9 の各数字を重複なく 1 つずつ配置する必要があります。配置には以下の制約が課されます。

• 上下左右および斜め方向のどちらでも、隣り合うマスの数字の絶対値の差が「1」であってはならない。

  ┌─┬─┬─┐
  │0│1│2│
  ├─┼─┼─┼─┤
  │3│4│5│6│7│
  ├─┼─┼─┤
  │ │ │
  └─┴─┴─┘
      8│9│

この条件を満たす可能な配置パターンの総数を計算することが目標です。

解法アプローチ

本問題は、10 個の異なる整数を格子に配置するため、「順列（Permutation）」の生成が適応可能です。0 から 9 までの数字を並べ替えたすべてのケースを生成し、それぞれの並びに対して「隣接チェック」という制約条件を満たすかを判定する手法を採用します。

判定ロジックとしては、ある数字 $x$ とその周辺の数字 $y$ を比較し、$|x - y| = 1$ となるペアが存在すればその順列は不適合となります。これをすべての隣接関係について検証を行います。

コード実装の詳細

C++ の標準ライブラリ機能である std::next_permutation を利用して順列列挙を行い、手動で定義された隣接関係リストに基づいて妥当性を評価する構成に変更しています。

<table cellpadding="0" cellspacing="0" style="border-collapse: collapse; border: none;">
<tbody>
<tr style="background-color: #f0f0f0;">
<td style="padding: 5px; border-bottom: 1px solid #ddd;" colspan="2">
<b>Header 1</b>
</td>
</tr>
<tr>
<td style="padding: 5px; border-bottom: 1px solid #ddd;" colspan="2">
<b>Body 1</b>
</td>
</tr>
</tbody>
</table>

#include <iostream>
#include <algorithm>
#include <cmath>
#include <utility>
#include <vector>

using namespace std;

// 格子の頂点間接続関係（インデックスベース）
// 元の論理構造と同じ隣接関係を保つため、データ駆動型に変換
const vector<pair<int, int>> edges = {
    {0, 1}, {0, 3}, {0, 4}, {0, 5},
    {1, 2}, {1, 4}, {1, 5}, {1, 6},
    {2, 5}, {2, 6},
    {3, 4}, {3, 7}, {3, 8},
    {4, 5}, {4, 7}, {4, 8}, {4, 9},
    {5, 6}, {5, 8}, {5, 9},
    {6, 9},
    {7, 8}, {8, 9}
};

// 現在の設定が制約を満たすか検証
bool isValidConfiguration(const vector<int>&numArr)&;
{
    for (const auto& edge : edges) {
        if (abs(numArr[edge.first] - numArr[edge.second]) == 1) {
            return false;
        }
    }
    return true;
}

int main()
{
    vector<int> nums;
    for (int i = 0; i < 10; ++i) nums.push_back(i);

    int validCount = 0;

    // 辞書式順列を生成しながら検証を行う
    do {
        if (isValidConfiguration(nums)) {
            validCount++;
        }
    } while (next_permutation(nums.begin(), nums.end()));

    cout << validCount << endl;

    return 0;
}

解説

上記の実装では、従来のハードコードされた if 文の羅列を、エッジリスト（edgesベクタ）として抽象化しました。これにより、隣接定義の変更が必要な場合やメンテナンス性が向上します。ループ処理の中で next_permutation が配列を更新するたびに isValidConfiguration が実行され、条件を満たす場合にカウンターが増加します。最終的な出力値は 1580 となっています。