21-04 Cannibal Monsters

問題

SmartGamesのCannibal Monstersを解きます。



各モンスターは上下左右にモンスターを食べる移動(チェスのルークの駒を取る移動)のみ可です。
最後に、モンスターが1匹だけになればクリアです。

初期配置のモンスターごとに食べれるモンスターは下記のようになります。
●赤は青を食べれる
●青は緑を食べれる
●緑は赤を食べれる

モンスターAがモンスターBを食べると、
次に食べれるモンスターは、モンスターBが食べれることのできたモンスターとなります。

Q01 (Starterの01問目)
□□□□
□赤青□
□□□□
□□□□

Q02 (Juniorの01問目)
□□□□
□青赤赤
□青□□
□緑□□

Q03 (Expertの01問目)
緑赤赤青
緑□□緑
赤□□青
□□赤青

Q04 (Masterの01問目)
青□赤赤
□赤赤緑
青緑□□
緑青□□

Q05 (Masterの10問目)
□赤緑青
□緑赤青
青□赤青
緑赤□□

Q06 (Masterの11問目)
□緑赤□
赤青□緑
□□青緑
青赤赤□

Q07 (Masterの12問目)
青赤緑青
青□赤□
緑赤緑□
青□□緑

ソース

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

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

    const int UB = 3;

    //問題を定義
    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[] {"□緑赤□",
                                     "赤青□緑",
                                     "□□青緑",
                                     "青赤赤□"};
        }
        if (mQuestionNo == 7) {
            wkStrArr = new string[] {"青赤緑青",
                                     "青□赤□",
                                     "緑赤緑□",
                                     "青□□緑"};
        }

        mQuestionArr = new string[UB + 1, UB + 1];
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                char CurrChar = wkStrArr[X][Y];
                if (CurrChar == '赤') mQuestionArr[Y, X] = "RB";
                if (CurrChar == '青') mQuestionArr[Y, X] = "BG";
                if (CurrChar == '緑') mQuestionArr[Y, X] = "GR";
                if (CurrChar == '□') mQuestionArr[Y, X] = "**";
            }
        }
    }

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

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

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.BanArr = mQuestionArr;
        WillPush.Log = new List<string[,]>() { WillPush.BanArr };
        Stk.Push(WillPush);

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

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

            //クリア判定
            if (IsClear(Popped.BanArr)) {
                Console.WriteLine("解を発見");
                for (int I = 0; I <= Popped.Log.Count - 1; I++) {
                    Console.WriteLine("レベル{0}", I);
                    PrintBan(Popped.Log[I]);
                }
                break;
            }

            for (int LoopX = 0; LoopX <= UB; LoopX++) {
                for (int LoopY = 0; LoopY <= UB; LoopY++) {

                    if (Popped.BanArr[LoopX, LoopY] == "**") continue;

                    List<string[,]> MovedBanArrList =
                        DeriveMovedBanArrList(Popped.BanArr, LoopX, LoopY);

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

                        ulong CurrHash = GetHash(WillPush.BanArr);
                        if (VisitedSet.Add(CurrHash) == false)
                            continue;

                        WillPush.Log = new List<string[,]>(Popped.Log) { WillPush.BanArr };
                        Stk.Push(WillPush);
                    }
                }
            }
        }
    }

    //クリア判定
    static bool IsClear(string[,] pBanArr)
    {
        int MonsterCnt = 0;
        for (int Y = 0; Y <= UB; Y++)
            for (int X = 0; X <= UB; X++)
                if (pBanArr[X, Y] != "**")
                    MonsterCnt++;

        return MonsterCnt == 1;
    }

    //移動後の盤情報の配列を返す
    static List<string[,]> DeriveMovedBanArrList(string[,] pBanArr, int pFromX, int pFromY)
    {
        var WillReturn = new List<string[,]>();

        Func<int, int, bool> MovePiece = (pToX, pToY) =>
        {
            if (pToX < 0 || UB < pToX) return false;
            if (pToY < 0 || UB < pToY) return false;
            if (pBanArr[pToX, pToY] == "**") return false;

            //食べれる色でない場合
            if (pBanArr[pFromX, pFromY][1] != pBanArr[pToX, pToY][0])
                return true;

            //食べれる色の場合
            char[] NewMonster = new char[2];
            NewMonster[0] = pBanArr[pFromX, pFromY][0];
            NewMonster[1] = pBanArr[pToX, pToY][1];

            string[,] wkArr = (string[,])pBanArr.Clone();
            wkArr[pToX, pToY] = new string(NewMonster);
            wkArr[pFromX, pFromY] = "**";
            WillReturn.Add(wkArr);
            return true;
        };

        Action<int, int> HeniLoopAct = (pHeniX, pHeniY) =>
        {
            int CurrX = pFromX + pHeniX;
            int CurrY = pFromY + pHeniY;

            while (true) {
                if (CurrX < 0 || UB < CurrX) break;
                if (CurrY < 0 || UB < CurrY) break;
                if (MovePiece(CurrX, CurrY)) break;

                CurrX += pHeniX;
                CurrY += pHeniY;
            }
        };

        HeniLoopAct(0, -1);
        HeniLoopAct(0, 1);
        HeniLoopAct(-1, 0);
        HeniLoopAct(1, 0);

        return WillReturn;
    }

    //盤面をハッシュ値に変換
    static ulong GetHash(string[,] pBanArr)
    {
        ulong WillReturn = 0UL;

        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (pBanArr[X, Y] == "**") {
                    WillReturn *= 16;
                    continue;
                }
                foreach (char EachChar in pBanArr[X, Y]) {
                    WillReturn *= 4;
                    if (EachChar == 'R') WillReturn += 1;
                    if (EachChar == 'G') WillReturn += 2;
                    if (EachChar == 'B') WillReturn += 3;
                }
            }
        }

        //4の32乗=2の64乗なのでオーバーフローしない
        return WillReturn;
    }

    //盤面を出力
    static void PrintBan(string[,] 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]);
                if (X < UB) sb.Append(",");
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

解を発見
レベル0
**,**,**,**
**,BG,RB,RB
**,BG,**,**
**,GR,**,**

レベル1
**,**,**,**
**,RG,**,RB
**,BG,**,**
**,GR,**,**

レベル2
**,**,**,**
**,RG,**,RB
**,**,**,**
**,BR,**,**

レベル3
**,**,**,**
**,BG,**,RB
**,**,**,**
**,**,**,**

レベル4
**,**,**,**
**,RG,**,**
**,**,**,**
**,**,**,**

解説

再訪防止の深さ優先探索で解いてます。

盤面表示は
本体の色,食べれる色
という表示としてます。