トップページに戻る    次の増井さんの書籍の問題へ    前の増井さんの書籍の問題へ

Q65 面倒なキャッチボール

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB = 12;

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

        //反復深化深さ優先探索で解く
        for (int I = 5; I < int.MaxValue; I++) {
            Console.WriteLine("レベル制限={0}で深さ優先探索中。経過時間={1}", I, sw.Elapsed);
            if (ExecDFS(I)) break;
        }
    }

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

    //深さ優先探索を行う
    static bool ExecDFS(int pLimitLevel)
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanArr = new int[UB + 1];
        for (int I = 1; I <= 11; I++) {
            WillPush.BanArr[I] = I;
        }
        WillPush.Level = 0;
        WillPush.Log = new List<string>();
        WillPush.Log.Add(BanToStr(WillPush.BanArr));
        stk.Push(WillPush);

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

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

            //クリア判定
            if (IsClear(Popped.BanArr)) {
                Console.WriteLine("解を発見");
                for (int I = 0; I <= Popped.Log.Count - 1; I++) {
                    Console.WriteLine("■■■■■{0}手目■■■■■", I);
                    Console.WriteLine(Popped.Log[I]);
                }
                return true;
            }

            //下限値枝切り
            if (Popped.Level + DeriveNeedMinTesuu(Popped.BanArr) > pLimitLevel)
                continue;

            //ボールを持ってない添字
            int SpaceInd = Array.FindIndex(Popped.BanArr, 1, X => X == 0);
            int[] FromIndArr = DeriveFromIndArr(SpaceInd);
            foreach (int EachInt in FromIndArr) {
                WillPush.BanArr = (int[])Popped.BanArr.Clone();
                WillPush.BanArr[EachInt] = 0;
                WillPush.BanArr[SpaceInd] = Popped.BanArr[EachInt];
                WillPush.Level = Popped.Level + 1;

                //メモ化探索
                ulong wkHash = GetHash(WillPush.BanArr);
                int MinTesuu;
                if (MinTesuuDict.TryGetValue(wkHash, out MinTesuu)) {
                    if (MinTesuu <= WillPush.Level) continue;
                }
                MinTesuuDict[wkHash] = WillPush.Level;

                WillPush.Log = new List<string>(Popped.Log);
                WillPush.Log.Add(BanToStr(WillPush.BanArr));

                stk.Push(WillPush);
            }
        }
        return false;
    }

    //クリア判定
    static bool IsClear(int[] pBanArr)
    {
        if (pBanArr[1] != 0) return false;
        for (int I = 2; I <= 11; I++)
            if (pBanArr[I] != I) return false;
        if (pBanArr[12] != 1) return false;

        return true;
    }

    //最小の残り手数を返す(下限値枝切り用)
    static int DeriveNeedMinTesuu(int[] pBanArr)
    {
        int WillReturn = 0;
        int wkInd = 0;
        Action<int, int> wkAct = (pInd, pTesuu) =>
        {
            if (wkInd == pInd) WillReturn += pTesuu;
        };

        //1のボールを12まで移動させる手数
        wkInd = Array.FindIndex(pBanArr, 1, X => X == 1);
        wkAct(1, 5); wkAct(2, 5); wkAct(3, 3); wkAct(4, 3); wkAct(5, 1); wkAct(6, 1);
        wkAct(7, 6); wkAct(8, 4); wkAct(9, 4); wkAct(10, 2); wkAct(11, 2); wkAct(12, 0);

        //2のボールを2まで移動させる手数
        wkInd = Array.FindIndex(pBanArr, 1, X => X == 2);
        wkAct(1, 2); wkAct(2, 0); wkAct(3, 2); wkAct(4, 2); wkAct(5, 4); wkAct(6, 4);
        wkAct(7, 1); wkAct(8, 1); wkAct(9, 1); wkAct(10, 3); wkAct(11, 3); wkAct(12, 5);

        //3のボールを3まで移動させる手数
        wkInd = Array.FindIndex(pBanArr, 1, X => X == 3);
        wkAct(1, 2); wkAct(2, 2); wkAct(3, 0); wkAct(4, 2); wkAct(5, 2); wkAct(6, 4);
        wkAct(7, 3); wkAct(8, 1); wkAct(9, 1); wkAct(10, 1); wkAct(11, 3); wkAct(12, 3);

        //4のボールを4まで移動させる手数
        wkInd = Array.FindIndex(pBanArr, 1, X => X == 4);
        wkAct(1, 4); wkAct(2, 2); wkAct(3, 2); wkAct(4, 0); wkAct(5, 2); wkAct(6, 2);
        wkAct(7, 3); wkAct(8, 3); wkAct(9, 1); wkAct(10, 1); wkAct(11, 1); wkAct(12, 3);

        //5のボールを5まで移動させる手数
        wkInd = Array.FindIndex(pBanArr, 1, X => X == 5);
        wkAct(1, 4); wkAct(2, 4); wkAct(3, 2); wkAct(4, 2); wkAct(5, 0); wkAct(6, 2);
        wkAct(7, 5); wkAct(8, 3); wkAct(9, 3); wkAct(10, 1); wkAct(11, 1); wkAct(12, 1);

        //6のボールを6まで移動させる手数
        wkInd = Array.FindIndex(pBanArr, 1, X => X == 6);
        wkAct(1, 6); wkAct(2, 4); wkAct(3, 4); wkAct(4, 2); wkAct(5, 2); wkAct(6, 0);
        wkAct(7, 5); wkAct(8, 5); wkAct(9, 3); wkAct(10, 3); wkAct(11, 1); wkAct(12, 1);

        //7のボールを7まで移動させる手数
        wkInd = Array.FindIndex(pBanArr, 1, X => X == 7);
        wkAct(1, 1); wkAct(2, 1); wkAct(3, 3); wkAct(4, 3); wkAct(5, 5); wkAct(6, 5);
        wkAct(7, 0); wkAct(8, 2); wkAct(9, 2); wkAct(10, 4); wkAct(11, 4); wkAct(12, 6);

        //8のボールを8まで移動させる手数
        wkInd = Array.FindIndex(pBanArr, 1, X => X == 8);
        wkAct(1, 1); wkAct(2, 1); wkAct(3, 1); wkAct(4, 3); wkAct(5, 3); wkAct(6, 5);
        wkAct(7, 2); wkAct(8, 0); wkAct(9, 2); wkAct(10, 2); wkAct(11, 4); wkAct(12, 4);

        //9のボールを9まで移動させる手数
        wkInd = Array.FindIndex(pBanArr, 1, X => X == 9);
        wkAct(1, 3); wkAct(2, 1); wkAct(3, 1); wkAct(4, 1); wkAct(5, 3); wkAct(6, 3);
        wkAct(7, 2); wkAct(8, 2); wkAct(9, 0); wkAct(10, 2); wkAct(11, 2); wkAct(12, 4);

        //10のボールを10まで移動させる手数
        wkInd = Array.FindIndex(pBanArr, 1, X => X == 10);
        wkAct(1, 3); wkAct(2, 3); wkAct(3, 1); wkAct(4, 1); wkAct(5, 1); wkAct(6, 3);
        wkAct(7, 4); wkAct(8, 2); wkAct(9, 2); wkAct(10, 0); wkAct(11, 2); wkAct(12, 2);

        //11のボールを11まで移動させる手数
        wkInd = Array.FindIndex(pBanArr, 1, X => X == 11);
        wkAct(1, 5); wkAct(2, 3); wkAct(3, 3); wkAct(4, 1); wkAct(5, 1); wkAct(6, 1);
        wkAct(7, 4); wkAct(8, 4); wkAct(9, 2); wkAct(10, 2); wkAct(11, 0); wkAct(12, 2);

        return WillReturn;
    }

    //ボールを投げれる添字の配列を返す
    static int[] DeriveFromIndArr(int pSpaceInd)
    {
        if (pSpaceInd == 1) return new int[] { 7, 8 };
        if (pSpaceInd == 2) return new int[] { 7, 8, 9 };
        if (pSpaceInd == 3) return new int[] { 8, 9, 10 };
        if (pSpaceInd == 4) return new int[] { 9, 10, 11 };
        if (pSpaceInd == 5) return new int[] { 10, 11, 12 };
        if (pSpaceInd == 6) return new int[] { 11, 12 };
        if (pSpaceInd == 7) return new int[] { 1, 2 };
        if (pSpaceInd == 8) return new int[] { 1, 2, 3 };
        if (pSpaceInd == 9) return new int[] { 2, 3, 4 };
        if (pSpaceInd == 10) return new int[] { 3, 4, 5 };
        if (pSpaceInd == 11) return new int[] { 4, 5, 6 };
        if (pSpaceInd == 12) return new int[] { 5, 6 };
        return null;
    }

    //盤面をハッシュ値に変換
    static ulong GetHash(int[] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int I = 1; I <= UB; I++) {
            sb.Append(pBanArr[I]);
        }
        return Convert.ToUInt64(sb.ToString());
    }

    //盤面をString型で表現
    static string BanToStr(int[] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int I = 1; I <= UB; I++) {
            sb.AppendFormat("{0,2},", pBanArr[I]);
            if (I == 6) sb.AppendLine();
        }
        sb.AppendLine();
        return sb.ToString();
    }
}

実行結果

省略
レベル制限=35で深さ優先探索中。経過時間=00:00:03.5120958
レベル制限=36で深さ優先探索中。経過時間=00:00:05.1939481
レベル制限=37で深さ優先探索中。経過時間=00:00:06.8724265
解を発見
■■■■■0手目■■■■■
 1, 2, 3, 4, 5, 6,
 7, 8, 9,10,11, 0,

■■■■■1手目■■■■■
 1, 2, 3, 4, 5, 0,
 7, 8, 9,10,11, 6,

■■■■■2手目■■■■■
 1, 2, 3, 4, 5,11,
 7, 8, 9,10, 0, 6,

■■■■■3手目■■■■■
 1, 2, 3, 4, 0,11,
 7, 8, 9,10, 5, 6,

■■■■■4手目■■■■■
 1, 2, 3, 4,10,11,
 7, 8, 9, 0, 5, 6,

■■■■■5手目■■■■■
 1, 2, 3, 0,10,11,
 7, 8, 9, 4, 5, 6,

■■■■■6手目■■■■■
 1, 2, 3, 9,10,11,
 7, 8, 0, 4, 5, 6,

■■■■■7手目■■■■■
 1, 2, 0, 9,10,11,
 7, 8, 3, 4, 5, 6,

■■■■■8手目■■■■■
 1, 2, 8, 9,10,11,
 7, 0, 3, 4, 5, 6,

■■■■■9手目■■■■■
 0, 2, 8, 9,10,11,
 7, 1, 3, 4, 5, 6,

■■■■■10手目■■■■■
 7, 2, 8, 9,10,11,
 0, 1, 3, 4, 5, 6,

■■■■■11手目■■■■■
 7, 0, 8, 9,10,11,
 2, 1, 3, 4, 5, 6,

■■■■■12手目■■■■■
 7, 3, 8, 9,10,11,
 2, 1, 0, 4, 5, 6,

■■■■■13手目■■■■■
 7, 3, 0, 9,10,11,
 2, 1, 8, 4, 5, 6,

■■■■■14手目■■■■■
 7, 3, 1, 9,10,11,
 2, 0, 8, 4, 5, 6,

■■■■■15手目■■■■■
 7, 0, 1, 9,10,11,
 2, 3, 8, 4, 5, 6,

■■■■■16手目■■■■■
 7, 8, 1, 9,10,11,
 2, 3, 0, 4, 5, 6,

■■■■■17手目■■■■■
 7, 8, 1, 0,10,11,
 2, 3, 9, 4, 5, 6,

■■■■■18手目■■■■■
 7, 8, 1, 4,10,11,
 2, 3, 9, 0, 5, 6,

■■■■■19手目■■■■■
 7, 8, 0, 4,10,11,
 2, 3, 9, 1, 5, 6,

■■■■■20手目■■■■■
 7, 8, 9, 4,10,11,
 2, 3, 0, 1, 5, 6,

■■■■■21手目■■■■■
 7, 8, 9, 0,10,11,
 2, 3, 4, 1, 5, 6,

■■■■■22手目■■■■■
 7, 8, 9, 5,10,11,
 2, 3, 4, 1, 0, 6,

■■■■■23手目■■■■■
 7, 8, 9, 5, 0,11,
 2, 3, 4, 1,10, 6,

■■■■■24手目■■■■■
 7, 8, 9, 5, 1,11,
 2, 3, 4, 0,10, 6,

■■■■■25手目■■■■■
 7, 8, 9, 0, 1,11,
 2, 3, 4, 5,10, 6,

■■■■■26手目■■■■■
 7, 8, 9,10, 1,11,
 2, 3, 4, 5, 0, 6,

■■■■■27手目■■■■■
 7, 8, 9,10, 1, 0,
 2, 3, 4, 5,11, 6,

■■■■■28手目■■■■■
 7, 8, 9,10, 1, 6,
 2, 3, 4, 5,11, 0,

■■■■■29手目■■■■■
 7, 8, 9,10, 0, 6,
 2, 3, 4, 5,11, 1,

■■■■■30手目■■■■■
 7, 8, 9,10, 5, 6,
 2, 3, 4, 0,11, 1,

■■■■■31手目■■■■■
 7, 8, 9, 0, 5, 6,
 2, 3, 4,10,11, 1,

■■■■■32手目■■■■■
 7, 8, 9, 4, 5, 6,
 2, 3, 0,10,11, 1,

■■■■■33手目■■■■■
 7, 8, 0, 4, 5, 6,
 2, 3, 9,10,11, 1,

■■■■■34手目■■■■■
 7, 8, 3, 4, 5, 6,
 2, 0, 9,10,11, 1,

■■■■■35手目■■■■■
 7, 0, 3, 4, 5, 6,
 2, 8, 9,10,11, 1,

■■■■■36手目■■■■■
 7, 2, 3, 4, 5, 6,
 0, 8, 9,10,11, 1,

■■■■■37手目■■■■■
 0, 2, 3, 4, 5, 6,
 7, 8, 9,10,11, 1,

解説

反復深化深さ優先探索で解いてます。
下限値枝切りとメモ化もしてます。