Cマガ電脳クラブ(第127回) タンク・チェンジ

問題

Fig.1のような盤を用意し，A軍の戦車3台とB軍の戦車3台をそれぞれ1,2,3と16,17,18の円に配置する。
直線は道路を，円は広場を表す。

　１．A軍を先手として，3台の戦車のうちのどれかを1台動かす。これを交互に繰り返す

　２．戦車は道路に沿って広場から広場へと移動できる。1つの広場には1台しか入れない

　３．戦車は動き始めたら止まるまで直進しかできない。いくつ先の広場で止まるかは自由だが，
　    通り道にほかの戦車がいる場合はそれより先には進めない。いくつ進んでもこれが「1手」

　４．止まった広場が敵軍の戦車から道路を介してまっすぐに見える場合には，撃たれてしまう

　以上の条件で，両軍が撃ち合うことなく戦車をそっくり入れ替えたい
(A軍とB軍がそれぞれ16,17,18と1,2,3にある状態にしたい)。
最低何手で完成できるだろうか。その移動手順の一例も示すこと。

Fig.1 タンク・チェンジの盤面

　　１　　　６　　　11　　　16
　　　＼　／　＼　／　＼　／
　　　　４　　　９　　　14
　　　／　＼　／　＼　／　＼
　　２　　　７　　　12　　　17
　　　＼　／　＼　／　＼　／
　　　　５　　　10　　　15
　　　／　＼　／　＼　／　＼
　　３　　　８　　　13　　　18

ソース

using System;
using System.Collections.Generic;

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

        //ネットワーク情報の配列を作成
        DeriveNetWorkInfoArr();

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

    //ネットワーク情報
    struct NetWorkInfoDef
    {
        internal int FromPos;
        internal int[] MovePosArr;
    }
    static NetWorkInfoDef[] NetWorkInfoArr;

    //ネットワーク情報の配列を作成
    static void DeriveNetWorkInfoArr()
    {
        var NetWorkInfoList = new List<NetWorkInfoDef>();
        Action<int, int[]> AddAct = (pFromPos, pMovePosArr) =>
        {
            NetWorkInfoDef WillAdd;
            WillAdd.FromPos = pFromPos;
            WillAdd.MovePosArr = pMovePosArr;
            NetWorkInfoList.Add(WillAdd);
        };
        AddAct(1, new int[] { 4, 7, 10, 13 });
        AddAct(2, new int[] { 4, 6 });
        AddAct(2, new int[] { 5, 8 });
        AddAct(3, new int[] { 5, 7, 9, 11 });
        AddAct(4, new int[] { 1 });
        AddAct(4, new int[] { 2 });
        AddAct(4, new int[] { 6 });
        AddAct(4, new int[] { 7, 10, 13 });
        AddAct(5, new int[] { 2 });
        AddAct(5, new int[] { 3 });
        AddAct(5, new int[] { 7, 9, 11 });
        AddAct(5, new int[] { 8 });
        AddAct(6, new int[] { 4, 2 });
        AddAct(6, new int[] { 9, 12, 15, 18 });
        AddAct(7, new int[] { 4, 1 });
        AddAct(7, new int[] { 5, 3 });
        AddAct(7, new int[] { 9, 11 });
        AddAct(7, new int[] { 10, 13 });
        AddAct(8, new int[] { 5, 2 });
        AddAct(8, new int[] { 10, 12, 14, 16 });
        AddAct(9, new int[] { 6 });
        AddAct(9, new int[] { 7, 5, 3 });
        AddAct(9, new int[] { 11 });
        AddAct(9, new int[] { 12, 15, 18 });
        AddAct(10, new int[] { 7, 4, 1 });
        AddAct(10, new int[] { 8 });
        AddAct(10, new int[] { 12, 14, 16 });
        AddAct(10, new int[] { 13 });
        AddAct(11, new int[] { 9, 7, 5, 3 });
        AddAct(11, new int[] { 14, 17 });
        AddAct(12, new int[] { 9, 6 });
        AddAct(12, new int[] { 10, 8 });
        AddAct(12, new int[] { 14, 16 });
        AddAct(12, new int[] { 15, 18 });
        AddAct(13, new int[] { 10, 7, 4, 1 });
        AddAct(13, new int[] { 15, 17 });
        AddAct(14, new int[] { 11 });
        AddAct(14, new int[] { 12, 10, 8 });
        AddAct(14, new int[] { 16 });
        AddAct(14, new int[] { 17 });
        AddAct(15, new int[] { 12, 9, 6 });
        AddAct(15, new int[] { 13 });
        AddAct(15, new int[] { 17 });
        AddAct(15, new int[] { 18 });
        AddAct(16, new int[] { 14, 12, 10, 8 });
        AddAct(17, new int[] { 14, 11 });
        AddAct(17, new int[] { 15, 13 });
        AddAct(18, new int[] { 15, 12, 9, 6 });
        NetWorkInfoArr = NetWorkInfoList.ToArray();
    }

    struct JyoutaiDef
    {
        internal Dictionary<int, char> BanDict;
        internal int Level;
        internal List<string> Log;
    }

    //深さ制限を引数として、深さ優先探索
    static bool ExecDFS(int pLimitLevel)
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanDict = new Dictionary<int, char>();
        for (int I = 1; I <= 18; I++) {
            if (I <= 3)
                WillPush.BanDict.Add(I, 'A');
            else if (I >= 16)
                WillPush.BanDict.Add(I, 'B');
            else WillPush.BanDict.Add(I, '*');
        }
        WillPush.Level = 0;
        WillPush.Log = new List<string>();
        WillPush.Log.Add(BanToStr(WillPush.BanDict));
        stk.Push(WillPush);

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

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

            //クリア判定
            if (IsClear(Popped.BanDict)) {
                Console.WriteLine("{0}手の解を発見", pLimitLevel);
                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.BanDict) > pLimitLevel)
                continue;

            for (int I = 1; I <= 18; I++) {
                if (Popped.Level % 2 == 0 && Popped.BanDict[I] != 'A') continue;
                if (Popped.Level % 2 == 1 && Popped.BanDict[I] != 'B') continue;

                //開始座標を引数として、移動可能な座標のListを返す
                List<int> MovePosList = DeriveMovePosList(I, Popped.BanDict);

                foreach (int EachMovePos in MovePosList) {
                    WillPush.BanDict = new Dictionary<int, char>(Popped.BanDict);
                    WillPush.BanDict[EachMovePos] = Popped.BanDict[I];
                    WillPush.BanDict[I] = '*';

                    //敵軍を砲撃可能かを判定
                    if (CanHougeki(EachMovePos, WillPush.BanDict))
                        continue;

                    WillPush.Level = Popped.Level + 1;

                    //メモ化探索
                    int wkHash = GetHash(WillPush.BanDict);
                    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.BanDict));

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

    //クリア判定
    static bool IsClear(Dictionary<int, char> pBanDict)
    {
        if (pBanDict[1] != 'B') return false;
        if (pBanDict[2] != 'B') return false;
        if (pBanDict[3] != 'B') return false;
        if (pBanDict[16] != 'A') return false;
        if (pBanDict[17] != 'A') return false;
        if (pBanDict[18] != 'A') return false;
        return true;
    }

    //最小の残り手数を返す(下限値枝切り用)
    static int DeriveNeedMinTesuu(Dictionary<int, char> pBanDict)
    {
        int WillReturn = 0;

        for (int I = 1; I <= 5; I++) {
            if (pBanDict[I] == 'A') WillReturn += 2;
        }
        if (pBanDict[6] == 'A') WillReturn++;
        if (pBanDict[7] == 'A') WillReturn += 2;
        if (pBanDict[8] == 'A') WillReturn++;
        for (int I = 9; I <= 15; I++) {
            if (pBanDict[I] == 'A') WillReturn++;
        }

        for (int I = 4; I <= 10; I++) {
            if (pBanDict[I] == 'B') WillReturn++;
        }
        if (pBanDict[11] == 'B') WillReturn++;
        if (pBanDict[12] == 'B') WillReturn += 2;
        if (pBanDict[13] == 'B') WillReturn++;
        for (int I = 14; I <= 18; I++) {
            if (pBanDict[I] == 'B') WillReturn += 2;
        }
        return WillReturn;
    }

    //開始座標を引数として、移動可能な座標のListを返す
    static List<int> DeriveMovePosList(int pFromPos, Dictionary<int, char> pBanDict)
    {
        var WillReturn = new List<int>();

        foreach (NetWorkInfoDef EachNetWorkInfo in NetWorkInfoArr) {
            if (EachNetWorkInfo.FromPos != pFromPos) continue;

            int[] wkArr = EachNetWorkInfo.MovePosArr;
            foreach (int EachMovePos in wkArr) {
                if (pBanDict[EachMovePos] != '*') break;
                WillReturn.Add(EachMovePos);
            }
        }
        return WillReturn;
    }

    //敵軍を砲撃可能かを判定
    static bool CanHougeki(int pCurrPos, Dictionary<int, char> pBanDict)
    {
        char Enemy = (pBanDict[pCurrPos] == 'A' ? 'B' : 'A');

        foreach (NetWorkInfoDef EachNetWorkInfo in NetWorkInfoArr) {
            if (EachNetWorkInfo.FromPos != pCurrPos) continue;

            int[] wkArr = EachNetWorkInfo.MovePosArr;
            if (Array.Exists(wkArr, X => pBanDict[X] == Enemy))
                return true;
        }
        return false;
    }

    //盤面をハッシュ値に変換
    static int GetHash(Dictionary<int, char> pBanDict)
    {
        var NumList = new List<int>();

        for (int I = 1; I <= 18; I++) {
            if (pBanDict[I] == '*') NumList.Add(0);
            if (pBanDict[I] == 'A') NumList.Add(1);
            if (pBanDict[I] == 'B') NumList.Add(2);
        }
        //3の17乗=129140163なので3進数ならオーバーフローしない
        int WillReturn = 0;
        foreach (int EachInt in NumList) {
            WillReturn *= 3;
            WillReturn += EachInt;
        }
        return WillReturn;
    }

    //盤面をString型で表現
    static string BanToStr(Dictionary<int, char> pBanDict)
    {
        var wkP = pBanDict;
        var sb = new System.Text.StringBuilder();
        sb.AppendFormat("{0} {1} {2} {3}", wkP[1], wkP[6], wkP[11], wkP[16]);
        sb.AppendLine();
        sb.AppendFormat(" {0} {1} {2}", wkP[4], wkP[9], wkP[14]);
        sb.AppendLine();
        sb.AppendFormat("{0} {1} {2} {3}", wkP[2], wkP[7], wkP[12], wkP[17]);
        sb.AppendLine();
        sb.AppendFormat(" {0} {1} {2}", wkP[5], wkP[10], wkP[15]);
        sb.AppendLine();
        sb.AppendFormat("{0} {1} {2} {3}", wkP[3], wkP[8], wkP[13], wkP[18]);
        sb.AppendLine();
        return sb.ToString();
    }
}

実行結果

省略
レベル制限=18で深さ優先探索中。経過時間=00:00:00.6283496
18手の解を発見
■■■■■0手目■■■■■
A * * B
 * * *
A * * B
 * * *
A * * B

■■■■■1手目■■■■■
A * * B
 * * *
A A * B
 * * *
* * * B

■■■■■2手目■■■■■
A * * B
 * * B
A A * *
 * * *
* * * B

■■■■■3手目■■■■■
A * * B
 * * B
A * * *
 * * *
* * A B

■■■■■4手目■■■■■
A * * B
 * B B
A * * *
 * * *
* * A *

■■■■■5手目■■■■■
A * * B
 A B B
* * * *
 * * *
* * A *

■■■■■6手目■■■■■
A * * B
 A * B
* * * *
 * * *
B * A *

■■■■■7手目■■■■■
A A * B
 * * B
* * * *
 * * *
B * A *

■■■■■8手目■■■■■
A A B B
 * * *
* * * *
 * * *
B * A *

■■■■■9手目■■■■■
A * B B
 * * *
* * * *
 * * *
B * A A

■■■■■10手目■■■■■
A * B *
 * * *
* * * *
 * * *
B B A A

■■■■■11手目■■■■■
A * B *
 * * *
* * * *
 * * A
B B * A

■■■■■12手目■■■■■
A * B *
 * * *
B * * *
 * * A
B * * A

■■■■■13手目■■■■■
* * B *
 * * *
B * * *
 * A A
B * * A

■■■■■14手目■■■■■
* * * *
 * * *
B * * *
 B A A
B * * A

■■■■■15手目■■■■■
* * * A
 * * *
B * * *
 B * A
B * * A

■■■■■16手目■■■■■
* * * A
 * * *
B B * *
 * * A
B * * A

■■■■■17手目■■■■■
* * * A
 * * *
B B * A
 * * *
B * * A

■■■■■18手目■■■■■
B * * A
 * * *
B * * A
 * * *
B * * A

経過時間=00:00:00.8161378

解説

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