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

13-02 ザ・太陽

問題

芦ヶ原伸之さんのザ・太陽を解きます。

開始


ゴール


ソース

using System;
using System.Collections.Generic;

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

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

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

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

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

    static bool ExecDFS(int pLevelLimit)
    {
        string[] InitArr ={"172",
                           "345",
                           "6*8",
                           "9AB"};

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanArr = new char[UB_X + 1, UB_Y + 1];
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; 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);
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            if (IsClear(Popped.BanArr)) {
                Console.WriteLine("解を発見");
                Console.WriteLine("Level={0}", Popped.Level);
                for (int I = 0; I <= Popped.Log.Count - 1; I++) {
                    Console.WriteLine("{0}手目", I);
                    Console.WriteLine(Popped.Log[I]);
                }
                return true;
            }
            if (Popped.Level + DeriveNeedMinTesuu(Popped.BanArr) > pLevelLimit) continue;

            //空白マスの座標を求める
            int SpaceX, SpaceY;
            DeriveSpaceMasu(Popped.BanArr, out SpaceX, out SpaceY);

            //空白マスの4近傍の座標のListを求める
            PointDef[] KinbouArr = DeriveKinbouArr(SpaceX, SpaceY);

            //Push処理を行う
            foreach (PointDef EachKinbou in KinbouArr) {
                WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                WillPush.BanArr[SpaceX, SpaceY] = Popped.BanArr[EachKinbou.X, EachKinbou.Y];
                WillPush.BanArr[EachKinbou.X, EachKinbou.Y] = '*';

                WillPush.Level = Popped.Level + 1;
                WillPush.Log = new List<string>(Popped.Log);
                WillPush.Log.Add(BanToStr(WillPush.BanArr));

                int MinTesuu;
                string wkHash = GetHash(WillPush.BanArr);
                if (MinTesuuDict.TryGetValue(wkHash, out MinTesuu)) {
                    if (MinTesuu <= WillPush.Level) continue;
                }
                MinTesuuDict[wkHash] = WillPush.Level;
                Stk.Push(WillPush);
            }
        }
        return false;
    }

    //最小の残り手数を返す(下限値枝切り用)
    static int DeriveNeedMinTesuu(char[,] pBanArr)
    {
        int SumKyori = 0;
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                if (pBanArr[X, Y] == '1') SumKyori += DeriveKyori(X, Y, 0, 0);
                if (pBanArr[X, Y] == '2') SumKyori += DeriveKyori(X, Y, 2, 0);
                if (pBanArr[X, Y] == '3') SumKyori += DeriveKyori(X, Y, 0, 1);
                if (pBanArr[X, Y] == '4') SumKyori += DeriveKyori(X, Y, 1, 1);
                if (pBanArr[X, Y] == '5' || pBanArr[X, Y] == '9') {
                    int Kyori1 = DeriveKyori(X, Y, 2, 1);
                    int Kyori2 = DeriveKyori(X, Y, 0, 3);
                    SumKyori += Math.Min(Kyori1, Kyori2);
                }
                if (pBanArr[X, Y] == '6') SumKyori += DeriveKyori(X, Y, 0, 2);
                if (pBanArr[X, Y] == '7') SumKyori += DeriveKyori(X, Y, 1, 2);
                if (pBanArr[X, Y] == '8') SumKyori += DeriveKyori(X, Y, 2, 2);
                if (pBanArr[X, Y] == 'A') SumKyori += DeriveKyori(X, Y, 1, 3);
                if (pBanArr[X, Y] == 'B') SumKyori += DeriveKyori(X, Y, 2, 3);
            }
        }
        return SumKyori;
    }

    //2つの座標のマンハッタン距離を求める
    static int DeriveKyori(int pX1, int pY1, int pX2, int pY2)
    {
        return Math.Abs(pX1 - pX2) + Math.Abs(pY1 - pY2);
    }

    //クリア判定
    static bool IsClear(char[,] pBanArr)
    {
        string[] GoalArr1 ={"1*2",
                            "345",
                            "678",
                            "9AB"};

        string[] GoalArr2 ={"1*2",
                            "349",
                            "678",
                            "5AB"};

        bool IsGoal1 = true, IsGoal2 = true;

        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                if (pBanArr[X, Y] != GoalArr1[Y][X]) IsGoal1 = false;
                if (pBanArr[X, Y] != GoalArr2[Y][X]) IsGoal2 = false;
            }
        }
        return IsGoal1 || IsGoal2;
    }

    //空白マスの座標を求める
    static void DeriveSpaceMasu(char[,] pBanArr, out int pX, out int pY)
    {
        pX = pY = -1;
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (pBanArr[LoopX, LoopY] == '*') {
                    pX = LoopX; pY = LoopY;
                    return;
                }
            }
        }
    }

    //4近傍の座標の配列を求める
    static PointDef[] DeriveKinbouArr(int pBaseX, int pBaseY)
    {
        var WillReturn = new List<PointDef>();
        Action<int, int> wkAct = (pX, pY) =>
        {
            if (pX < 0 || UB_X < pX) return;
            if (pY < 0 || UB_Y < pY) return;

            WillReturn.Add(new PointDef() { X = pX, Y = pY });
        };
        wkAct(pBaseX, pBaseY - 1);
        wkAct(pBaseX, pBaseY + 1);
        wkAct(pBaseX - 1, pBaseY);
        wkAct(pBaseX + 1, pBaseY);

        return WillReturn.ToArray();
    }

    //ハッシュ値を求める
    static string GetHash(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; 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; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        return sb.ToString();
    }
}


実行結果

省略
深さ制限=28で解を検証中。経過時間=00:00:02.0655172
解を発見
Level=28
0手目
172
345
6*8
9AB

1手目
172
345
*68
9AB

2手目
172
345
968
*AB

3手目
172
345
968
A*B

4手目
172
345
9*8
A6B

5手目
172
3*5
948
A6B

6手目
1*2
375
948
A6B

7手目
*12
375
948
A6B

8手目
312
*75
948
A6B

9手目
312
975
*48
A6B

10手目
312
975
4*8
A6B

11手目
312
9*5
478
A6B

12手目
312
95*
478
A6B

13手目
312
958
47*
A6B

14手目
312
958
4*7
A6B

15手目
312
9*8
457
A6B

16手目
312
*98
457
A6B

17手目
312
498
*57
A6B

18手目
312
498
5*7
A6B

19手目
312
498
567
A*B

20手目
312
498
567
*AB

21手目
312
498
*67
5AB

22手目
312
498
6*7
5AB

23手目
312
498
67*
5AB

24手目
312
49*
678
5AB

25手目
312
4*9
678
5AB

26手目
312
*49
678
5AB

27手目
*12
349
678
5AB

28手目
1*2
349
678
5AB


解説

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

パズルトピア - [ザ・太陽] 紹介