Q54 同じ数字で挟み撃ち

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    const int n = 11;
    const int UB = n * 2 - 1;

    struct JyoutaiDef
    {
        internal int CurrNum;
        internal int[] BanArr;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrNum = n;
        WillPush.BanArr = new int[UB + 1];
        stk.Push(WillPush);

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

            if (Array.TrueForAll(Popped.BanArr, X => X != 0)) {
                AnswerCnt++;
                //var sb = new System.Text.StringBuilder();
                //sb.AppendFormat("Answer{0}は、", AnswerCnt);
                //Array.ForEach(Popped.BanArr, X => sb.Append(X));
                //Console.WriteLine(sb.ToString());
                continue;
            }
            for (int I = 0; I <= UB; I++) {
                if (Popped.BanArr[I] != 0) continue;

                int SecondPos = I + Popped.CurrNum + 1;
                if (UB < SecondPos) break;
                if (Popped.BanArr[SecondPos] != 0) continue;

                WillPush.CurrNum = Popped.CurrNum - 1;
                WillPush.BanArr = (int[])Popped.BanArr.Clone();
                WillPush.BanArr[I] = WillPush.BanArr[SecondPos] = Popped.CurrNum;
                stk.Push(WillPush);
            }
        }
        Console.WriteLine("解は{0}通り", AnswerCnt);
    }
}

実行結果

解は35584通り

解説

計算量を減らすために、大きい数値から探索してます。

Cマガ電脳クラブ(第004回) カードの間には