Q43 シャッフルで逆順

C#のソース

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

class Program
{
    static int UB;

    static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();

    static void Main()
    {
        Solve(2);
        Solve(5);
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal int[] BanArr;
        internal List<int[]> Log;
    }

    static void Solve(int pN)
    {
        UB = pN * 2 - 1;
        for (int I = 1; I < int.MaxValue; I++) {
            if (ExecDFS(pN, I)) break;
        }
    }

    static bool ExecDFS(int pN, int pLevelLimit)
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.BanArr = Enumerable.Range(1, pN * 2).ToArray();
        WillPush.Log = new List<int[]>() { WillPush.BanArr };
        stk.Push(WillPush);

        var MinTesuuDict = new Dictionary<ulong, int>();
        MinTesuuDict.Add(BanToULong(WillPush.BanArr), 0);

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

            //クリア判定
            IEnumerable<int> AnswerEnum = Enumerable.Range(1, pN * 2).Reverse();
            if (Popped.BanArr.Cast<int>().SequenceEqual(AnswerEnum)) {
                Console.WriteLine("N={0}での解を発見。経過時間={1}", pN, sw.Elapsed);
                for (int I = 0; I <= Popped.Log.Count - 1; I++) {
                    Console.Write("{0}回目 ", I);
                    Array.ForEach(Popped.Log[I], X => Console.Write("{0},", X));
                    Console.WriteLine();
                }
                return true;
            }

            //下限値枝切り
            int NeedMinTesuu = DeriveNeedMinTesuu(pN, Popped.BanArr);
            if (pLevelLimit < Popped.Level + NeedMinTesuu) continue;

            for (int LoopFromInd = 0; LoopFromInd <= UB; LoopFromInd++) {
                int ToInd = LoopFromInd + pN - 1;
                if (UB < ToInd) break;

                int[] CopiedArr = new int[pN];
                Array.Copy(Popped.BanArr, LoopFromInd, CopiedArr, 0, pN);

                var wkList = Popped.BanArr.ToList();
                wkList.RemoveRange(LoopFromInd, pN);
                wkList.InsertRange(0, CopiedArr);
                WillPush.BanArr = wkList.ToArray();

                WillPush.Level = Popped.Level + 1;
                int MinTesuu;
                ulong BanULong = BanToULong(WillPush.BanArr);
                if (MinTesuuDict.TryGetValue(BanULong, out MinTesuu)) {
                    if (MinTesuu <= WillPush.Level) continue;
                }
                MinTesuuDict[BanULong] = WillPush.Level;

                WillPush.Log = new List<int[]>(Popped.Log) { WillPush.BanArr };
                stk.Push(WillPush);
            }
        }
        return false;
    }

    //必要な最低手数を求める
    static int DeriveNeedMinTesuu(int pN, int[] pBanArr)
    {
        if (pBanArr[UB] == 1) return 1;
        if (pBanArr[UB - pN] == 1) return 1;
        return 2;
    }

    //盤面をULong型で表現
    static ulong BanToULong(int[] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int I = 0; I <= UB; I++) {
            sb.Append(pBanArr[I]);
        }
        return ulong.Parse(sb.ToString());
    }
}

実行結果

N=2での解を発見。経過時間=00:00:00.0449537
0回目 1,2,3,4,
1回目 2,3,1,4,
2回目 3,1,2,4,
3回目 2,4,3,1,
4回目 4,3,2,1,
N=5での解を発見。経過時間=00:05:55.8889062
0回目 1,2,3,4,5,6,7,8,9,10,
1回目 5,6,7,8,9,1,2,3,4,10,
2回目 7,8,9,1,2,5,6,3,4,10,
3回目 9,1,2,5,6,7,8,3,4,10,
4回目 1,2,5,6,7,9,8,3,4,10,
5回目 5,6,7,9,8,1,2,3,4,10,
6回目 7,9,8,1,2,5,6,3,4,10,
7回目 9,8,1,2,5,7,6,3,4,10,
8回目 7,6,3,4,10,9,8,1,2,5,
9回目 4,10,9,8,1,7,6,3,2,5,
10回目 7,6,3,2,5,4,10,9,8,1,
11回目 5,4,10,9,8,7,6,3,2,1,
12回目 10,9,8,7,6,5,4,3,2,1,

解説

反復深化深さ優先探索で解いてます。