8-5 連環の数 初級編

問題

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

円が２つの場合は1から3の数が図のように入ります。


円が3つの場合は、1から5の数が、例えば図のように入ります。


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

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int CircleCnt = 4;
    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 (CircleCnt >= 2) {
            if (IsValidHelper(pJyoutai.IntArr, 0, 1, 2) == false) return false;
        }
        if (CircleCnt >= 3) {
            if (IsValidHelper(pJyoutai.IntArr, 2, 3, 4) == false) return false;
        }
        if (CircleCnt >= 4) {
            if (IsValidHelper(pJyoutai.IntArr, 4, 5, 6) == 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 = 6,7,1,4,3,5,2,
Answer2 = 3,4,1,6,5,7,2,
Answer3 = 2,7,5,6,1,4,3,
Answer4 = 2,5,3,4,1,7,6,

解説

Array.IndexOfジェネリックメソッドを使ってます。
MSDN --- Array.IndexOf(T) メソッド