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

13-06 ラビリンス88

問題

植松峰幸さんのラビリンス88を解きます。



6個のT字型ピースと1個の十字架型ピース、
それに赤と緑の丸いピース1個ずつ、合計9個のピースで構成されているスライドパズル。
指定のスタート位置にそれぞれピースを置き、赤と黄緑の丸いピースを入れ換えるのが目的です。

タイトルの“88”は88手かかるという意味です。


ソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB = 5;

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

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

    static void Main()
    {
        string[] InitArr ={"12223□",
                           "112333",
                           "1444赤5",
                           "□64□55",
                           "666黄75",
                           "□6□777"};

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanArr = new char[UB + 1, UB + 1];
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; 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<string, int>();
        MinTesuuDict.Add(GetHash(WillPush.BanArr), 0);

        List<string> AnswerLog = null;

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

            if (IsClear(Popped.BanArr)) {
                AnswerLog = Popped.Log;
                continue;
            }

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

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

                    //メモ化探索
                    int MinTesuu;
                    string Hash = GetHash(EachMovedBanArr);
                    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);
                }
            }
        }
        for (int I = 0; I <= AnswerLog.Count - 1; I++) {
            Console.WriteLine("{0}手目", I);
            Console.WriteLine(AnswerLog[I]);
        }
    }

    //クリア判定
    static bool IsClear(char[,] pBanArr)
    {
        if (pBanArr[4, 2] != '黄') return false;
        if (pBanArr[3, 4] != '赤') return false;
        return true;
    }

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

        var Stk = new Stack<char[,]>();
        char[,] WillPush;
        WillPush = pBanArr;
        Stk.Push(WillPush);

        var VisitedSet = new HashSet<string>();
        while (Stk.Count > 0) {
            char[,] Popped = Stk.Pop();

            List<char[,]> MovedBanArrList = DeriveMovedBanArrListHelper(Popped, pPiece);
            foreach (char[,] EachBanArr in MovedBanArrList) {
                string CurrHash = GetHash(EachBanArr);
                if (CurrHash == GetHash(pBanArr)) continue;
                if (VisitedSet.Add(CurrHash) == false) continue;
                WillReturn.Add(EachBanArr);

                Stk.Push(EachBanArr);
            }
        }
        return WillReturn;
    }

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

        PointDef wkPiecePoint = DerivePiecePoint(pBanArr, pPiece);
        int CurrX = wkPiecePoint.X;
        int CurrY = wkPiecePoint.Y;

        if (pPiece == '1') {
            //上に移動
            if (IsSpace(pBanArr, CurrX, CurrY - 1)
             && IsSpace(pBanArr, CurrX + 1, CurrY)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX, CurrY - 1] = '1';
                wkArr[CurrX + 1, CurrY] = '1';
                wkArr[CurrX, CurrY + 2] = '□';
                wkArr[CurrX + 1, CurrY + 1] = '□';
                WillReturn.Add(wkArr);
            }
            //下に移動
            if (IsSpace(pBanArr, CurrX, CurrY + 3)
             && IsSpace(pBanArr, CurrX + 1, CurrY + 2)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX, CurrY + 3] = '1';
                wkArr[CurrX + 1, CurrY + 2] = '1';
                wkArr[CurrX, CurrY] = '□';
                wkArr[CurrX + 1, CurrY + 1] = '□';
                WillReturn.Add(wkArr);
            }
            //左に移動
            if (IsSpace(pBanArr, CurrX - 1, CurrY)
             && IsSpace(pBanArr, CurrX - 1, CurrY + 1)
             && IsSpace(pBanArr, CurrX - 1, CurrY + 2)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX - 1, CurrY] = '1';
                wkArr[CurrX - 1, CurrY + 1] = '1';
                wkArr[CurrX - 1, CurrY + 2] = '1';
                wkArr[CurrX, CurrY] = '□';
                wkArr[CurrX + 1, CurrY + 1] = '□';
                wkArr[CurrX, CurrY + 2] = '□';
                WillReturn.Add(wkArr);
            }
            //右に移動
            if (IsSpace(pBanArr, CurrX + 1, CurrY)
             && IsSpace(pBanArr, CurrX + 2, CurrY + 1)
             && IsSpace(pBanArr, CurrX + 1, CurrY + 2)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX + 1, CurrY] = '1';
                wkArr[CurrX + 2, CurrY + 1] = '1';
                wkArr[CurrX + 1, CurrY + 2] = '1';
                wkArr[CurrX, CurrY] = '□';
                wkArr[CurrX, CurrY + 1] = '□';
                wkArr[CurrX, CurrY + 2] = '□';
                WillReturn.Add(wkArr);
            }
        }

        if (pPiece == '2' || pPiece == '4') {
            //上に移動
            if (IsSpace(pBanArr, CurrX, CurrY - 1)
             && IsSpace(pBanArr, CurrX + 1, CurrY - 1)
             && IsSpace(pBanArr, CurrX + 2, CurrY - 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX, CurrY - 1] = pPiece;
                wkArr[CurrX + 1, CurrY - 1] = pPiece;
                wkArr[CurrX + 2, CurrY - 1] = pPiece;
                wkArr[CurrX, CurrY] = '□';
                wkArr[CurrX + 1, CurrY + 1] = '□';
                wkArr[CurrX + 2, CurrY] = '□';
                WillReturn.Add(wkArr);
            }
            //下に移動
            if (IsSpace(pBanArr, CurrX, CurrY + 1)
             && IsSpace(pBanArr, CurrX + 1, CurrY + 2)
             && IsSpace(pBanArr, CurrX + 2, CurrY + 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX, CurrY + 1] = pPiece;
                wkArr[CurrX + 1, CurrY + 2] = pPiece;
                wkArr[CurrX + 2, CurrY + 1] = pPiece;
                wkArr[CurrX, CurrY] = '□';
                wkArr[CurrX + 1, CurrY] = '□';
                wkArr[CurrX + 2, CurrY] = '□';
                WillReturn.Add(wkArr);
            }
            //左に移動
            if (IsSpace(pBanArr, CurrX - 1, CurrY)
             && IsSpace(pBanArr, CurrX, CurrY + 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX - 1, CurrY] = pPiece;
                wkArr[CurrX, CurrY + 1] = pPiece;
                wkArr[CurrX + 2, CurrY] = '□';
                wkArr[CurrX + 1, CurrY + 1] = '□';
                WillReturn.Add(wkArr);
            }
            //右に移動
            if (IsSpace(pBanArr, CurrX + 3, CurrY)
             && IsSpace(pBanArr, CurrX + 2, CurrY + 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX + 3, CurrY] = pPiece;
                wkArr[CurrX + 2, CurrY + 1] = pPiece;
                wkArr[CurrX, CurrY] = '□';
                wkArr[CurrX + 1, CurrY + 1] = '□';
                WillReturn.Add(wkArr);
            }
        }

        if (pPiece == '3' || pPiece == '7') {
            //上に移動
            if (IsSpace(pBanArr, CurrX - 1, CurrY)
             && IsSpace(pBanArr, CurrX, CurrY - 1)
             && IsSpace(pBanArr, CurrX + 1, CurrY)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX - 1, CurrY] = pPiece;
                wkArr[CurrX, CurrY - 1] = pPiece;
                wkArr[CurrX + 1, CurrY] = pPiece;
                wkArr[CurrX - 1, CurrY + 1] = '□';
                wkArr[CurrX, CurrY + 1] = '□';
                wkArr[CurrX + 1, CurrY + 1] = '□';
                WillReturn.Add(wkArr);
            }
            //下に移動
            if (IsSpace(pBanArr, CurrX - 1, CurrY + 2)
             && IsSpace(pBanArr, CurrX, CurrY + 2)
             && IsSpace(pBanArr, CurrX + 1, CurrY + 2)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX - 1, CurrY + 2] = pPiece;
                wkArr[CurrX, CurrY + 2] = pPiece;
                wkArr[CurrX + 1, CurrY + 2] = pPiece;
                wkArr[CurrX - 1, CurrY + 1] = '□';
                wkArr[CurrX, CurrY] = '□';
                wkArr[CurrX + 1, CurrY + 1] = '□';
                WillReturn.Add(wkArr);
            }
            //左に移動
            if (IsSpace(pBanArr, CurrX - 1, CurrY)
             && IsSpace(pBanArr, CurrX - 2, CurrY + 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX - 1, CurrY] = pPiece;
                wkArr[CurrX - 2, CurrY + 1] = pPiece;
                wkArr[CurrX, CurrY] = '□';
                wkArr[CurrX + 1, CurrY + 1] = '□';
                WillReturn.Add(wkArr);
            }
            //右に移動
            if (IsSpace(pBanArr, CurrX + 1, CurrY)
             && IsSpace(pBanArr, CurrX + 2, CurrY + 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX + 1, CurrY] = pPiece;
                wkArr[CurrX + 2, CurrY + 1] = pPiece;
                wkArr[CurrX, CurrY] = '□';
                wkArr[CurrX - 1, CurrY + 1] = '□';
                WillReturn.Add(wkArr);
            }
        }

        if (pPiece == '5') {
            //上に移動
            if (IsSpace(pBanArr, CurrX - 1, CurrY)
             && IsSpace(pBanArr, CurrX, CurrY - 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX - 1, CurrY] = '5';
                wkArr[CurrX, CurrY - 1] = '5';
                wkArr[CurrX - 1, CurrY + 1] = '□';
                wkArr[CurrX, CurrY + 2] = '□';
                WillReturn.Add(wkArr);
            }
            //下に移動
            if (IsSpace(pBanArr, CurrX - 1, CurrY + 2)
             && IsSpace(pBanArr, CurrX, CurrY + 3)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX - 1, CurrY + 2] = '5';
                wkArr[CurrX, CurrY + 3] = '5';
                wkArr[CurrX - 1, CurrY + 1] = '□';
                wkArr[CurrX, CurrY] = '□';
                WillReturn.Add(wkArr);
            }
            //左に移動
            if (IsSpace(pBanArr, CurrX - 1, CurrY)
             && IsSpace(pBanArr, CurrX, CurrY + 1)
             && IsSpace(pBanArr, CurrX - 1, CurrY + 2)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX - 1, CurrY] = '5';
                wkArr[CurrX - 2, CurrY + 1] = '5';
                wkArr[CurrX - 1, CurrY + 2] = '5';
                wkArr[CurrX + 1, CurrY] = '□';
                wkArr[CurrX + 1, CurrY + 1] = '□';
                wkArr[CurrX + 1, CurrY + 2] = '□';
                WillReturn.Add(wkArr);
            }
            //右に移動
            if (IsSpace(pBanArr, CurrX + 1, CurrY)
             && IsSpace(pBanArr, CurrX + 1, CurrY + 1)
             && IsSpace(pBanArr, CurrX + 1, CurrY + 2)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX + 1, CurrY] = '5';
                wkArr[CurrX + 1, CurrY + 1] = '5';
                wkArr[CurrX + 1, CurrY + 2] = '5';
                wkArr[CurrX, CurrY] = '□';
                wkArr[CurrX - 1, CurrY + 1] = '□';
                wkArr[CurrX, CurrY + 2] = '□';
                WillReturn.Add(wkArr);
            }
        }

        if (pPiece == '6') {
            //上に移動
            if (IsSpace(pBanArr, CurrX - 1, CurrY)
             && IsSpace(pBanArr, CurrX, CurrY - 1)
             && IsSpace(pBanArr, CurrX + 1, CurrY)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX - 1, CurrY] = '6';
                wkArr[CurrX, CurrY - 1] = '6';
                wkArr[CurrX + 1, CurrY] = '6';
                wkArr[CurrX - 1, CurrY + 1] = '□';
                wkArr[CurrX, CurrY + 2] = '□';
                wkArr[CurrX + 1, CurrY + 1] = '□';
                WillReturn.Add(wkArr);
            }
            //下に移動
            if (IsSpace(pBanArr, CurrX - 1, CurrY + 2)
             && IsSpace(pBanArr, CurrX, CurrY + 3)
             && IsSpace(pBanArr, CurrX + 1, CurrY + 2)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX - 1, CurrY + 2] = '6';
                wkArr[CurrX, CurrY + 3] = '6';
                wkArr[CurrX + 1, CurrY + 2] = '6';
                wkArr[CurrX - 1, CurrY + 1] = '□';
                wkArr[CurrX, CurrY] = '□';
                wkArr[CurrX + 1, CurrY + 1] = '□';
                WillReturn.Add(wkArr);
            }
            //左に移動
            if (IsSpace(pBanArr, CurrX - 1, CurrY)
             && IsSpace(pBanArr, CurrX - 2, CurrY + 1)
             && IsSpace(pBanArr, CurrX - 1, CurrY + 2)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX - 1, CurrY] = '6';
                wkArr[CurrX - 2, CurrY + 1] = '6';
                wkArr[CurrX - 1, CurrY + 2] = '6';
                wkArr[CurrX, CurrY] = '□';
                wkArr[CurrX + 1, CurrY + 1] = '□';
                wkArr[CurrX, CurrY + 2] = '□';
                WillReturn.Add(wkArr);
            }
            //右に移動
            if (IsSpace(pBanArr, CurrX + 1, CurrY)
             && IsSpace(pBanArr, CurrX + 2, CurrY + 1)
             && IsSpace(pBanArr, CurrX + 1, CurrY + 2)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX + 1, CurrY] = '6';
                wkArr[CurrX + 2, CurrY + 1] = '6';
                wkArr[CurrX + 1, CurrY + 2] = '6';
                wkArr[CurrX, CurrY] = '□';
                wkArr[CurrX - 1, CurrY + 1] = '□';
                wkArr[CurrX, CurrY + 2] = '□';
                WillReturn.Add(wkArr);
            }
        }

        if (pPiece == '赤' || pPiece == '黄') {
            //上に移動
            if (IsSpace(pBanArr, CurrX, CurrY - 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX, CurrY - 1] = pPiece; wkArr[CurrX, CurrY] = '□';
                WillReturn.Add(wkArr);
            }
            //下に移動
            if (IsSpace(pBanArr, CurrX, CurrY + 1)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX, CurrY + 1] = pPiece; wkArr[CurrX, CurrY] = '□';
                WillReturn.Add(wkArr);
            }
            //左に移動
            if (IsSpace(pBanArr, CurrX - 1, CurrY)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX - 1, CurrY] = pPiece; wkArr[CurrX, CurrY] = '□';
                WillReturn.Add(wkArr);
            }
            //右に移動
            if (IsSpace(pBanArr, CurrX + 1, CurrY)) {
                char[,] wkArr = (char[,])pBanArr.Clone();
                wkArr[CurrX + 1, CurrY] = pPiece; wkArr[CurrX, CurrY] = '□';
                WillReturn.Add(wkArr);
            }
        }
        return WillReturn;
    }

    //盤面とピースを引数として、ピースの左上の座標を返す
    static PointDef DerivePiecePoint(char[,] pBanArr, char pPiece)
    {
        for (int LoopY = 0; LoopY <= UB; LoopY++) {
            for (int LoopX = 0; LoopX <= UB; 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 < pX) return false;
        if (pY < 0 || UB < pY) return false;
        return pBanArr[pX, pY] == '□';
    }

    //ハッシュ値を求める
    static string GetHash(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                sb.Append(pBanArr[X, Y]);
            }
        }
        return sb.ToString();
    }

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


実行結果

省略
87手目
12223□
112333
1444黄5
□64赤55
666□75
□6□777

88手目
12223□
112333
1444黄5
□64□55
666赤75
□6□777


解説

メモ化探索な深さ優先探索で解いてます。