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

22-01 Flip It

問題

ThinkfunのFlip Itを解きます。


    

カメは、1匹または2匹のカメを、縦か横か斜め45度に、跳び越して移動できます。
跳び越されたカメは、表裏が反転します。
全てのカメが表になればクリアです。

同じカメが動き続ける限り1手として、最少手数で解きます。

Q1
裏裏□□
□□□裏
□□□□
□□□□

Q2
□裏裏□
裏裏裏裏
裏裏裏裏
□裏裏□

Q3
□裏裏□
裏裏□裏
裏□裏裏
□裏裏□

Q4
□裏裏□
裏□□裏
□裏裏□
□□□□

Q5
裏□裏□
表表□裏
□裏裏裏
□□表裏

Q6
表裏表裏
裏表裏表
表裏表裏
□表裏表


ソース

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

class Program
{
    static int mQuestionNo = 2;
    static char[,] mQuestionArr; //問題の初期盤面

    const int UB = 4 - 1;

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

    //問題を定義
    static void QuestionDef()
    {
        string[] wkStrArr = null;
        if (mQuestionNo == 1) {
            wkStrArr = new string[] {"裏裏□□",
                                     "□□□裏",
                                     "□□□□",
                                     "□□□□"};
        }
        if (mQuestionNo == 2) {
            wkStrArr = new string[] {"□裏裏□",
                                     "裏裏裏裏",
                                     "裏裏裏裏",
                                     "□裏裏□"};
        }
        if (mQuestionNo == 3) {
            wkStrArr = new string[] {"□裏裏□",
                                     "裏裏□裏",
                                     "裏□裏裏",
                                     "□裏裏□"};
        }
        if (mQuestionNo == 4) {
            wkStrArr = new string[] {"□裏裏□",
                                     "裏□□裏",
                                     "□裏裏□",
                                     "□□□□"};
        }
        if (mQuestionNo == 5) {
            wkStrArr = new string[] {"裏□裏□",
                                     "表表□裏",
                                     "□裏裏裏",
                                     "□□表裏"};
        }
        if (mQuestionNo == 6) {
            wkStrArr = new string[] {"表裏表裏",
                                     "裏表裏表",
                                     "表裏表裏",
                                     "□表裏表"};
        }

        mQuestionArr = new char[UB + 1, UB + 1];
        for (int Y = 0; Y <= UB; Y++)
            for (int X = 0; X <= UB; X++)
                mQuestionArr[Y, X] = wkStrArr[X][Y];
    }

    static void Main()
    {
        //問題を定義
        QuestionDef();

        //反復深化深さ優先探索で解く
        for (int I = 1; I < int.MaxValue; I++) {
            Console.WriteLine("手数制限={0}で深さ優先探索を実行中", I);
            if (ExecDFS(I)) break;
        }
    }

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

    //手数制限を引数として深さ優先探索を行う
    static bool ExecDFS(int pTesuuMax)
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Tesuu = 0;
        WillPush.Level = 0;
        WillPush.BanArr = mQuestionArr;
        WillPush.CurrPos = new PointDef() { X = -1, Y = -1 };
        WillPush.Log = new List<char[,]>() { WillPush.BanArr };
        Stk.Push(WillPush);

        int AnswerLevel = int.MaxValue;
        List<char[,]> AnswerKouhoLog = null;
        bool FoundAnswer = false;

        //盤面に対する最少手数のDict
        var MinTesuuDict = new Dictionary<string, MinTesuuInfo>();

        MinTesuuDict.Add(GetHash(WillPush.BanArr, WillPush.CurrPos),
            new MinTesuuInfo() { Tesuu = 0, Level = 0 });

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

            //下限値枝切り
            if (pTesuuMax < Popped.Tesuu) continue;
            if (pTesuuMax == Popped.Tesuu && AnswerLevel <= Popped.Level) continue;

            //クリア判定
            if (IsClear(Popped.BanArr)) {
                if (Popped.Level < AnswerLevel) {
                    Console.WriteLine("{0}手({1}レベル)の解候補を発見",
                        Popped.Tesuu, Popped.Level);

                    AnswerLevel = Popped.Level;
                    AnswerKouhoLog = Popped.Log;
                    FoundAnswer = true;
                }
                continue;
            }

            for (int LoopX = 0; LoopX <= UB; LoopX++) {
                for (int LoopY = 0; LoopY <= UB; LoopY++) {
                    if (Popped.BanArr[LoopX, LoopY] == '□') continue;

                    JumpedInfoDef[] JumpedInfoArr =
                        DeriveJumpedInfoArr(Popped.BanArr, LoopX, LoopY);

                    foreach (JumpedInfoDef EachJumoedInfo in JumpedInfoArr) {
                        if (Popped.CurrPos.X != LoopX || Popped.CurrPos.Y != LoopY)
                            WillPush.Tesuu = Popped.Tesuu + 1;
                        else WillPush.Tesuu = Popped.Tesuu;

                        WillPush.Level = Popped.Level + 1;
                        WillPush.BanArr = EachJumoedInfo.BanArr;
                        WillPush.CurrPos = EachJumoedInfo.NewCurrPos;
                        WillPush.Log = new List<char[,]>(Popped.Log) { WillPush.BanArr };

                        string CurrHash = GetHash(WillPush.BanArr, WillPush.CurrPos);
                        MinTesuuInfo CurrTesuuInfo;
                        CurrTesuuInfo.Tesuu = WillPush.Tesuu;
                        CurrTesuuInfo.Level = WillPush.Level;

                        if (MinTesuuDict.ContainsKey(CurrHash)) {
                            if (MinTesuuDict[CurrHash].Tesuu < CurrTesuuInfo.Tesuu)
                                continue;
                            if (MinTesuuDict[CurrHash].Tesuu == CurrTesuuInfo.Tesuu
                             && MinTesuuDict[CurrHash].Level <= CurrTesuuInfo.Level)
                                continue;
                        }
                        MinTesuuDict[CurrHash] = CurrTesuuInfo;
                        Stk.Push(WillPush);
                    }
                }
            }
        }

        if (FoundAnswer) {
            for (int I = 0; I <= AnswerKouhoLog.Count - 1; I++) {
                Console.WriteLine("レベル{0}", I);
                PrintBan(AnswerKouhoLog[I]);
            }
            return true;
        }
        return false;
    }

    //クリア判定
    static bool IsClear(char[,] pBanArr)
    {
        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                if (pBanArr[LoopX, LoopY] == '裏') return false;
            }
        }
        return true;
    }

    //ジャンプ後の盤情報
    struct JumpedInfoDef
    {
        internal char[,] BanArr;
        internal PointDef NewCurrPos;
    }

    //カメのジャンプ後の盤情報の配列を返す
    static JumpedInfoDef[] DeriveJumpedInfoArr(char[,] pBanArr, int pFromX, int pFromY)
    {
        var WillReturn = new List<JumpedInfoDef>();

        Func<int, int, bool> IsInside = (pX, pY) =>
        {
            if (pX < 0 || UB < pX) return false;
            if (pY < 0 || UB < pY) return false;
            return true;
        };

        Action<int, int> JumpAct = (pHeniX, pHeniY) =>
        {
            //1マス先のチェック
            if (IsInside(pFromX + pHeniX, pFromY + pHeniY) == false) return;
            if (pBanArr[pFromX + pHeniX, pFromY + pHeniY] == '□') return;

            //2マス先のチェック
            if (IsInside(pFromX + pHeniX * 2, pFromY + pHeniY * 2) == false) return;
            if (pBanArr[pFromX + pHeniX * 2, pFromY + pHeniY * 2] == '□') {
                char[,] wkArr = (char[,])pBanArr.Clone();

                wkArr[pFromX, pFromY] = '□';
                HantenSyori(wkArr, pFromX + pHeniX, pFromY + pHeniY);
                wkArr[pFromX + pHeniX * 2, pFromY + pHeniY * 2] = pBanArr[pFromX, pFromY];

                JumpedInfoDef WillAdd;
                WillAdd.BanArr = wkArr;
                WillAdd.NewCurrPos =
                    new PointDef() { X = pFromX + pHeniX * 2, Y = pFromY + pHeniY * 2 };
                WillReturn.Add(WillAdd);
                return;
            }

            //3マス先のチェック
            if (IsInside(pFromX + pHeniX * 3, pFromY + pHeniY * 3) == false) return;
            if (pBanArr[pFromX + pHeniX * 3, pFromY + pHeniY * 3] == '□') {
                char[,] wkArr = (char[,])pBanArr.Clone();

                wkArr[pFromX, pFromY] = '□';
                HantenSyori(wkArr, pFromX + pHeniX, pFromY + pHeniY);
                HantenSyori(wkArr, pFromX + pHeniX * 2, pFromY + pHeniY * 2);
                wkArr[pFromX + pHeniX * 3, pFromY + pHeniY * 3] = pBanArr[pFromX, pFromY];

                JumpedInfoDef WillAdd;
                WillAdd.BanArr = wkArr;
                WillAdd.NewCurrPos =
                    new PointDef() { X = pFromX + pHeniX * 3, Y = pFromY + pHeniY * 3 };
                WillReturn.Add(WillAdd);
                return;
            }
        };

        JumpAct(-1, -1); JumpAct(-1, 0); JumpAct(-1, 1);
        JumpAct(0, -1); JumpAct(0, +1);
        JumpAct(1, -1); JumpAct(1, 0); JumpAct(1, -1);

        return WillReturn.ToArray();
    }

    //指定したマスのカメを反転
    static void HantenSyori(char[,] pBanArr, int pX, int pY)
    {
        if (pBanArr[pX, pY] == '表')
            pBanArr[pX, pY] = '裏';
        else
            pBanArr[pX, pY] = '表';
    }

    struct MinTesuuInfo
    {
        internal int Tesuu;
        internal int Level;
    }

    //盤面をハッシュ値に変換
    static string GetHash(char[,] pBanArr, PointDef pCurrPos)
    {
        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]);
            }
        }

        sb.AppendFormat("{0},{1}", pCurrPos.X, pCurrPos.Y);
        return sb.ToString();
    }

    //盤面を出力
    static void PrintBan(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();
        }
        Console.WriteLine(sb.ToString());
    }
}


実行結果

手数制限=1で深さ優先探索を実行中
手数制限=2で深さ優先探索を実行中
手数制限=3で深さ優先探索を実行中
手数制限=4で深さ優先探索を実行中
4手(17レベル)の解候補を発見
4手(15レベル)の解候補を発見
4手(14レベル)の解候補を発見
4手(12レベル)の解候補を発見
4手(11レベル)の解候補を発見
4手(10レベル)の解候補を発見
レベル0
□裏裏□
裏裏裏裏
裏裏裏裏
□裏裏□

レベル1
裏表□□
裏裏裏裏
裏裏裏裏
□裏裏□

レベル2
□表□□
表裏裏裏
表裏裏裏
裏裏裏□

レベル3
□表□□
表裏裏裏
表裏裏裏
□表表裏

レベル4
裏表□□
表表裏裏
表裏表裏
□表表□

レベル5
裏表表□
表裏裏裏
□裏表裏
□表表□

レベル6
□表表□
裏裏裏裏
裏裏表裏
□表表□

レベル7
表表表□
裏表裏裏
裏裏□裏
□表表□

レベル8
□表表□
表表裏裏
表裏□裏
表表表□

レベル9
□表表表
表表表裏
表表□裏
□表表□

レベル10
□表表□
表表表表
表表□表
□表表表


解説

反復深化深さ優先探索で解いてます。