16-03 Say Cheese

問題

ポピュラープレイシングスのSay Cheeseを解きます。

＜ゲームの目的＞
問題シートの指示のとおりにチーズのブロックを配置し、
しっぽしか見えなかったネズミを、限られた回数だけブロックを転がして、
すべて笑顔が上に向くようにするゲームです。

＜ゲームの準備＞
まずは問題カードを選び、そこに示されたとおりに四角いチーズのブロックを配置します。
それぞれのチーズには色の異なるネズミが隠れています。
スタート次点では、必ずネズミのしっぽが上を向いているように、置いてください。

＜ルール＞
チーズのブロックは、上下左右にだけ、また問題ごとに決められた回数（各問題の左下に書かれています）だけ、
転がして動かすことができます。ななめに進むことや、曲がることはできません。
チーズのブロックには2種類の大きさがあるので、それぞれ転がり方が異なります。

＜ブロックの動かし方＞
大きさの異なるブロックの、それぞれの転がり方は下図のとおり。
どちらも上下左右に空間が空いている場所であれば、どの方向にも転がすことができます。
また、6つの面のどこで止まってもよいです。

ソース

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

class Program
{
    const int UB = 3 - 1;

    struct JyoutaiDef
    {
        internal int MoveCnt;
        internal char[,] BanArr;

        //尾が底面なら1
        //尾が上面なら2
        //尾が右面なら3
        //尾が左面なら4
        //尾が前面なら5
        //尾が後面なら6
        internal Dictionary<char, int> SippoMukiDict;

        internal List<string> BanArrLog;
    }

    static char[,] Q00Arr = new char[,]{{'A','A',' '},
                                        {' ',' ',' '},
                                        {'C',' ',' '}};

    static char[,] Q04Arr = new char[,]{{' ','C',' '},
                                        {' ',' ',' '},
                                        {'A','A',' '}};

    static char[,] Q16Arr = new char[,]{{' ','A','A'},
                                        {'B',' ',' '},
                                        {'B',' ',' '}};

    static char[,] Q17Arr = new char[,]{{' ','C','A'},
                                        {' ','D','A'},
                                        {' ',' ',' '}};

    static char[,] Q18Arr = new char[,]{{' ','C',' '},
                                        {'D',' ','F'},
                                        {' ','E',' '}};

    static char[,] Q19Arr = new char[,]{{' ',' ',' '},
                                        {' ','C','D'},
                                        {'A','A','E'}};

    static char[,] Q20Arr = new char[,]{{'C',' ','D'},
                                        {'A',' ','E'},
                                        {'A',' ','F'}};

    static char[,] Q21Arr = new char[,]{{' ',' ','C'},
                                        {'A','A',' '},
                                        {'B','B',' '}};

    static char[,] Q22Arr = new char[,]{{'C','A','D'},
                                        {' ','A',' '},
                                        {' ',' ',' '}};

    static char[,] Q23Arr = new char[,]{{' ','C',' '},
                                        {'A','A',' '},
                                        {' ','D',' '}};

    static char[,] Q24Arr = new char[,]{{'C',' ','D'},
                                        {' ','E',' '},
                                        {'F',' ','G'}};

    static char[,] Q48Arr = new char[,]{{'C','A','A'},
                                        {' ','B',' '},
                                        {'D','B',' '}};

    static char[,] Q49Arr = new char[,]{{'C','A','A'},
                                        {'B','D',' '},
                                        {'B',' ','E'}};

    static char[,] Q50Arr = new char[,]{{'A','C','B'},
                                        {'A','D','B'},
                                        {' ','E',' '}};

    static char[,] wkArr = Q48Arr;

    static System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew();

    static void Main()
    {
        //反復深化深さ優先探索で解く
        for (int Depth = 1; Depth < int.MaxValue; Depth++) {
            Console.WriteLine("深さ制限={0}で解を検証中。経過時間={1}", Depth, sw.Elapsed);

            List<string> AnswerBanArrLog = ExecDFS(Depth);

            if (AnswerBanArrLog.Count > 0) {
                Console.WriteLine("解は");
                AnswerBanArrLog.ForEach(X => Console.WriteLine(X));
                Console.WriteLine("経過時間={0}", sw.Elapsed);
                return;
            }
        }
    }

    //深さ制限を引数として深さ優先探索を行う
    static List<string> ExecDFS(int pDepthMax)
    {
        char[,] QuestionArr = new char[UB + 1, UB + 1];

        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                QuestionArr[X, Y] = wkArr[Y, X];
            }
        }

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.MoveCnt = 0;
        WillPush.BanArr = QuestionArr;
        WillPush.SippoMukiDict = new Dictionary<char, int>();
        foreach (char AnyChar in QuestionArr.Cast<char>().Distinct()) {
            if (AnyChar != ' ') WillPush.SippoMukiDict.Add(AnyChar, 2);
        }
        WillPush.BanArrLog = new List<string>() { DeriveBanInfo(QuestionArr, WillPush.SippoMukiDict) };

        stk.Push(WillPush);

        //盤面に対する最少手数のDict
        var MinTesuuSortedDict = new SortedDictionary<ulong, int>();

        var WillReturn = new List<string>();

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

            //クリア判定
            if (Popped.SippoMukiDict.Values.All(X => X == 1)) {
                Console.WriteLine("MoveCnt={0}の解を発見。経過時間={1}", Popped.MoveCnt, sw.Elapsed);
                WillReturn = Popped.BanArrLog;
                break;
            }

            //Move処理
            foreach (char AnyChar in Popped.SippoMukiDict.Keys) {
                int FromX, FromY;
                SearchMouseXY(AnyChar, Popped.BanArr, out FromX, out FromY);

                bool Is1Masu = (AnyChar != 'A' && AnyChar != 'B');

                //当該盤面に、少ない手数か等しい手数で、到達済かを返す
                Predicate<ulong> HasAlreadyToutatu = pBanULong =>
                {
                    int MinTesuu;
                    if (MinTesuuSortedDict.TryGetValue(pBanULong, out MinTesuu)) {
                        if (MinTesuu <= WillPush.MoveCnt) return true;
                    }
                    MinTesuuSortedDict[pBanULong] = WillPush.MoveCnt;
                    return false;
                };

                //1マスのネズミの移動のPush処理と
                //2マスのネズミの移動のPush処理の共通の処理(枝切りの前)
                Action<int, int> PushSyoriCommonBeforeEdakiri = (pHeniX, pHeniY) =>
                {
                    WillPush.MoveCnt = Popped.MoveCnt + 1;

                    WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                    WillPush.BanArr[FromX, FromY] = ' ';
                    WillPush.BanArr[FromX + pHeniX, FromY + pHeniY] = AnyChar;

                    WillPush.SippoMukiDict = new Dictionary<char, int>(Popped.SippoMukiDict);
                    WillPush.SippoMukiDict[AnyChar] =
                        DeriveNewSippoMuki(WillPush.SippoMukiDict[AnyChar], pHeniX, pHeniY);
                };

                //1マスのネズミの移動のPush処理と
                //2マスのネズミの移動のPush処理の共通の処理(枝切りの後)
                Action PushSyoriCommonAfterEdakiri = () =>
                {
                    string wkLog = DeriveBanInfo(WillPush.BanArr, WillPush.SippoMukiDict);
                    WillPush.BanArrLog = new List<string>(Popped.BanArrLog) { wkLog };
                    stk.Push(WillPush);
                };

                //移動元座標と移動変位を引数にして、1マスのネズミの移動のPush処理を行う
                Action<int, int> PushSyori1Masu = (pHeniX, pHeniY) =>
                {
                    //共通の処理(枝切りの前)
                    PushSyoriCommonBeforeEdakiri(pHeniX, pHeniY);

                    //MoveCnt制限で枝切り
                    if (pDepthMax < WillPush.MoveCnt + CalcNeedMinTesuu(WillPush.SippoMukiDict))
                        return;

                    //当該盤面に、少ない手数か等しい手数で、到達済なら枝切り
                    if (HasAlreadyToutatu(BanToULong(WillPush.BanArr, WillPush.SippoMukiDict)))
                        return;

                    //共通の処理(枝切りの後)
                    PushSyoriCommonAfterEdakiri();
                };

                //1マスのネズミが上に移動
                if (Is1Masu && FromY - 1 >= 0 && Popped.BanArr[FromX, FromY - 1] == ' ') {
                    PushSyori1Masu(0, -1);
                }

                //1マスのネズミが下に移動
                if (Is1Masu && FromY + 1 <= UB && Popped.BanArr[FromX, FromY + 1] == ' ') {
                    PushSyori1Masu(0, 1);
                }

                //1マスのネズミが左に移動
                if (Is1Masu && FromX - 1 >= 0 && Popped.BanArr[FromX - 1, FromY] == ' ') {
                    PushSyori1Masu(-1, 0);
                }

                //1マスのネズミが右に移動
                if (Is1Masu && FromX + 1 <= UB && Popped.BanArr[FromX + 1, FromY] == ' ') {
                    PushSyori1Masu(1, 0);
                }

                //2マスのネズミの移動処理
                if (Is1Masu) continue;

                int XLength; //移動前のX方向の長さ
                int YLength; //移動前のY方向の長さ
                DeriveXLengthAndYLength(AnyChar, Popped.BanArr, out XLength, out YLength);

                //移動元座標と移動変位を引数にして、2マスのネズミの移動のPush処理を行う
                Action<int, int> PushSyori2Masu = (pHeniX, pHeniY) =>
                {
                    //共通の処理(枝切りの前)
                    PushSyoriCommonBeforeEdakiri(pHeniX, pHeniY);

                    if (XLength == 2 && YLength == 1) WillPush.BanArr[FromX + 1, FromY] = ' ';
                    if (XLength == 1 && YLength == 2) WillPush.BanArr[FromX, FromY + 1] = ' ';

                    if (XLength == 1 && YLength == 1) {
                        if (Math.Abs(pHeniX) > 0) { //横に移動した場合
                            WillPush.BanArr[FromX + pHeniX + 1, FromY + pHeniY] = AnyChar;
                        }
                        else { //縦に移動した場合
                            WillPush.BanArr[FromX + pHeniX, FromY + pHeniY + 1] = AnyChar;
                        }
                    }
                    if (XLength == 2 && YLength == 1) {
                        if (Math.Abs(pHeniY) > 0) { //縦に移動した場合
                            WillPush.BanArr[FromX + pHeniX + 1, FromY + pHeniY] = AnyChar;
                        }
                    }
                    if (XLength == 1 && YLength == 2) {
                        if (Math.Abs(pHeniX) > 0) { //横に移動した場合
                            WillPush.BanArr[FromX + pHeniX, FromY + pHeniY + 1] = AnyChar;
                        }
                    }

                    //MoveCnt制限で枝切り
                    if (pDepthMax < WillPush.MoveCnt + CalcNeedMinTesuu(WillPush.SippoMukiDict))
                        return;

                    //当該盤面に、少ない手数か等しい手数で、到達済なら枝切り
                    if (HasAlreadyToutatu(BanToULong(WillPush.BanArr, WillPush.SippoMukiDict)))
                        return;

                    //共通の処理(枝切りの後)
                    PushSyoriCommonAfterEdakiri();
                };

                //X方向の長さが1 Y方向の長さが1
                if (XLength == 1 && YLength == 1) {
                    //上に移動
                    if (FromY - 2 >= 0 && Popped.BanArr[FromX, FromY - 1] == ' '
                                       && Popped.BanArr[FromX, FromY - 2] == ' ') {
                        PushSyori2Masu(0, -2);
                    }
                    //下に移動
                    if (FromY + 2 <= UB && Popped.BanArr[FromX, FromY + 1] == ' '
                                        && Popped.BanArr[FromX, FromY + 2] == ' ') {
                        PushSyori2Masu(0, 1);
                    }
                    //左に移動
                    if (FromX - 2 >= 0 && Popped.BanArr[FromX - 1, FromY] == ' '
                                       && Popped.BanArr[FromX - 2, FromY] == ' ') {
                        PushSyori2Masu(-2, 0);
                    }
                    //右に移動
                    if (FromX + 2 <= UB && Popped.BanArr[FromX + 1, FromY] == ' '
                                        && Popped.BanArr[FromX + 2, FromY] == ' ') {
                        PushSyori2Masu(1, 0);
                    }
                }
                //X方向の長さが2 Y方向の長さが1
                if (XLength == 2 && YLength == 1) {
                    //上に移動
                    if (FromY - 1 >= 0 && Popped.BanArr[FromX, FromY - 1] == ' '
                                       && Popped.BanArr[FromX + 1, FromY - 1] == ' ') {
                        PushSyori2Masu(0, -1);
                    }
                    //下に移動
                    if (FromY + 1 <= UB && Popped.BanArr[FromX, FromY + 1] == ' '
                                        && Popped.BanArr[FromX + 1, FromY + 1] == ' ') {
                        PushSyori2Masu(0, 1);
                    }
                    //左に移動
                    if (FromX - 1 >= 0 && Popped.BanArr[FromX - 1, FromY] == ' ') {
                        PushSyori2Masu(-1, 0);
                    }
                    //右に移動
                    if (FromX + 2 <= UB && Popped.BanArr[FromX + 2, FromY] == ' ') {
                        PushSyori2Masu(2, 0);
                    }
                }
                //X方向の長さが1 Y方向の長さが2
                if (XLength == 1 && YLength == 2) {
                    //上に移動
                    if (FromY - 1 >= 0 && Popped.BanArr[FromX, FromY - 1] == ' ') {
                        PushSyori2Masu(0, -1);
                    }
                    //下に移動
                    if (FromY + 2 <= UB && Popped.BanArr[FromX, FromY + 2] == ' ') {
                        PushSyori2Masu(0, 2);
                    }
                    //左に移動
                    if (FromX - 1 >= 0 && Popped.BanArr[FromX - 1, FromY] == ' '
                                       && Popped.BanArr[FromX - 1, FromY + 1] == ' ') {
                        PushSyori2Masu(-1, 0);
                    }
                    //右に移動
                    if (FromX + 1 <= UB && Popped.BanArr[FromX + 1, FromY] == ' '
                                        && Popped.BanArr[FromX + 1, FromY + 1] == ' ') {
                        PushSyori2Masu(1, 0);
                    }
                }
            }
        }
        return WillReturn;
    }

    //必要な最低手数を求める
    static int CalcNeedMinTesuu(Dictionary<char, int> pSippoMukiDict)
    {
        int WillReturn = 0;
        foreach (int AnyVal in pSippoMukiDict.Values) {
            if (AnyVal == 1) continue;
            if (AnyVal == 2) WillReturn += 2;
            else WillReturn++;
        }
        return WillReturn;
    }

    //ネズミ名を引数にして、X方向の長さとY方向の長さを返す
    static void DeriveXLengthAndYLength(char pMouseName, char[,] pBanArr, out int pX, out int pY)
    {
        pX = pY = 1;

        //Y方向の長さのチェック
        for (int X = 0; X <= UB; X++) {
            int SeqCnt = 0;
            for (int Y = 0; Y <= UB; Y++) if (pBanArr[X, Y] == pMouseName) SeqCnt++;
            if (SeqCnt == 2) {
                pY = 2;
                return;
            }
        }

        //X方向の長さのチェック
        for (int Y = 0; Y <= UB; Y++) {
            int SeqCnt = 0;
            for (int X = 0; X <= UB; X++) if (pBanArr[X, Y] == pMouseName) SeqCnt++;
            if (SeqCnt == 2) {
                pX = 2;
                return;
            }
        }
    }

    //尾の向きと移動変位を引数にして、新しい尾の向きを返す
    static int DeriveNewSippoMuki(int pSippoMuki, int pHeniX, int pHeniY)
    {
        if (pHeniX == 0 && pHeniY <= -1) {
            if (pSippoMuki == 1) return 5;
            if (pSippoMuki == 2) return 6;
            if (pSippoMuki == 3) return 3;
            if (pSippoMuki == 4) return 4;
            if (pSippoMuki == 5) return 2;
            if (pSippoMuki == 6) return 1;
        }

        if (pHeniX == 0 && pHeniY >= 1) {
            if (pSippoMuki == 1) return 6;
            if (pSippoMuki == 2) return 5;
            if (pSippoMuki == 3) return 3;
            if (pSippoMuki == 4) return 4;
            if (pSippoMuki == 5) return 1;
            if (pSippoMuki == 6) return 2;
        }

        if (pHeniX <= -1 && pHeniY == 0) {
            if (pSippoMuki == 1) return 3;
            if (pSippoMuki == 2) return 4;
            if (pSippoMuki == 3) return 2;
            if (pSippoMuki == 4) return 1;
            if (pSippoMuki == 5) return 5;
            if (pSippoMuki == 6) return 6;
        }

        //if(pHeniX == 1 && pHeniY == 0){
        if (pSippoMuki == 1) return 4;
        if (pSippoMuki == 2) return 3;
        if (pSippoMuki == 3) return 1;
        if (pSippoMuki == 4) return 2;
        if (pSippoMuki == 5) return 5;
        return 6;
    }

    //ネズミが存在する座標を返す(2マスの長さの場合は左上の座標を返す)
    static void SearchMouseXY(char pMouseName, char[,] pBanArr, out int pX, out int pY)
    {
        pX = pY = -1;
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (pBanArr[X, Y] == pMouseName) {
                    pX = X; pY = Y;
                    return;
                }
            }
        }
    }

    //盤面情報を作成して返す
    static string DeriveBanInfo(char[,] pBanArr, Dictionary<char, int> pSippoMukiDict)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                char wkChar = pBanArr[X, Y];
                if (wkChar == ' ') sb.Append("**");
                else sb.AppendFormat("{0}{1}", wkChar, pSippoMukiDict[wkChar]);
                if (X < UB) sb.Append(',');
            }
            sb.AppendLine();
        }
        return sb.ToString();
    }


    //盤面を符号なしULong型で表現
    static ulong BanToULong(char[,] pBanArr, Dictionary<char, int> pSippoMukiDict)
    {
        var sb = new System.Text.StringBuilder();

        bool IsAppearedA = false;
        bool IsAppearedB = false;

        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                char wkChar = pBanArr[X, Y];
                if (wkChar == ' ') { //空白の場合
                    sb.Append('0');
                    continue;
                }
                int wkMuki = pSippoMukiDict[wkChar];

                if (wkChar == 'A') {
                    if (IsAppearedA == false) {
                        sb.AppendFormat("{0}{1}", '7', wkMuki);
                        IsAppearedA = true;
                    }
                    else sb.Append('7');
                    continue;
                }
                if (wkChar == 'B') {
                    if (IsAppearedB == false) {
                        sb.AppendFormat("{0}{1}", '8', wkMuki);
                        IsAppearedB = true;
                    }
                    else sb.Append('8');
                    continue;
                }

                //1マスのネズミの場合
                sb.Append(wkMuki);
            }
        }
        return ulong.Parse(sb.ToString());
    }
}

実行結果

深さ制限=1で解を検証中。経過時間=00:00:00.0026492
深さ制限=2で解を検証中。経過時間=00:00:00.0808058
深さ制限=3で解を検証中。経過時間=00:00:00.0813849
深さ制限=4で解を検証中。経過時間=00:00:00.0816673
深さ制限=5で解を検証中。経過時間=00:00:00.0990592
MoveCnt=5の解を発見。経過時間=00:00:00.1000710
解は
**,C2,**
**,**,**
A2,A2,**

**,**,**
**,C5,**
A2,A2,**

**,**,**
**,**,C5
A2,A2,**

**,**,**
**,**,**
A2,A2,C1

**,**,**
A6,A6,**
**,**,C1

A1,A1,**
**,**,**
**,**,C1

経過時間=00:00:00.1282006

解説

反復深化深さ優先探索と下限値枝切りを組み合わせて使って解を求めてます。