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

Cマガ電脳クラブ(第158回) カーペンターズ・パズル

問題

Fig.1-(a)のように,6×4のマスに9個のコインが置いてある。
これをスタートとして,Fig.1-(b)のようにグレーの部分にコインをすべて移したい。
どのコインも,次の2種類の移動が可能である。
 1) 縦,横,斜め方向の隣のマスが空いていれば1マス進む
 2) 縦,横,斜め方向の隣のマスにコインがあって,その先のマスが空いていれば1つ飛び越す

1つのコインがこのどちらかの移動を1回行うと「1手」と数えるとすると,最低何手で移せるだろうか。
当然,1マスに2個以上のコインは入れない。
また,コインに区別はないので,スタート時とゴール時において,9個のコイン同士の位置関係が同じである必要はない
(たとえば,スタート時の中央のコインが,ゴール時にも中央にある必要はない)。

Fig.1 カーペンターズ・パズル
  (a) スタートの配置    (b) ゴールの配置
    ●●●□□□       □□□●●●
    ●●●□□□       □□□●●●
    ●●●□□□       □□□●●●
    □□□□□□       □□□□□□


ソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB_X = 6 - 1;
    const int UB_Y = 4 - 1;

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

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

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

    //深さ制限を引数として、深さ優先探索
    static bool ExecDFS(int pLimitLevel)
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanArr = new bool[UB_X + 1, UB_Y + 1];
        for (int X = 0; X <= 2; X++) {
            for (int Y = 0; Y <= 2; Y++) {
                WillPush.BanArr[X, Y] = true;
            }
        }
        WillPush.Level = 0;
        WillPush.Log = new List<string>();
        WillPush.Log.Add(BanToStr(WillPush.BanArr));
        Stk.Push(WillPush);

        var MinTesuuDict = new Dictionary<uint, int>();
        MinTesuuDict.Add(GetHash(WillPush.BanArr), 0);

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

            //クリア判定
            if (IsClear(Popped.BanArr)) {
                Console.WriteLine("{0}手の解を発見", pLimitLevel);
                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) > pLimitLevel) continue;

            for (int X = 0; X <= UB_X; X++) {
                for (int Y = 0; Y <= UB_Y; Y++) {
                    if (Popped.BanArr[X, Y] == false) continue;

                    //開始座標を引数として、移動可能な座標のListを返す
                    List<Point> MovePosList = DeriveMovePosList(X, Y, Popped.BanArr);

                    foreach (Point EachMovePos in MovePosList) {
                        WillPush.BanArr = (bool[,])(Popped.BanArr).Clone();
                        WillPush.BanArr[EachMovePos.X, EachMovePos.Y] = true;
                        WillPush.BanArr[X, Y] = false;
                        WillPush.Level = Popped.Level + 1;

                        //メモ化探索
                        uint wkHash = GetHash(WillPush.BanArr);
                        int MinTesuu;
                        if (MinTesuuDict.TryGetValue(wkHash, out MinTesuu)) {
                            if (MinTesuu <= WillPush.Level) continue;
                        }
                        MinTesuuDict[wkHash] = WillPush.Level;

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

                        Stk.Push(WillPush);
                    }
                }
            }
        }
        return false;
    }

    //クリア判定
    static bool IsClear(bool[,] pBanArr)
    {
        for (int X = 3; X <= 5; X++) {
            for (int Y = 0; Y <= 2; Y++) {
                if (pBanArr[X, Y] == false) return false;
            }
        }
        return true;
    }

    //最小の残り手数を返す(下限値枝切り用)
    static int DeriveNeedMinTesuu(bool[,] pBanArr)
    {
        int WillReturn = 0;
        if (pBanArr[5, 0] == false) {
            WillReturn += 2;
        }
        if (pBanArr[5, 1] == false) {
            if (pBanArr[4, 2] && pBanArr[3, 3]) WillReturn++;
            else if (pBanArr[5, 2] && pBanArr[5, 3]) WillReturn++;
            else WillReturn += 2;
        }
        if (pBanArr[5, 2] == false) {
            if (pBanArr[4, 3]) WillReturn++;
            else if (pBanArr[5, 3]) WillReturn++;
            else WillReturn += 2;
        }
        if (pBanArr[4, 0] == false) {
            if (pBanArr[3, 0] && pBanArr[2, 0]) WillReturn++;
            else if (pBanArr[3, 1] && pBanArr[2, 2]) WillReturn++;
            else WillReturn += 2;
        }
        if (pBanArr[4, 1] == false) {
            if (pBanArr[3, 1] && pBanArr[2, 1]) WillReturn++;
            else if (pBanArr[3, 2] && pBanArr[2, 3]) WillReturn++;
            else if (pBanArr[4, 2] && pBanArr[4, 3]) WillReturn++;
            else WillReturn += 2;
        }
        if (pBanArr[4, 2] == false) {
            if (pBanArr[3, 1] && pBanArr[2, 0]) WillReturn++;
            else if (pBanArr[3, 2] && pBanArr[2, 2]) WillReturn++;
            else if (pBanArr[3, 3]) WillReturn++;
            else if (pBanArr[4, 3]) WillReturn++;
            else if (pBanArr[5, 3]) WillReturn++;
            else WillReturn += 2;
        }
        if (pBanArr[3, 0] == false) {
            if (pBanArr[2, 0]) WillReturn++;
            else if (pBanArr[2, 1]) WillReturn++;
            else WillReturn += 2;
        }
        if (pBanArr[3, 1] == false) {
            if (pBanArr[2, 0]) WillReturn++;
            else if (pBanArr[2, 1]) WillReturn++;
            else if (pBanArr[2, 2]) WillReturn++;
            else WillReturn += 2;
        }
        if (pBanArr[3, 2] == false) {
            if (pBanArr[2, 1]) WillReturn++;
            else if (pBanArr[2, 2]) WillReturn++;
            else if (pBanArr[2, 3]) WillReturn++;
            else if (pBanArr[3, 3]) WillReturn++;
            else if (pBanArr[4, 3]) WillReturn++;
            else WillReturn += 2;
        }

        return WillReturn;
    }

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

    //開始座標を引数として、移動可能な座標のListを返す
    static List<Point> DeriveMovePosList(int pFromX, int pFromY, bool[,] pBanArr)
    {
        var WillReturn = new List<Point>();

        Action<int, int, bool> wkAct = (pToX, pToY, pIsJump) =>
        {
            if (pToX < 0 || UB_X < pToX) return;
            if (pToY < 0 || UB_Y < pToY) return;

            //中点がコインの必要あり
            if (pIsJump) {
                if (pBanArr[(pFromX + pToX) / 2, (pFromY + pToY) / 2] == false)
                    return;
            }

            if (pBanArr[pToX, pToY] == false)
                WillReturn.Add(new Point() { X = pToX, Y = pToY });
        };

        wkAct(pFromX - 2, pFromY - 2, true);
        wkAct(pFromX + 0, pFromY - 2, true);
        wkAct(pFromX + 2, pFromY - 2, true);

        wkAct(pFromX - 1, pFromY - 1, false);
        wkAct(pFromX + 0, pFromY - 1, false);
        wkAct(pFromX + 1, pFromY - 1, false);

        wkAct(pFromX - 2, pFromY, true);
        wkAct(pFromX - 1, pFromY, false);
        wkAct(pFromX + 1, pFromY, false);
        wkAct(pFromX + 2, pFromY, true);

        wkAct(pFromX - 1, pFromY + 1, false);
        wkAct(pFromX + 0, pFromY + 1, false);
        wkAct(pFromX + 1, pFromY + 1, false);

        wkAct(pFromX - 2, pFromY + 2, true);
        wkAct(pFromX + 0, pFromY + 2, true);
        wkAct(pFromX + 2, pFromY + 2, true);

        return WillReturn;
    }

    //盤面をハッシュ値に変換
    static uint GetHash(bool[,] 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] ? 1 : 0);
            }
        }
        return Convert.ToUInt32(sb.ToString(), 2);
    }

    //盤面をString型で表現
    static string BanToStr(bool[,] 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();
    }
}


実行結果

省略
レベル制限=15で深さ優先探索中。経過時間=00:00:00.0166395
15手の解を発見
0手目
●●●□□□
●●●□□□
●●●□□□
□□□□□□

1手目
●●●□□□
●●●□□□
●●□□□□
□□□●□□

2手目
●●●□□□
●●□□□□
●●□●□□
□□□●□□

3手目
●□●●□□
●●□□□□
●●□●□□
□□□●□□

4手目
●□□●●□
●●□□□□
●●□●□□
□□□●□□

5手目
●□□●●□
●●□□□□
□●●●□□
□□□●□□

6手目
●□□●●□
●●□□□□
□●□●●□
□□□●□□

7手目
●□□●●□
●●□□□●
□●□●●□
□□□□□□

8手目
●□□●●□
□●●□□●
□●□●●□
□□□□□□

9手目
●□□●●□
□●●□□●
□●□□●●
□□□□□□

10手目
●□□□●●
□●●□□●
□●□□●●
□□□□□□

11手目
●□□●●●
□●●□□●
□□□□●●
□□□□□□

12手目
●□□●●●
□□●●□●
□□□□●●
□□□□□□

13手目
□●□●●●
□□●●□●
□□□□●●
□□□□□□

14手目
□□□●●●
□□●●□●
□□□●●●
□□□□□□

15手目
□□□●●●
□□□●●●
□□□●●●
□□□□□□

経過時間=00:00:13.0468715


解説

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