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

23-07 王将出陣

問題

ハナヤマのWOODY STYLE 王将出陣を解きます。





ソース

using System;
using System.Collections.Generic;

class Program
{
    const int LevelLimit = 81;

    const int UB_X = 3;
    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 ={"歩□□歩",
                           "飛桂香角",
                           "車銀将行",
                           "金王王金",
                           "将将将将"};

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.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++) {
                WillEnqueue.BanArr[X, Y] = InitArr[Y][X];
            }
        }
        WillEnqueue.Level = 0;
        WillEnqueue.Log = new List<string>();
        WillEnqueue.Log.Add(BanToStr(WillEnqueue.BanArr));
        Que.Enqueue(WillEnqueue);

        var VisitedSet = new HashSet<ulong>();
        VisitedSet.Add(GetHash(WillEnqueue.BanArr));

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            if (IsClear(Dequeued.BanArr)) {
                for (int I = 0; I <= Dequeued.Log.Count - 1; I++) {
                    Console.WriteLine("{0}手目", I);
                    Console.WriteLine(Dequeued.Log[I]);
                }
                break;
            }
            //下限値枝切り
            if (Dequeued.Level + DeriveNeedMinTesuu(Dequeued.BanArr) > LevelLimit) continue;

            foreach (char EachPiece in "歩香桂銀金角飛王") {
                //特殊枝切り 2手目は、香を動かす
                if (Dequeued.Level == 1 && EachPiece != '歩' && EachPiece != '香') continue;

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

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

                    //再訪防止
                    if (VisitedSet.Add(GetHash(EachMovedArr)) == false) continue;

                    WillEnqueue.Log = new List<string>(Dequeued.Log);
                    WillEnqueue.Log.Add(BanToStr(WillEnqueue.BanArr));
                    Que.Enqueue(WillEnqueue);
                }
            }
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

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

    //最小の残り手数を返す(下限値枝切り用)
    static int DeriveNeedMinTesuu(char[,] pBanArr)
    {
        if (pBanArr[0, 0] == '王') return 1;
        if (pBanArr[1, 0] == '王') return 0;
        if (pBanArr[2, 0] == '王') return 1;
        if (pBanArr[0, 1] == '王') return 5;
        if (pBanArr[1, 1] == '王') return 1;
        if (pBanArr[2, 1] == '王') return 5;
        if (pBanArr[0, 2] == '王') return 9;
        if (pBanArr[1, 2] == '王') return 5;
        if (pBanArr[2, 2] == '王') return 9;
        if (pBanArr[0, 3] == '王') return 13;
        if (pBanArr[1, 3] == '王') return 9;
        if (pBanArr[2, 3] == '王') return 13;
        return -1;
    }

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

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

        PointDef[] PiecePosArr = DerivePiecePosArr(pBanArr, pPiece);

        var Stk = new Stack<MoveInfoDef>();
        MoveInfoDef WillPush;
        foreach (PointDef EachPos in PiecePosArr) {
            WillPush.BanArr = pBanArr;
            WillPush.FromPos = EachPos;
            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);
                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 == '王') {
            //上に移動
            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] = '王';
                wkArr[FromX, FromY] = wkArr[FromX + 1, FromY] = '将';
                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] = '王';
                wkArr[FromX, FromY + 2] = wkArr[FromX + 1, FromY + 2] = '将';
                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] = '王';
                wkArr[FromX - 1, FromY + 1] = '将';
                wkArr[FromX, FromY] = '王';
                wkArr[FromX, FromY + 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] = '王';
                wkArr[FromX + 2, FromY + 1] = '将';
                wkArr[FromX + 1, FromY] = '王';
                wkArr[FromX + 1, FromY + 1] = '将';
                wkArr[FromX, FromY] = wkArr[FromX, FromY + 1] = '□';
                AddAct1(wkArr, FromX + 1, FromY);
            }
        }

        if (pPiece == '角' || pPiece == '飛' || pPiece == '金') {
            Func<char> Derive2Mojime = () =>
            {
                if (pPiece == '金') return '将';
                if (pPiece == '角') return '行';
                return '車';
            };

            //上に移動
            if (IsSpace(pBanArr, FromX, FromY - 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[FromX, FromY - 1] = pPiece;
                wkArr[FromX, FromY] = Derive2Mojime();
                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] = Derive2Mojime();
                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] = Derive2Mojime();
                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] = Derive2Mojime();
                wkArr[FromX, FromY] = wkArr[FromX, FromY + 1] = '□';
                AddAct1(wkArr, FromX + 1, FromY);
            }
        }

        if (pPiece == '銀') {
            //上に移動
            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] = '将';
                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] = '銀';
                wkArr[FromX + 1, FromY + 1] = '将';
                AddAct1(wkArr, FromX, FromY + 1);
            }
            //左に移動
            if (IsSpace(pBanArr, FromX - 1, FromY)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[FromX - 1, FromY] = '銀';
                wkArr[FromX, FromY] = '将';
                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] = '銀';
                wkArr[FromX + 2, FromY] = '将';
                AddAct1(wkArr, FromX + 1, FromY);
            }
        }

        if (pPiece == '桂' || pPiece == '香' || pPiece == '歩') {
            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[] DerivePiecePosArr(char[,] pBanArr, char pPiece)
    {
        var WillReturn = new List<PointDef>();

        for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
            for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                if (pBanArr[LoopX, LoopY] == pPiece) {
                    PointDef WillAdd;
                    WillAdd.X = LoopX;
                    WillAdd.Y = LoopY;
                    WillReturn.Add(WillAdd);

                    //王将は1座標のみ
                    if (pPiece == '王') break;
                }
            }
        }
        return WillReturn.ToArray();
    }

    //座標が空白かを判定
    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 NumList = new List<ulong>();

        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                char wkChar = pBanArr[X, Y];
                if (wkChar == '将') continue;
                if (wkChar == '車') continue;
                if (wkChar == '行') continue;

                if (wkChar == '王') NumList.Add(4);
                else if (wkChar == '飛') NumList.Add(3);
                else if (wkChar == '角') NumList.Add(3);
                else if (wkChar == '金') NumList.Add(3);
                else if (wkChar == '銀') NumList.Add(2);
                else if (wkChar == '歩') NumList.Add(1);
                else if (wkChar == '香') NumList.Add(1);
                else if (wkChar == '桂') NumList.Add(1);
                else NumList.Add(0);
            }
        }

        //5の21乗=476837158203125なので5進数ならオーバーフローしない
        ulong WillReturn = 0;
        foreach (ulong EachInt in NumList) {
            WillReturn *= 5;
            WillReturn += EachInt;
        }

        return WillReturn;
    }

    //盤面を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();
    }
}


実行結果

省略
80手目
歩□王王
歩□将将
銀将桂香
飛金角金
車将行将

81手目
歩王王□
歩将将□
銀将桂香
飛金角金
車将行将

経過時間=00:00:02.1688695


解説

手数上限を81手として下限値枝切りする、幅優先探索で解いてます。

14-01 アウトゲーム 王将