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

14-02 牛の牧場

問題

花菱の牛の牧場を解きます。



各ピースをスライドさせ、
牛が右下に到達し、
牛が柵に囲まれて(上の画像で、3つある柵のピースの初期状態)、
2つの空白マスが縦の柵の左(座標だと[1,2]と[1,3])、にあればクリアです。

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int LevelLimit = 73;

    const int UB_X = 4;
    const int UB_Y = 3;

    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 "牛止横縦小木コ輪ミ") {
                //盤面とピースを引数として、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)
    {
        if (pBanArr[3, 2] != '牛') return false;
        if (pBanArr[4, 2] != '牛') return false;
        if (pBanArr[3, 3] != '牛') return false;
        if (pBanArr[4, 3] != '牛') return false;
        if (pBanArr[2, 0] != '止') return false;
        if (pBanArr[2, 1] != '止') return false;
        if (pBanArr[3, 1] != '横') return false;
        if (pBanArr[4, 1] != '横') return false;
        if (pBanArr[2, 2] != '縦') return false;
        if (pBanArr[2, 3] != '縦') return false;
        if (pBanArr[1, 2] != '□') return false;
        if (pBanArr[1, 3] != '□') return false;

        return true;
    }

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

        if (X == 0 && Y == 0) return 18;
        if (X == 1 && Y == 0) return 14;
        if (X == 2 && Y == 0) return 10;
        if (X == 3 && Y == 0) return 6;

        if (X == 0 && Y == 1) return 14;
        if (X == 1 && Y == 1) return 10;
        if (X == 2 && Y == 1) return 6;
        if (X == 3 && Y == 1) return 2;

        if (X == 0 && Y == 2) return 10;
        if (X == 1 && Y == 2) return 6;
        if (X == 2 && Y == 2) return 2;

        //牛が[3,2]にいたら、柵の座標を見る
        int WillReturn = 0;
        wkPos = DerivePiecePosArr(pBanArr, '止')[0];
        if (wkPos.Y != 0) WillReturn++;
        WillReturn += Math.Abs(2 - wkPos.X);

        wkPos = DerivePiecePosArr(pBanArr, '横')[0];
        if (wkPos.X != 3) WillReturn++;
        WillReturn += Math.Abs(1 - wkPos.Y);

        wkPos = DerivePiecePosArr(pBanArr, '縦')[0];
        if (wkPos.Y != 2) WillReturn++;
        WillReturn += Math.Abs(2 - wkPos.X);

        return WillReturn;
    }

    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);

                //1手で複数マス動けるピースの場合
                if (pPiece != '牛') 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 == '縦') {
            //上に移動
            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 == '横' || pPiece == '小') {
            Func<char> Derive2Mojime = () => pPiece == '横' ? '横' : '屋';

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

        if (pPiece == '木' || 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 != '木') return WillReturn.ToArray();
                }
            }
        }
        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 sb = new System.Text.StringBuilder();

        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 == '牛') sb.Append('6');
                else if (wkChar == '止') sb.Append('5');
                else if (wkChar == '横') sb.Append('4');
                else if (wkChar == '縦') sb.Append('3');
                else if (wkChar == '小') sb.Append('2');
                else if (wkChar == '木') sb.Append('1');
                else if (wkChar == 'コ') sb.Append('1');
                else if (wkChar == '輪') sb.Append('1');
                else if (wkChar == 'ミ') sb.Append('1');
                else sb.Append('0');
            }
        }
        //8の21乗=9223372036854780000なので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();
    }
}

実行結果

省略
72手目
木コ止小屋
木□止横横
輪□縦牛牛
ミ木縦牛牛

73手目
木コ止小屋
木木止横横
輪□縦牛牛
ミ□縦牛牛

経過時間=00:00:23.1169989

解説

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