この記事では、C++を使用して4x4のランダムなラテン方陣を生成する方法を解説します。プログラミング初心者の方にも理解しやすいように、順を追って説明します。

1. ラテン方陣とは？

ラテン方陣は、n×nの行列で、すべての行と列において異なる数字が現れ、かつその数字が1からnまでの連続した自然数で構成されるものです。これは数学的なパズルであり、プログラミングの練習としても人気のある課題です。

2. ラテン方陣の性質

ラテン方陣は以下の性質を持ちます。

各行と列には異なる数字が一度だけ現れる。
数字の範囲は1からnまでの連続した自然数。

3. C++での実装手順

必要なライブラリのインクルード

まず、プログラム内で使用するライブラリをインクルードします。

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>

ランダム性を持たせる

乱数を生成するために、ランダムシードを初期化します。

srand(time(0)); // ランダムシードの初期化

行と列の重複をチェックする

ラテン方陣を生成する際に、各行と列に重複がないように確認します。

bool isValid(const std::vector<std::vector<int>>& matrix, int row, int col, int num) {
    for (int i = 0; i < matrix.size(); ++i) {
        if (matrix[row][i] == num || matrix[i][col] == num) {
            return false;
        }
    }
    return true;
}

バックトラッキング法による解法

バックトラッキング法を使用して、ラテン方陣を生成します。

bool solveLatinSquare(std::vector<std::vector<int>>& matrix, int row, int col) {
    if (row == matrix.size() - 1 && col == matrix.size()) {
        return true;
    }
    if (col == matrix.size()) {
        row++;
        col = 0;
    }

    std::vector<int> randomNums(matrix.size());
    for (int i = 0; i < matrix.size(); ++i) {
        randomNums[i] = i + 1;
    }

    for (int i = 0; i < matrix.size(); ++i) {
        int randomIndex = rand() % randomNums.size();
        int num = randomNums[randomIndex];
        randomNums.erase(randomNums.begin() + randomIndex);

        if (isValid(matrix, row, col, num)) {
            matrix[row][col] = num;
            if (solveLatinSquare(matrix, row, col + 1)) {
                return true;
            }
            matrix[row][col] = 0;
        }

        randomNums.insert(randomNums.begin() + randomIndex, num);
    }

    return false;
}

4. サンプルコードの解説

// インクルードと名前空間の指定

// isValid関数の定義

// solveLatinSquare関数の定義

int main() {
    // 定数と行列の初期化

    // ランダムシードの初期化

    if (solveLatinSquare(latinSquare, 0, 0)) {
        // ラテン方陣が生成された場合の処理
    } else {
        std::cout << "解が存在しません。" << std::endl;
    }

    return 0;
}

5. プログラムの実行と結果

全体のプログラムは以下の通りです。

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>

using namespace std;

bool isValid(const vector<vector<int>>& matrix, int row, int col, int num) {
    for (int i = 0; i < matrix.size(); i++) {
        if (matrix[row][i] == num || matrix[i][col] == num) {
            return false;
        }
    }
    return true;
}

bool solveLatinSquare(vector<vector<int>>& matrix, int row, int col) {
    if (row == matrix.size() - 1 && col == matrix.size()) {
        return true;
    }
    if (col == matrix.size()) {
        row++;
        col = 0;
    }

    vector<int> randomNums(matrix.size());
    for (int i = 0; i < matrix.size(); i++) {
        randomNums[i] = i + 1;
    }

    for (int i = 0; i < matrix.size(); i++) {
        int randomIndex = rand() % randomNums.size();
        int num = randomNums[randomIndex];
        randomNums.erase(randomNums.begin() + randomIndex);

        if (isValid(matrix, row, col, num)) {
            matrix[row][col] = num;
            if (solveLatinSquare(matrix, row, col + 1)) {
                return true;
            }
            matrix[row][col] = 0;
        }

        randomNums.insert(randomNums.begin() + randomIndex, num);
    }

    return false;
}

int main() {
    const int n = 4;
    vector<vector<int>> latinSquare(n, vector<int>(n, 0));

    srand(time(0)); // ランダムシードの初期化

    if (solveLatinSquare(latinSquare, 0, 0)) {
        cout << "4x4 ラテン方陣:" << endl;
        for (const auto& row : latinSquare) {
            for (int num : row) {
                cout << num << " ";
            }
            cout << endl;
        }
    } else {
        cout << "解が存在しません。" << endl;
    }

    return 0;
}

プログラムを実行すると、4x4のランダムなラテン方陣が生成されます。もし解が存在しない場合は、「解が存在しません。」と表示されます。解が生成されるたびに異なる結果が得られることに注意してください。

この記事では、C++を使用して4x4のランダムなラテン方陣を生成する手順を詳しく解説しました。プログラミング初心者の方でも理解しやすいように説明しましたので、ぜひ試してみてください。

My note for history

学んだこと、感じたことをまとめたノート

C++でラテン方陣を作成する方法【初心者向けガイド】