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

18-04 ブロック10

問題

みのるパズルのブロック10を解きます。



各ピースをスライドさせ、リンゴが中央上に到着すればクリアです。


ソース

using System;
using System.Collections.Generic;
using System.Linq;

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

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

    static char[,] mQuestionArr = new char[UB_X + 1, UB_Y + 1]; //問題の初期盤面
    const char mRingoChar = '7'; //リンゴの文字

    //問題を定義
    static void QuestionDef()
    {
        string[] wkArr ={"*□□*",
                         "1□□2",
                         "3322",
                         "4456",
                         "4776",
                         "8779"};

        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                mQuestionArr[X, Y] = wkArr[Y][X];
            }
        }
    }

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

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

        //問題を定義
        QuestionDef();

        //ピースの配置情報を取得
        DerivePieceHeniListDict();

        //ピースの変位情報のDense_Rankを取得
        DerivePieceHeniDnDict();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanArr = mQuestionArr;
        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 = 26;

        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 "123456789") {
                //盤面とピースを引数として、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);
                }
            }
        }
        for (int I = 0; I <= AnswerLog.Count - 1; I++) {
            Console.WriteLine("{0}手目", I);
            Console.WriteLine(AnswerLog[I]);
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    //ピースの配置情報を取得
    static Dictionary<char, List<PointDef>> mPieceHeniListDict = new Dictionary<char, List<PointDef>>();
    static void DerivePieceHeniListDict()
    {
        char[] PieceArr = mQuestionArr.Cast<char>().Where(X => X != '□').Distinct().ToArray();
        Array.Sort(PieceArr);

        foreach (char EachPiece in PieceArr) {
            bool FirstFlag = true;
            PointDef GentenPos = new PointDef() { X = -1, Y = -1 };
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                    if (mQuestionArr[LoopX, LoopY] != EachPiece) continue;

                    if (FirstFlag) {
                        FirstFlag = false;
                        GentenPos.X = LoopX;
                        GentenPos.Y = LoopY;
                        mPieceHeniListDict.Add(EachPiece, new List<PointDef>());
                    }
                    //原点 + 変位ベクトル = カレント座標
                    //を移項
                    PointDef HeniVect;
                    HeniVect.X = LoopX - GentenPos.X;
                    HeniVect.Y = LoopY - GentenPos.Y;
                    mPieceHeniListDict[EachPiece].Add(HeniVect);
                }
            }
        }
    }

    //ピースの変位情報のDense_Rankを取得
    static Dictionary<char, ulong> mPieceHeniDnDict = new Dictionary<char, ulong>();
    static void DerivePieceHeniDnDict()
    {
        var wkList = new List<string>();
        foreach (var EachPair in mPieceHeniListDict) {
            var sb = new System.Text.StringBuilder();
            foreach (PointDef EachPoint in EachPair.Value) {
                sb.AppendFormat("{0}{1}", EachPoint.X, EachPoint.Y);
            }
            string wkStr = sb.ToString();
            if (wkList.Contains(wkStr) == false)
                wkList.Add(wkStr);

            mPieceHeniDnDict.Add(EachPair.Key, 1 + (ulong)wkList.IndexOf(wkStr));
        }
    }

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

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

        if (Y == 0) return 0;
        if (Y == 1) return 1;
        if (Y == 2) return 1;
        if (Y == 3) return 2;
        if (Y == 4) return 2;
        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);

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

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

        //変位ベクトルのList
        var HeniList = new List<PointDef>();
        HeniList.Add(new PointDef() { X = 0, Y = -1 });
        HeniList.Add(new PointDef() { X = 0, Y = +1 });
        HeniList.Add(new PointDef() { X = -1, Y = 0 });
        HeniList.Add(new PointDef() { X = +1, Y = 0 });

        foreach (PointDef EachHeni in HeniList) {
            bool CanMove = true;
            foreach (PointDef EachPos in mPieceHeniListDict[pPiece]) {
                int X = pFromPos.X + EachPos.X + EachHeni.X;
                int Y = pFromPos.Y + EachPos.Y + EachHeni.Y;

                if (X < 0 || UB_X < X) CanMove = false;
                if (Y < 0 || UB_Y < Y) CanMove = false;
                if (CanMove == false) break;

                if (pBanArr[X, Y] != '□' && pBanArr[X, Y] != pPiece)
                    CanMove = false;
            }
            if (CanMove == false) continue;

            //移動可能な場合
            char[,] wkArr = (char[,])pBanArr.Clone();
            foreach (PointDef EachPos in mPieceHeniListDict[pPiece]) {
                int X = pFromPos.X + EachPos.X;
                int Y = pFromPos.Y + EachPos.Y;
                wkArr[X, Y] = '□'; //空白で埋める
            }
            foreach (PointDef EachPos in mPieceHeniListDict[pPiece]) {
                int X = pFromPos.X + EachPos.X + EachHeni.X;
                int Y = pFromPos.Y + EachPos.Y + EachHeni.Y;
                wkArr[X, Y] = pPiece; //ピースで埋める
            }
            MoveInfoDef WillAdd;
            WillAdd.BanArr = wkArr;
            WillAdd.FromPos = new PointDef() { X = pFromPos.X + EachHeni.X, Y = pFromPos.Y + EachHeni.Y };
            WillReturn.Add(WillAdd);
        }
        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 ulong GetHash(char[,] pBanArr)
    {
        var AppearedSet = new HashSet<char>();
        var sb = new System.Text.StringBuilder();

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

                if (CurrChar == '□') {
                    sb.Append('0');
                }
                else if (AppearedSet.Add(CurrChar)) {
                    sb.Append(mPieceHeniDnDict[CurrChar]);
                }
            }
        }

        //ULong型ならオーバーフローしない
        return Convert.ToUInt64(sb.ToString());
    }

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


実行結果

省略
26手目
*77*
177□
6□□□
6933
5244
2248

経過時間=00:00:11.8379978


解説

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