Cマガ電脳クラブ(第065回) 24手

問題

Fig.1の左側のように10個のマスの中に左詰めで四つの駒が入っている。
一度にひとつの駒を1マスだけ右に動かす事にすると、Fig.1の右側のように右詰めにするには24手かかる。
では24手の動かし方、これは全部で何通りあるだろうか？

次のマスが埋まっている場合はその駒は動かせない (ひとつのマスにふたつの駒は入れられない) ものとする。
つまり、1手目は必ずAを動かして、2手目はAかBを動かすことになる。

Fig.1 24手

ソース

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

class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        Console.WriteLine("正方向探索を行います。");
        Dictionary<uint, int> SeiHoukouLeafDict = ExecDFS(true);
        Console.WriteLine("正方向探索の葉ノード数={0}", SeiHoukouLeafDict.Count);

        Console.WriteLine("逆方向探索を行います。");
        Dictionary<uint, int> RevHoukouLeafDict = ExecDFS(false);
        Console.WriteLine("逆方向探索の葉ノード数={0}", RevHoukouLeafDict.Count);

        int ProdSum = 0;
        foreach (var AnyPair in SeiHoukouLeafDict) {
            ProdSum += AnyPair.Value * RevHoukouLeafDict[AnyPair.Key];
        }
        Console.WriteLine("解は{0}通り。経過時間={1}", ProdSum, sw.Elapsed);
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal char[] BanArr;
    }

    //深さ優先探索を行い(双方向探索なので方向を引数で指定する)
    //葉ノードの状態ごとの件数を返す
    static Dictionary<uint, int> ExecDFS(bool IsSeiHoukou)
    {
        var WillReturnDict = new Dictionary<uint, int>();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;

        char[] wkArr = { 'D', 'C', 'B', 'A' };
        if (IsSeiHoukou) { //正方向の探索
            WillPush.BanArr = wkArr.Concat(Enumerable.Repeat(' ', 6)).ToArray();
        }
        else { //逆方向の探索
            WillPush.BanArr = Enumerable.Repeat(' ', 6).Concat(wkArr).ToArray();
        }
        stk.Push(WillPush);

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

            if (Popped.Level == 12) {
                uint BanUInt = BanToUInt(Popped.BanArr);
                if (WillReturnDict.ContainsKey(BanUInt))
                    WillReturnDict[BanUInt]++;
                else WillReturnDict[BanUInt] = 1;

                continue;
            }

            WillPush.Level = Popped.Level + 1;
            if (IsSeiHoukou) { //正方向の探索
                for (int I = 1; I <= Popped.BanArr.GetUpperBound(0); I++) {
                    if (Popped.BanArr[I] == ' ' && Popped.BanArr[I - 1] != ' ') {
                        WillPush.BanArr = (char[])Popped.BanArr.Clone();
                        WillPush.BanArr[I] = Popped.BanArr[I - 1];
                        WillPush.BanArr[I - 1] = ' ';
                        stk.Push(WillPush);
                    }
                }
            }
            else { //逆方向の探索
                for (int I = 0; I <= Popped.BanArr.GetUpperBound(0) - 1; I++) {
                    if (Popped.BanArr[I] == ' ' && Popped.BanArr[I + 1] != ' ') {
                        WillPush.BanArr = (char[])Popped.BanArr.Clone();
                        WillPush.BanArr[I] = Popped.BanArr[I + 1];
                        WillPush.BanArr[I + 1] = ' ';
                        stk.Push(WillPush);
                    }
                }
            }
        }
        return WillReturnDict;
    }

    //盤面を符号なしInt型で表現
    static uint BanToUInt(char[] pBanArr)
    {
        var sb = new System.Text.StringBuilder();

        for (int I = 0; I <= pBanArr.GetUpperBound(0); I++) {
            if (pBanArr[I] == ' ') sb.Append(0);
            if (pBanArr[I] == 'A') sb.Append(1);
            if (pBanArr[I] == 'B') sb.Append(2);
            if (pBanArr[I] == 'C') sb.Append(3);
            if (pBanArr[I] == 'D') sb.Append(4);
        }
        return Convert.ToUInt32(sb.ToString(), 8);
    }
}

実行結果

正方向探索を行います。
正方向探索の葉ノード数=18
逆方向探索を行います。
逆方向探索の葉ノード数=18
解は140229804通り。経過時間=00:00:00.7464526

解説

開始と終了の状態が分かっているので双方向探索が使えますので、
双方向探索で、正方向で12手、逆方向で12手の探索を行ってから、
合流した葉ノードまでの組み合わせの数同士に対して、積の法則を使ってます。