8-4 ぶどうの房パズル上級編

問題

下の図での1〜15までの自然数の組み合わせを求めます。

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int husaCnt = 15;

    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 <= husaCnt; I++) {
            WillPush.IntArr = new int[husaCnt];
            WillPush.IntArr[0] = I;
            stk.Push(WillPush);
        }

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

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

            WillPush.Level = Popped.Level + 1;

            for (int I = 1; I <= husaCnt; 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)
    {
        int[] wkArrP = (int[])pJyoutai.IntArr;

        if (IsValidSub(wkArrP[5], wkArrP[0], wkArrP[1]) == false) return false;
        if (IsValidSub(wkArrP[6], wkArrP[1], wkArrP[2]) == false) return false;
        if (IsValidSub(wkArrP[7], wkArrP[2], wkArrP[3]) == false) return false;
        if (IsValidSub(wkArrP[8], wkArrP[3], wkArrP[4]) == false) return false;
        if (IsValidSub(wkArrP[9], wkArrP[5], wkArrP[6]) == false) return false;
        if (IsValidSub(wkArrP[10], wkArrP[6], wkArrP[7]) == false) return false;
        if (IsValidSub(wkArrP[11], wkArrP[7], wkArrP[8]) == false) return false;
        if (IsValidSub(wkArrP[12], wkArrP[9], wkArrP[10]) == false) return false;
        if (IsValidSub(wkArrP[13], wkArrP[10], wkArrP[11]) == false) return false;
        if (IsValidSub(wkArrP[14], wkArrP[12], wkArrP[13]) == false) return false;
        return true;
    }

    private static bool IsValidSub(int P1, int P2, int P3)
    {
        if (P1 != 0 && P2 != 0 && P3 != 0) {
            if (P1 != Math.Abs(P2 - P3)) return false;
        }
        return true;
    }
}

実行結果

Answer=13,3,15,14,6,10,12,1,8,2,11,7,9,4,5,
Answer=6,14,15,3,13,8,1,12,10,7,11,2,4,9,5,

解説

差のチェック用のヘルパメソッドを作ってます。