トップページに戻る    次のC#のサンプルへ    前のC#のサンプルへ

14-03 戦国時代

問題

花菱の戦国時代を解きます。



各ピースをスライドさせ、秀吉が左上の天下統一に到着すればクリアです。


ソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB_X = 5;
    const int UB_Y = 4;

    struct PointDef
    {
        internal int X;
        internal int Y;
    }

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

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

        string[] InitArr ={"FEAA□□",
                           "FE9932",
                           "DD8732",
                           "CC6511",
                           "BB6411"};

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanArr = new char[UB_X + 1, UB_Y + 1];
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                WillPush.BanArr[X, Y] = InitArr[Y][X];
            }
        }
        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);

        List<string> AnswerLog = null;
        int AnswerLevel = 44;

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

            if (IsClear(Popped.BanArr)) {
                if (AnswerLog == null && Popped.Level == AnswerLevel
                 || Popped.Level < AnswerLevel) {
                    AnswerLog = Popped.Log;
                    AnswerLevel = Popped.Level;
                    Console.WriteLine("{0}手の解を発見", Popped.Level);
                }
                continue;
            }
            //下限値枝切り
            if (Popped.Level + DeriveNeedMinTesuu(Popped.BanArr) > AnswerLevel) continue;

            foreach (char EachPiece in "123456789ABCDEF") {
                //盤面とピースを引数として、1手後の盤面のListを返す
                List<char[,]> MovedArrList = DeriveMovedArrList(Popped.BanArr, EachPiece);

                foreach (char[,] EachMovedArr in MovedArrList) {
                    WillPush.BanArr = EachMovedArr;
                    WillPush.Level = Popped.Level + 1;

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

                    WillPush.Log = new List<string>(Popped.Log);
                    WillPush.Log.Add(BanToStr(WillPush.BanArr));
                    Stk.Push(WillPush);
                }
            }
        }
        if (AnswerLog == null) Console.WriteLine("解はありません");
        else {
            for (int I = 0; I <= AnswerLog.Count - 1; I++) {
                Console.WriteLine("{0}手目", I);
                Console.WriteLine(AnswerLog[I]);
            }
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    //クリア判定
    static bool IsClear(char[,] pBanArr)
    {
        return pBanArr[0, 0] == '1';
    }

    //最小の残り手数を返す(下限値枝切り用)
    static int DeriveNeedMinTesuu(char[,] pBanArr)
    {
        PointDef wkPos = DerivePiecePos(pBanArr, '1');
        int X = wkPos.X;
        int Y = wkPos.Y;

        if (X == 1 && Y == 0) return 1;
        if (X == 2 && Y == 0) return 5;
        if (X == 3 && Y == 0) return 9;
        if (X == 4 && Y == 0) return 13;

        if (X == 0 && Y == 1) return 1;
        if (X == 1 && Y == 1) return 5;
        if (X == 2 && Y == 1) return 9;
        if (X == 3 && Y == 1) return 13;
        if (X == 4 && Y == 1) return 17;

        if (X == 0 && Y == 2) return 1;
        if (X == 1 && Y == 2) return 9;
        if (X == 2 && Y == 2) return 13;
        if (X == 3 && Y == 2) return 17;
        if (X == 4 && Y == 2) return 21;

        if (X == 0 && Y == 3) return 9;
        if (X == 1 && Y == 3) return 13;
        if (X == 2 && Y == 3) return 17;
        if (X == 3 && Y == 3) return 21;
        if (X == 4 && Y == 3) return 25;

        return 0;
    }

    struct MoveInfoDef
    {
        internal char[,] BanArr;
        internal PointDef FromPos;
    }

    //盤面とピースを引数として、1手後の盤面のListを返す
    static List<char[,]> DeriveMovedArrList(char[,] pBanArr, char pPiece)
    {
        var WillReturn = new List<char[,]>();

        PointDef PiecePos = DerivePiecePos(pBanArr, pPiece);

        var Stk = new Stack<MoveInfoDef>();
        MoveInfoDef WillPush;
        WillPush.BanArr = pBanArr;
        WillPush.FromPos = PiecePos;
        Stk.Push(WillPush);

        var VisitedSet = new HashSet<ulong>();
        while (Stk.Count > 0) {
            MoveInfoDef Popped = Stk.Pop();

            MoveInfoDef[] MovedInfoArr = DeriveMovedInfoArr(Popped.BanArr, pPiece, Popped.FromPos);
            foreach (MoveInfoDef EachJyoutai in MovedInfoArr) {
                ulong CurrHash = GetHash(EachJyoutai.BanArr);
                if (CurrHash == GetHash(pBanArr)) continue;
                if (VisitedSet.Add(CurrHash) == false) continue;
                WillReturn.Add(EachJyoutai.BanArr);

                //1手で複数マス動けるピースの場合
                if (pPiece != '1') Stk.Push(EachJyoutai);
            }
        }
        return WillReturn;
    }

    //盤面とピースを引数として、移動情報の配列を返す
    static MoveInfoDef[] DeriveMovedInfoArr(char[,] pBanArr, char pPiece, PointDef pFromPos)
    {
        var WillReturn = new List<MoveInfoDef>();

        int FromX = pFromPos.X, FromY = pFromPos.Y;

        Action<char[,], int, int> AddAct1 = (pArr, pToX, pToY) =>
        {
            MoveInfoDef WillAdd;
            WillAdd.BanArr = pArr;
            WillAdd.FromPos = new PointDef() { X = pToX, Y = pToY };
            WillReturn.Add(WillAdd);
        };

        if (pPiece == '1') {
            //上に移動
            if (IsSpace(pBanArr, FromX, FromY - 1)
             && IsSpace(pBanArr, FromX + 1, FromY - 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[FromX, FromY - 1] = wkArr[FromX + 1, FromY - 1] = '1';
                wkArr[FromX, FromY] = wkArr[FromX + 1, FromY] = '1';
                wkArr[FromX, FromY + 1] = wkArr[FromX + 1, FromY + 1] = '□';
                AddAct1(wkArr, FromX, FromY - 1);
            }
            //下に移動
            if (IsSpace(pBanArr, FromX, FromY + 2)
             && IsSpace(pBanArr, FromX + 1, FromY + 2)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[FromX, FromY] = wkArr[FromX + 1, FromY] = '□';
                wkArr[FromX, FromY + 1] = wkArr[FromX + 1, FromY + 1] = '1';
                wkArr[FromX, FromY + 2] = wkArr[FromX + 1, FromY + 2] = '1';
                AddAct1(wkArr, FromX, FromY + 1);
            }
            //左に移動
            if (IsSpace(pBanArr, FromX - 1, FromY)
             && IsSpace(pBanArr, FromX - 1, FromY + 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[FromX - 1, FromY] = '1';
                wkArr[FromX - 1, FromY + 1] = '1';
                wkArr[FromX, FromY] = '1';
                wkArr[FromX, FromY + 1] = '1';
                wkArr[FromX + 1, FromY] = wkArr[FromX + 1, FromY + 1] = '□';
                AddAct1(wkArr, FromX - 1, FromY);
            }

            //右に移動
            if (IsSpace(pBanArr, FromX + 2, FromY)
             && IsSpace(pBanArr, FromX + 2, FromY + 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[FromX + 2, FromY] = '1';
                wkArr[FromX + 2, FromY + 1] = '1';
                wkArr[FromX + 1, FromY] = '1';
                wkArr[FromX + 1, FromY + 1] = '1';
                wkArr[FromX, FromY] = wkArr[FromX, FromY + 1] = '□';
                AddAct1(wkArr, FromX + 1, FromY);
            }
        }

        if (pPiece == '2' || pPiece == '3' || pPiece == '6' || pPiece == 'E' || pPiece == 'F') {
            //上に移動
            if (IsSpace(pBanArr, FromX, FromY - 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[FromX, FromY - 1] = pPiece;
                wkArr[FromX, FromY] = pPiece;
                wkArr[FromX, FromY + 1] = '□';
                AddAct1(wkArr, FromX, FromY - 1);
            }
            //下に移動
            if (IsSpace(pBanArr, FromX, FromY + 2)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[FromX, FromY] = '□';
                wkArr[FromX, FromY + 1] = pPiece;
                wkArr[FromX, FromY + 2] = pPiece;
                AddAct1(wkArr, FromX, FromY + 1);
            }
            //左に移動
            if (IsSpace(pBanArr, FromX - 1, FromY)
             && IsSpace(pBanArr, FromX - 1, FromY + 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[FromX - 1, FromY] = pPiece;
                wkArr[FromX - 1, FromY + 1] = pPiece;
                wkArr[FromX, FromY] = wkArr[FromX, FromY + 1] = '□';
                AddAct1(wkArr, FromX - 1, FromY);
            }
            //右に移動
            if (IsSpace(pBanArr, FromX + 1, FromY)
             && IsSpace(pBanArr, FromX + 1, FromY + 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[FromX + 1, FromY] = pPiece;
                wkArr[FromX + 1, FromY + 1] = pPiece;
                wkArr[FromX, FromY] = wkArr[FromX, FromY + 1] = '□';
                AddAct1(wkArr, FromX + 1, FromY);
            }
        }

        if (pPiece == '9' || pPiece == 'A' || pPiece == 'B' || pPiece == 'C' || pPiece == 'D') {
            //上に移動
            if (IsSpace(pBanArr, FromX, FromY - 1)
             && IsSpace(pBanArr, FromX + 1, FromY - 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[FromX, FromY - 1] = pPiece;
                wkArr[FromX + 1, FromY - 1] = pPiece;
                wkArr[FromX, FromY] = wkArr[FromX + 1, FromY] = '□';
                AddAct1(wkArr, FromX, FromY - 1);
            }
            //下に移動
            if (IsSpace(pBanArr, FromX, FromY + 1)
             && IsSpace(pBanArr, FromX + 1, FromY + 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[FromX, FromY] = wkArr[FromX + 1, FromY] = '□';
                wkArr[FromX, FromY + 1] = pPiece;
                wkArr[FromX + 1, FromY + 1] = pPiece;
                AddAct1(wkArr, FromX, FromY + 1);
            }
            //左に移動
            if (IsSpace(pBanArr, FromX - 1, FromY)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[FromX - 1, FromY] = pPiece;
                wkArr[FromX, FromY] = pPiece;
                wkArr[FromX + 1, FromY] = '□';
                AddAct1(wkArr, FromX - 1, FromY);
            }
            //右に移動
            if (IsSpace(pBanArr, FromX + 2, FromY)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[FromX, FromY] = '□';
                wkArr[FromX + 1, FromY] = pPiece;
                wkArr[FromX + 2, FromY] = pPiece;
                AddAct1(wkArr, FromX + 1, FromY);
            }
        }

        if (pPiece == '4' || pPiece == '5' || pPiece == '7' || pPiece == '8') {
            Action<int, int> AddAct2 = (pToX, pToY) =>
            {
                if (IsSpace(pBanArr, pToX, pToY) == false) return;
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[pToX, pToY] = pPiece; wkArr[FromX, FromY] = '□';
                MoveInfoDef WillAdd;
                WillAdd.BanArr = wkArr;
                WillAdd.FromPos = new PointDef() { X = pToX, Y = pToY };
                WillReturn.Add(WillAdd);
            };

            //上に移動
            AddAct2(FromX, FromY - 1);
            //下に移動
            AddAct2(FromX, FromY + 1);
            //左に移動
            AddAct2(FromX - 1, FromY);
            //右に移動
            AddAct2(FromX + 1, FromY);
        }
        return WillReturn.ToArray();
    }

    //盤面とピースを引数として、ピースの左上の座標を返す
    static PointDef DerivePiecePos(char[,] pBanArr, char pPiece)
    {
        for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
            for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                if (pBanArr[LoopX, LoopY] == pPiece) {
                    return new PointDef() { X = LoopX, Y = LoopY };
                }
            }
        }
        return new PointDef() { X = -1, Y = -1 };
    }

    //座標が空白かを判定
    static bool IsSpace(char[,] pBanArr, int pX, int pY)
    {
        if (pX < 0 || UB_X < pX) return false;
        if (pY < 0 || UB_Y < pY) return false;
        return pBanArr[pX, pY] == '□';
    }

    //ハッシュ値を求める
    static ulong GetHash(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        var AppearedSet = new HashSet<char>();

        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                char CurrChar = pBanArr[X, Y];

                if (CurrChar == '1') {
                    if (AppearedSet.Add(CurrChar)) sb.Append(4);
                }
                else if (CurrChar == '9' || CurrChar == 'A' || CurrChar == 'B'
                      || CurrChar == 'C' || CurrChar == 'D') {
                    if (AppearedSet.Add(CurrChar)) sb.Append(3);
                }
                else if (CurrChar == '2' || CurrChar == '3' || CurrChar == '6'
                      || CurrChar == 'E' || CurrChar == 'F') {
                    if (AppearedSet.Add(CurrChar)) sb.Append(2);
                }
                else if (CurrChar == '4' || CurrChar == '5' || CurrChar == '7'
                      || CurrChar == '8') {
                    if (AppearedSet.Add(CurrChar)) sb.Append(1);
                }
                else sb.Append(0);
            }
        }
        //8の15乗=35184372088832なので8進数ならオーバーフローしない
        return Convert.ToUInt64(sb.ToString(), 8);
    }

    //盤面をString型で表現
    static string BanToStr(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        return sb.ToString();
    }
}


実行結果

省略
43手目
□11699
□116AA
EFDD54
EFCC23
BB7823

44手目
11□699
11□6AA
EFDD54
EFCC23
BB7823

経過時間=00:00:19.3683339


解説

深さ優先探索で44手以下の解を列挙してます。