C#で魔方陣をつくる

n×n 個の正方形の方陣に数字を配置し、縦・横・対角線のすべての列でその列の数の合計が同じになるものを魔方陣といいます。今回はC#で魔方陣をつくります。

まず3×3の魔方陣について。1～9までの整数で順列をつくり、縦横斜めが同じになるかどうかを調べます。1～9までの総和と縦3列の総和は同じなので、1～9までの総和 / 3 ＝ 15が各列の合計となります。

まずは順列をつくります。

public partial class Form1 : Form
{
    /// <summary>
    /// min ～ max の整数から順列をつくる
    /// </summary>
    List<List<int>> GetPermutation(int min, int max)
    {
        List<int> vs1 = new List<int>();
        for(int i = min; i <= max; i++)
            vs1.Add(i);

        List<List<int>> list = new List<List<int>>();
        for(int i = min; i <= max; i++)
        {
            List<int> vs2 = new List<int>();
            vs2.Add(i);
            list.Add(vs2);
        }

        while(true)
        {
            List<List<int>> templist = new List<List<int>>();

            foreach(var list1 in list)
            {
                var vs3 = vs1.Except(list1).ToList();
                if(vs3.Count == 0)
                {
                    return list;
                }

                foreach(int i in vs3)
                {
                    List<int> list3 = new List<int>(list1);
                    list3.Add(i);
                    templist.Add(list3);
                }
            }
            list = templist;
        }
    }
}

public partial class Form1 : Form

{

/// <summary>

/// min ～ max の整数から順列をつくる

/// </summary>

List<List<int>> GetPermutation(int min, int max)

{

List<int> vs1 = new List<int>();

for(int i = min; i <= max; i++)

vs1.Add(i);

List<List<int>> list = new List<List<int>>();

for(int i = min; i <= max; i++)

{

List<int> vs2 = new List<int>();

vs2.Add(i);

list.Add(vs2);

}

while(true)

{

List<List<int>> templist = new List<List<int>>();

foreach(var list1 in list)

{

var vs3 = vs1.Except(list1).ToList();

if(vs3.Count == 0)

{

return list;

}

foreach(int i in vs3)

{

List<int> list3 = new List<int>(list1);

list3.Add(i);

templist.Add(list3);

}

list = templist;

}

次に魔方陣になっているかどうか調べるメソッドを示します。

public partial class Form1 : Form
{
    /// <summary>
    /// 縦・横・斜めがsumに等しいか調べる
    /// </summary>
    bool IsMahojin(List<int> vs, int sum)
    {
        int line = (int)Math.Sqrt(vs.Count);

        // 二元配列に変換する
        int[,] vs1 = new int[line, line];
        int i = 0;
        for(int row =0; row < line; row++)
        {
            for(int colum = 0; colum < line; colum++)
            {
                vs1[row, colum] = vs[i];
                i++;
            }
        }

        // 横列のチェック
        for(int row = 0; row < line; row++)
        {
            int sumTemp = 0;
            for(int colum = 0; colum < line; colum++)
            {
                sumTemp += vs1[row, colum];
            }
            if(sumTemp != sum)
                return false;
        }

        // 縦列のチェック
        for(int colum = 0; colum < line; colum++)
        {
            int sumTemp = 0;
            for(int row = 0; row < line; row++)
            {
                sumTemp += vs1[row, colum];
            }
            if(sumTemp != sum)
                return false;
        }

        // 斜めのチェック
        int sumTemp1 = 0;
        for(int colum = 0; colum < line; colum++)
        {
            sumTemp1 += vs1[line - colum - 1, colum];
        }
        if(sumTemp1 != sum)
            return false;

        int sumTemp2 = 0;
        for(int colum = 0; colum < line; colum++)
        {
            sumTemp2 += vs1[colum, colum];
        }
        if(sumTemp2 != sum)
            return false;

        return true;
    }
}

public partial class Form1 : Form

{

/// <summary>

/// 縦・横・斜めがsumに等しいか調べる

/// </summary>

bool IsMahojin(List<int> vs, int sum)

{

int line = (int)Math.Sqrt(vs.Count);

// 二元配列に変換する

int[,] vs1 = new int[line, line];

int i = 0;

for(int row =0; row < line; row++)

{

for(int colum = 0; colum < line; colum++)

{

vs1[row, colum] = vs[i];

i++;

}

// 横列のチェック

for(int row = 0; row < line; row++)

{

int sumTemp = 0;

for(int colum = 0; colum < line; colum++)

{

sumTemp += vs1[row, colum];

}

if(sumTemp != sum)

return false;

}

// 縦列のチェック

for(int colum = 0; colum < line; colum++)

{

int sumTemp = 0;

for(int row = 0; row < line; row++)

{

sumTemp += vs1[row, colum];

}

if(sumTemp != sum)

return false;

}

// 斜めのチェック

int sumTemp1 = 0;

for(int colum = 0; colum < line; colum++)

{

sumTemp1 += vs1[line - colum - 1, colum];

}

if(sumTemp1 != sum)

return false;

int sumTemp2 = 0;

for(int colum = 0; colum < line; colum++)

{

sumTemp2 += vs1[colum, colum];

}

if(sumTemp2 != sum)

return false;

return true;

}

GetResult()は処理の結果を取得するメソッドです。

public partial class Form1 : Form
{
    void GetResult()
    {
        int min = 1;
        int max = 9;

        // 順列を取得する
        List<List<int>> lists = GetPermutation(min, max);

        int count = max - min + 1;
        int lineCount = (int)Math.Sqrt(count);
        int allSum = max * (max + 1) / 2;
        int lineSum = allSum / lineCount;

        // 取得した順列のうち魔方陣になっているものを取得する
        List<List<int>> ret = new List<List<int>>();
        foreach(var list2 in lists)
        {
            if(IsMahojin(list2, lineSum))
                ret.Add(list2);
        }

        StringBuilder sb = new StringBuilder();
        foreach(List<int> list in ret)
            sb.Append(String.Join(", ", list.Select(x => x.ToString()).ToArray()) + "\n");

        Invoke((Action)(() => {
            // 回転させたり裏返すと一致するものは同じとしてカウントする
            string str1 = String.Format("{0:#,0}種類\n\n", ret.Count / 8);
            richTextBox1.Text = str1 + sb.ToString();
        }));
    }

    private void button1_Click(object sender, EventArgs e)
    {
        Task.Run(() => {
            GetResult();
        });
    }
}

public partial class Form1 : Form

{

void GetResult()

{

int min = 1;

int max = 9;

// 順列を取得する

List<List<int>> lists = GetPermutation(min, max);

int count = max - min + 1;

int lineCount = (int)Math.Sqrt(count);

int allSum = max * (max + 1) / 2;

int lineSum = allSum / lineCount;

// 取得した順列のうち魔方陣になっているものを取得する

List<List<int>> ret = new List<List<int>>();

foreach(var list2 in lists)

{

if(IsMahojin(list2, lineSum))

ret.Add(list2);

}

StringBuilder sb = new StringBuilder();

foreach(List<int> list in ret)

sb.Append(String.Join(", ", list.Select(x => x.ToString()).ToArray()) + "\n");

Invoke((Action)(() => {

// 回転させたり裏返すと一致するものは同じとしてカウントする

string str1 = String.Format("{0:#,0}種類\n\n", ret.Count / 8);

richTextBox1.Text = str1 + sb.ToString();

}));

}

private void button1_Click(object sender, EventArgs e)

{

Task.Run(() => {

GetResult();

});

}

この方法は時間がかかります。横列がそろうときに入れることができる数字は決まっているので、それ以外の順列は考えないことにします。これだとすぐに結果が表示されます。

public partial class Form1 : Form
{
    void GetResult()
    {
        int min = 1;
        int max = 9;

        // 順列を取得する
        List<List<int>> lists = GetPermutation2(min, max);

        StringBuilder sb = new StringBuilder();
        foreach(List<int> list in lists)
        {
            sb.Append(String.Join(", ", list.Select(x => x.ToString()).ToArray()) + "\n");
        }
        Invoke((Action)(() => {
            string[] vs = listCounts.Select(x => x.ToString("#,0")).ToArray();
            string str1 = String.Format("{0:#,0}種類\n\n", lists.Count / 8);
            richTextBox1.Text = str1 + sb.ToString();
        }));
    }

    List<List<int>> GetPermutation2(int min, int max)
    {
        List<int> vs1 = new List<int>();
        for(int i = min; i <= max; i++)
            vs1.Add(i);

        int allSum = vs1.Sum();
        int count = max - min + 1;
        int lineCount = (int)Math.Sqrt(count);
        int lineSum = allSum / lineCount;

        List<List<int>> list = null;
        list = new List<List<int>>();

        for(int i = min; i <= max; i++)
        {
            List<int> vs2 = new List<int>();
            vs2.Add(i);
            list.Add(vs2);
        }

        while(true)
        {
            List<List<int>> templist = null;
            templist = new List<List<int>>();

            foreach(var list1 in list)
            {
                var vs3 = vs1.Except(list1).ToList();
                if(vs3.Count == 0)
                {
                    // 取得した順列のうち魔方陣になっているもののみを返す
                    List<List<int>> ret = new List<List<int>>();
                    foreach(var list2 in list)
                    {
                        if(IsMahojin(list2, lineSum))
                            ret.Add(list2);
                    }
                    return ret;
                }

                // 横列完成まであと1個のときは追加される数値はひとつに決まっている
                if(list1.Count % lineCount == lineCount-1)
                {
                    int curSum = list1.Sum() - lineSum * (list1.Count / lineCount);
                    int needNum = lineSum - curSum;
                    if(vs3.Any(x => x == needNum))
                    {
                        List<int> list3 = new List<int>(list1);
                        list3.Add(needNum);
                        templist.Add(list3);
                    }
                }
                else
                {
                    foreach(int i in vs3)
                    {
                        List<int> list3 = new List<int>(list1);
                        list3.Add(i);
                        templist.Add(list3);
                    }
                }
            }
            list = templist;
        }
    }
}

public partial class Form1 : Form

{

void GetResult()

{

int min = 1;

int max = 9;

// 順列を取得する

List<List<int>> lists = GetPermutation2(min, max);

StringBuilder sb = new StringBuilder();

foreach(List<int> list in lists)

{

sb.Append(String.Join(", ", list.Select(x => x.ToString()).ToArray()) + "\n");

}

Invoke((Action)(() => {

string[] vs = listCounts.Select(x => x.ToString("#,0")).ToArray();

string str1 = String.Format("{0:#,0}種類\n\n", lists.Count / 8);

richTextBox1.Text = str1 + sb.ToString();

}));

}

List<List<int>> GetPermutation2(int min, int max)

{

List<int> vs1 = new List<int>();

for(int i = min; i <= max; i++)

vs1.Add(i);

int allSum = vs1.Sum();

int count = max - min + 1;

int lineCount = (int)Math.Sqrt(count);

int lineSum = allSum / lineCount;

List<List<int>> list = null;

list = new List<List<int>>();

for(int i = min; i <= max; i++)

{

List<int> vs2 = new List<int>();

vs2.Add(i);

list.Add(vs2);

}

while(true)

{

List<List<int>> templist = null;

templist = new List<List<int>>();

foreach(var list1 in list)

{

var vs3 = vs1.Except(list1).ToList();

if(vs3.Count == 0)

{

// 取得した順列のうち魔方陣になっているもののみを返す

List<List<int>> ret = new List<List<int>>();

foreach(var list2 in list)

{

if(IsMahojin(list2, lineSum))

ret.Add(list2);

}

return ret;

}

// 横列完成まであと1個のときは追加される数値はひとつに決まっている

if(list1.Count % lineCount == lineCount-1)

{

int curSum = list1.Sum() - lineSum * (list1.Count / lineCount);

int needNum = lineSum - curSum;

if(vs3.Any(x => x == needNum))

{

List<int> list3 = new List<int>(list1);

list3.Add(needNum);

templist.Add(list3);

}

else

{

foreach(int i in vs3)

{

List<int> list3 = new List<int>(list1);

list3.Add(i);

templist.Add(list3);

}

list = templist;

}

これで4×4の魔方陣もできるのかと思ったらそうはいかないようです。場合の数が多すぎて途中で処理が止まってしまいます。

数字を入れたときに縦列が残り1つになっている場合、そこに入れることができる数字が存在しない場合は除外して考えると計算量が少なくなります。

public partial class Form1 : Form
{
    /// <summary>
    /// 最後の要素からみて縦列の空いているマスの数を返す
    /// </summary>
    int GetRowSpaceCount(List<int> ints, int lineCount)
    {
        if(ints.Count % lineCount == 0)
            return lineCount - ints.Count / lineCount;
        else
            return lineCount - ints.Count / lineCount - 1;
    }

    /// <summary>
    /// 最後の要素からみて縦列の合計を返す
    /// </summary>
    int GetRowSum(List<int> ints, int lineCount)
    {
        int count = ints.Count();

        int ret = 0;
        for(int i = count; i > 0; i -= lineCount)
        {
            ret += ints[i - 1];
        }
        return ret;
    }

    // フィールド変数
    List<int> listCounts = new List<int>();

    List<List<int>> GetPermutation3(int min, int max)
    {
        List<int> vs1 = new List<int>();
        for(int i = min; i <= max; i++)
            vs1.Add(i);

        int allSum = vs1.Sum();
        int count = max - min + 1;
        int lineCount = (int)Math.Sqrt(count);
        int lineSum = allSum / lineCount;

        List<List<int>> list = null;
        list = new List<List<int>>();

        Invoke((Action)(() => {
            progressBar1.Value = 0;
            progressBar1.Maximum = max - min;
        }));

        for(int i = min; i <= max; i++)
        {
            List<int> vs2 = new List<int>();
            vs2.Add(i);
            list.Add(vs2);
        }

        while(true)
        {
            // list.Countの最大値を保存しておく
            listCounts.Add(list.Count);

            List<List<int>> templist = new List<List<int>>();
            foreach(var list1 in list)
            {
                var vs3 = vs1.Except(list1).ToList();

                // 処理が終わったら魔方陣になっている順列のみを返す
                if(vs3.Count == 0)
                {
                    Invoke((Action)(() => {
                        progressBar1.Value = 0;
                    }));

                    List<List<int>> ret = new List<List<int>>();
                    foreach(var list2 in list)
                    {
                        if(IsMahojin(list2, lineSum))
                            ret.Add(list2);
                    }
                    return ret;
                }

                // 横列完成まであと1個のときは追加される数値はひとつに決まっている
                if(list1.Count % lineCount == lineCount - 1)
                {
                    AddLastToColum(list1, vs3, templist, lineCount, lineSum);
                }
                else
                {
                    foreach(int i in vs3)
                    {
                        List<int> list3 = new List<int>(list1);
                        list3.Add(i);

                        // 縦列が埋まったら合計がlineCountになっている場合だけ templistに加える
                        if(GetRowSpaceCount(list3, lineCount) == 0)
                        {
                            if(GetRowSum(list3, lineCount) == lineSum)
                                templist.Add(list3);
                        }
                        // 縦列が残り1マスになったら
                        // 合計をlineCountにすることができる要素が残っている場合だけ templistに加える
                        else if(GetRowSpaceCount(list3, lineCount) == 1)
                        {
                            int needNum1 = lineSum - GetRowSum(list3, lineCount);
                            if(needNum1 == i)
                                continue;
                            if(vs3.Any(x => x == needNum1))
                                templist.Add(list3);
                        }
                        // それ以外は普通に templistへ追加する
                        else
                        {
                            templist.Add(list3);
                        }
                    }
                }
            }
            list = templist;

            Invoke((Action)(() => {
                progressBar1.Value++;
            }));
        }
    }

    /// <summary>
    /// 横列の最後の数字を入れる
    /// </summary>
    void AddLastToColum(List<int> list, List<int> vs, List<List<int>> templist, int lineCount, int lineSum)
    {
        int curSum = list.Sum() - lineSum * (list.Count / lineCount);
        int needNum = lineSum - curSum;
        if(vs.Any(x => x == needNum))
        {
            List<int> list1 = new List<int>(list);
            list1.Add(needNum);

            if(GetRowSpaceCount(list1, lineCount) == 0)
            {
                if(GetRowSum(list1, lineCount) == lineSum)
                    templist.Add(list1);
            }
            else if(GetRowSpaceCount(list1, lineCount) == 1)
            {
                int needNum1 = lineSum - GetRowSum(list1, lineCount);
                if(needNum1 == needNum)
                    return;
                if(vs.Any(x => x == needNum1))
                    templist.Add(list1);
            }
            else
                templist.Add(list1);
        }
    }

    void GetResult()
    {
        int min = 1;
        int max = 16;

        // 順列を取得する
        List<List<int>> lists = GetPermutation3(min, max);

        StringBuilder sb = new StringBuilder();
        foreach(List<int> list in lists)
        {
            sb.Append(String.Join(", ", list.Select(x => x.ToString()).ToArray()) + "\n");
        }
        Invoke((Action)(() => {
            string[] vs = listCounts.Select(x => x.ToString("#,0")).ToArray();
            string str1 = String.Format("{0:#,0}種類\n\n", lists.Count / 8);
            string str2 = String.Join("\n", vs) + "\n";
            richTextBox1.Text = str1 + str2 + "\n\n" + sb.ToString();
        }));
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

public partial class Form1 : Form

{

/// <summary>

/// 最後の要素からみて縦列の空いているマスの数を返す

/// </summary>

int GetRowSpaceCount(List<int> ints, int lineCount)

{

if(ints.Count % lineCount == 0)

return lineCount - ints.Count / lineCount;

else

return lineCount - ints.Count / lineCount - 1;

}

/// <summary>

/// 最後の要素からみて縦列の合計を返す

/// </summary>

int GetRowSum(List<int> ints, int lineCount)

{

int count = ints.Count();

int ret = 0;

for(int i = count; i > 0; i -= lineCount)

{

ret += ints[i - 1];

}

return ret;

}

// フィールド変数

List<int> listCounts = new List<int>();

List<List<int>> GetPermutation3(int min, int max)

{

List<int> vs1 = new List<int>();

for(int i = min; i <= max; i++)

vs1.Add(i);

int allSum = vs1.Sum();

int count = max - min + 1;

int lineCount = (int)Math.Sqrt(count);

int lineSum = allSum / lineCount;

List<List<int>> list = null;

list = new List<List<int>>();

Invoke((Action)(() => {

progressBar1.Value = 0;

progressBar1.Maximum = max - min;

}));

for(int i = min; i <= max; i++)

{

List<int> vs2 = new List<int>();

vs2.Add(i);

list.Add(vs2);

}

while(true)

{

// list.Countの最大値を保存しておく

listCounts.Add(list.Count);

List<List<int>> templist = new List<List<int>>();

foreach(var list1 in list)

{

var vs3 = vs1.Except(list1).ToList();

// 処理が終わったら魔方陣になっている順列のみを返す

if(vs3.Count == 0)

{

Invoke((Action)(() => {

progressBar1.Value = 0;

}));

List<List<int>> ret = new List<List<int>>();

foreach(var list2 in list)

{

if(IsMahojin(list2, lineSum))

ret.Add(list2);

}

return ret;

}

// 横列完成まであと1個のときは追加される数値はひとつに決まっている

if(list1.Count % lineCount == lineCount - 1)

{

AddLastToColum(list1, vs3, templist, lineCount, lineSum);

}

else

{

foreach(int i in vs3)

{

List<int> list3 = new List<int>(list1);

list3.Add(i);

// 縦列が埋まったら合計がlineCountになっている場合だけ templistに加える

if(GetRowSpaceCount(list3, lineCount) == 0)

{

if(GetRowSum(list3, lineCount) == lineSum)

templist.Add(list3);

}

// 縦列が残り1マスになったら

// 合計をlineCountにすることができる要素が残っている場合だけ templistに加える

else if(GetRowSpaceCount(list3, lineCount) == 1)

{

int needNum1 = lineSum - GetRowSum(list3, lineCount);

if(needNum1 == i)

continue;

if(vs3.Any(x => x == needNum1))

templist.Add(list3);

}

// それ以外は普通に templistへ追加する

else

{

templist.Add(list3);

}

list = templist;

Invoke((Action)(() => {

progressBar1.Value++;

}));

}

/// <summary>

/// 横列の最後の数字を入れる

/// </summary>

void AddLastToColum(List<int> list, List<int> vs, List<List<int>> templist, int lineCount, int lineSum)

{

int curSum = list.Sum() - lineSum * (list.Count / lineCount);

int needNum = lineSum - curSum;

if(vs.Any(x => x == needNum))

{

List<int> list1 = new List<int>(list);

list1.Add(needNum);

if(GetRowSpaceCount(list1, lineCount) == 0)

{

if(GetRowSum(list1, lineCount) == lineSum)

templist.Add(list1);

}

else if(GetRowSpaceCount(list1, lineCount) == 1)

{

int needNum1 = lineSum - GetRowSum(list1, lineCount);

if(needNum1 == needNum)

return;

if(vs.Any(x => x == needNum1))

templist.Add(list1);

}

else

templist.Add(list1);

}

void GetResult()

{

int min = 1;

int max = 16;

// 順列を取得する

List<List<int>> lists = GetPermutation3(min, max);

StringBuilder sb = new StringBuilder();

foreach(List<int> list in lists)

{

sb.Append(String.Join(", ", list.Select(x => x.ToString()).ToArray()) + "\n");

}

Invoke((Action)(() => {

string[] vs = listCounts.Select(x => x.ToString("#,0")).ToArray();

string str1 = String.Format("{0:#,0}種類\n\n", lists.Count / 8);

string str2 = String.Join("\n", vs) + "\n";

richTextBox1.Text = str1 + str2 + "\n\n" + sb.ToString();

}));

}

作業用リストの要素がそれくらいになるか記憶しておくようにしました。

実行しようとすると2～3分かかります。出力結果はこうなりました。

880種類

16
240
3,360
2,064
24,768
272,448
2,724,480
1,238,400
2,793,888
5,180,480
7,563,568
958,880
756,640
657,464
549,504
549,504

1, 2, 15, 16, 12, 14, 3, 5, 13, 7, 10, 4, 8, 11, 6, 9
1, 2, 15, 16, 13, 14, 3, 4, 12, 7, 10, 5, 8, 11, 6, 9
// 以下省略

以下の動画によると5×5だと275,305,224通り、6×6に至っては不明です。スーパーコンピューターを使った予想では1800京通り（1京は1億の1億倍）とのこと。絶対にムリ（汗）

また奇数であれば簡単につくる方法があります。

魔方陣の解法、ヒンズーの連続方式 – 浄土真宗の学び場、法雷窟

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ