8-6 連環の数 上級編

問題

連なった円の中に1から始まる、連続した自然数を入れていきます。
ただし、円の重なった部分には、その左右に入っている数の和を入れてください

円が8個の場合、1から15までの数を入れてみてください。

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int CircleCnt = 8;
    const int MaxVal = CircleCnt * 2 - 1;

    struct JyoutaiDef
    {
        internal int Level;
        internal int[] IntArr;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();

        JyoutaiDef WillPush;
        WillPush.Level = 1;

        for (int I = 1; I <= MaxVal; I++) {
            WillPush.IntArr = new int[MaxVal];
            WillPush.IntArr[0] = I;
            stk.Push(WillPush);
        }

        int answerCnt = 0;
        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            if (Popped.Level == MaxVal) {
                string WillOut = "";
                foreach (int each in Popped.IntArr) {
                    WillOut += each.ToString() + ",";
                }
                Console.WriteLine("Answer{0} = {1}", ++answerCnt, WillOut);
                continue;
            }

            WillPush.Level = Popped.Level + 1;

            for (int I = 1; I <= MaxVal; I++) {
                if (Array.IndexOf<int>(Popped.IntArr, I) >= 0) continue;

                WillPush.IntArr = (int[])Popped.IntArr.Clone();
                WillPush.IntArr[WillPush.Level - 1] = I;

                if (IsValid(WillPush)) {
                    stk.Push(WillPush);
                }
            }
        }
    }

    static bool IsValid(JyoutaiDef pJyoutai)
    {
        if (IsValidHelper(pJyoutai.IntArr, 0, 1, 2) == false) return false;
        if (IsValidHelper(pJyoutai.IntArr, 2, 3, 4) == false) return false;
        if (IsValidHelper(pJyoutai.IntArr, 4, 5, 6) == false) return false;
        if (IsValidHelper(pJyoutai.IntArr, 6, 7, 8) == false) return false;
        if (IsValidHelper(pJyoutai.IntArr, 8, 9, 10) == false) return false;
        if (IsValidHelper(pJyoutai.IntArr, 10, 11, 12) == false) return false;
        if (IsValidHelper(pJyoutai.IntArr, 12, 13, 14) == false) return false;
        return true;
    }

    private static bool IsValidHelper(int[] pArr, int P1, int P2, int P3)
    {
        if (pArr[P1] != 0 && pArr[P2] != 0 && pArr[P3] != 0) {
            if (pArr[P2] != pArr[P1] + pArr[P3]) return false;
        }
        return true;
    }
}

実行結果

Answer1 = 14,15,1,12,11,13,2,7,5,8,3,9,6,10,4,
Answer2 = 14,15,1,12,11,13,2,6,4,9,5,8,3,10,7,
Answer3 = 14,15,1,11,10,13,3,8,5,12,7,9,2,6,4,
省略
Answer394 = 1,3,2,10,8,12,4,11,7,13,6,15,9,14,5,
Answer395 = 1,3,2,9,7,13,6,11,5,15,10,14,4,12,8,
Answer396 = 1,3,2,9,7,12,5,13,8,14,6,10,4,15,11,

解説

ヘルパメソッドが活躍してますね。