Q22 絡まない糸電話

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    //const int N = 6;
    const int N = 16;

    struct JyoutaiDef
    {
        internal int PairCnt;
        internal List<int[]> RyouikiNumArrList;
        internal String Log;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.PairCnt = 0;
        WillPush.RyouikiNumArrList = new List<int[]>();
        WillPush.RyouikiNumArrList.Add(Enumerable.Range(1, N).ToArray());
        WillPush.Log = "";
        stk.Push(WillPush);

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

            //クリア判定
            if (Popped.PairCnt == N / 2) {
                AnswerCnt++;
                Console.WriteLine("解{0}を発見。{1}", AnswerCnt, Popped.Log);
                continue;
            }

            int[] CurrRyouikiNumArr = Popped.RyouikiNumArrList[0];
            int UB = CurrRyouikiNumArr.GetUpperBound(0);
            //0番目とペアを作る
            for (int I = 1; I <= UB; I++) {
                //奇数人になる分割は不可
                if ((I + 1) % 2 == 1) continue;

                WillPush.PairCnt = Popped.PairCnt + 1;
                WillPush.RyouikiNumArrList = new List<int[]>(Popped.RyouikiNumArrList);
                WillPush.RyouikiNumArrList.RemoveAt(0);
                WillPush.Log = Popped.Log + string.Format("{0}と{1}。",
                    CurrRyouikiNumArr[0], CurrRyouikiNumArr[I]);

                //隣接した人でペアを作った場合
                if (I == 1 || I == UB) {
                    var wkRyouikiNumArr = new List<int>();
                    for (int J = 1; J <= UB; J++) {
                        if (J != I)
                            wkRyouikiNumArr.Add(CurrRyouikiNumArr[J]);
                    }
                    if (wkRyouikiNumArr.Count >= 2)
                        WillPush.RyouikiNumArrList.Add(wkRyouikiNumArr.ToArray());
                }
                //隣接してない人でペアを作った場合
                else {
                    var wkRyouikiNumArr = new List<int>();
                    for (int J = 1; J <= I - 1; J++) {
                        wkRyouikiNumArr.Add(CurrRyouikiNumArr[J]);
                    }
                    WillPush.RyouikiNumArrList.Add(wkRyouikiNumArr.ToArray());
                    wkRyouikiNumArr.Clear();
                    for (int J = I + 1; J <= UB; J++) {
                        wkRyouikiNumArr.Add(CurrRyouikiNumArr[J]);
                    }
                    WillPush.RyouikiNumArrList.Add(wkRyouikiNumArr.ToArray());
                }
                stk.Push(WillPush);
            }
        }
    }
}

実行結果

省略
解1426を発見。1と2。3と4。5と6。7と8。9と10。11と16。12と15。13と14。
解1427を発見。1と2。3と4。5と6。7と8。9と10。11と16。12と13。14と15。
解1428を発見。1と2。3と4。5と6。7と8。9と10。11と14。12と13。15と16。
解1429を発見。1と2。3と4。5と6。7と8。9と10。11と12。13と16。14と15。
解1430を発見。1と2。3と4。5と6。7と8。9と10。11と12。13と14。15と16。

解説

深さ優先探索で、ペアを作りつつ、領域の分断をシュミレーションしてます。