Cマガ電脳クラブ(第119回) H2O

問題

 Fig.1のように，机の上に8個のコインをH型に並べた。これをFig.2のようにO型にしたい。
まず1個のコインを選び，もち上げないで机の表面を滑らせる。
もちろんこのときほかのコインを動かしてはいけない。
そして位置がはっきりと決まる(つまり2個以上のコインと接する)ところまで移動する。
これで1手だ。完成までの最少手数とその手順をお答えいただきたい。

なお，2個と接するとはいっても，
1個ぶんの間隔をあけた2個のコインの間に差し込むという動きは，位置がうまく決まらないので不可とする。

Fig.1 H型　   　Fig.2 O型
●　　●　　　　●●●
●●●●　　　　●　●
●　　●　　　　●●●

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB_X = 4 + 2 - 1; //外周で2足す
    const int UB_Y = 3 + 2 - 1; //外周で2足す

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

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

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

    //深さ優先探索を行う
    static bool ExecDFS(int pLimitLevel)
    {
        var stk = new Stack<JyoutaiDef1>();
        JyoutaiDef1 WillPush;
        WillPush.Level = 0;
        WillPush.BanArr = new char[UB_X + 1, UB_Y + 1];
        char[,] wkP = WillPush.BanArr;
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                wkP[X, Y] = '□';
            }
        }
        wkP[1, 1] = '●'; wkP[4, 1] = '●';
        wkP[1, 2] = '●'; wkP[2, 2] = '●'; wkP[3, 2] = '●'; wkP[4, 2] = '●';
        wkP[1, 3] = '●'; wkP[4, 3] = '●';
        WillPush.Log = new List<char[,]>() { WillPush.BanArr };
        stk.Push(WillPush);

        while (stk.Count > 0) {
            JyoutaiDef1 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]);
                }
                return true;
            }

            //レベル制限
            if (pLimitLevel <= Popped.Level)
                continue;

            for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                    if (Popped.BanArr[LoopX, LoopY] != '●') continue;

                    //対称解の除外で初手は上半分のコインを移動させる
                    if (Popped.Level == 0) {
                        if (LoopY > UB_Y / 2) continue;
                    }

                    List<PointDef> CanMovePointList =
                        DeriveCanMovePointList(LoopX, LoopY, Popped.BanArr);

                    CanMovePointList.RemoveAll(A =>
                        Is2MaiRinsetu(LoopX, LoopY, A.X, A.Y, Popped.BanArr) == false);

                    foreach (PointDef EachToPoint in CanMovePointList) {
                        WillPush.Level = Popped.Level + 1;
                        WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                        WillPush.BanArr[LoopX, LoopY] = '□';
                        WillPush.BanArr[EachToPoint.X, EachToPoint.Y] = '●';
                        WillPush.Log = new List<char[,]>(Popped.Log);
                        WillPush.Log.Add(WillPush.BanArr);
                        stk.Push(WillPush);
                    }
                }
            }
        }
        return false;
    }

    //クリア判定
    static bool IsClear(char[,] pBanArr)
    {
        if (pBanArr[1, 1] != '●') return false;
        if (pBanArr[2, 1] != '●') return false;
        if (pBanArr[3, 1] != '●') return false;

        if (pBanArr[1, 2] != '●') return false;
        if (pBanArr[3, 2] != '●') return false;

        if (pBanArr[1, 3] != '●') return false;
        if (pBanArr[2, 3] != '●') return false;
        if (pBanArr[3, 3] != '●') return false;

        return true;
    }

    struct JyoutaiDef2
    {
        internal int CurrX;
        internal int CurrY;
    }

    //指定したコインが移動可能な空マスを列挙
    static List<PointDef> DeriveCanMovePointList(int pFromX, int pFromY, char[,] pBanArr)
    {
        var VisitedList = new List<PointDef>();

        var stk = new Stack<JyoutaiDef2>();
        JyoutaiDef2 WillPush;
        WillPush.CurrX = pFromX;
        WillPush.CurrY = pFromY;
        stk.Push(WillPush);

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

            Action<int, int> PushSyori = (pNewX, pNewY) =>
            {
                if (pNewX < 0 || UB_X < pNewX) return;
                if (pNewY < 0 || UB_Y < pNewY) return;

                //コインなら訪問不可
                if (pBanArr[pNewX, pNewY] == '●') return;

                //再訪不可
                if (VisitedList.Exists(A => A.X == pNewX && A.Y == pNewY)) {
                    return;
                }
                VisitedList.Add(new PointDef() { X = pNewX, Y = pNewY });

                WillPush.CurrX = pNewX;
                WillPush.CurrY = pNewY;
                stk.Push(WillPush);
            };
            PushSyori(Popped.CurrX, Popped.CurrY - 1);
            PushSyori(Popped.CurrX, Popped.CurrY + 1);
            PushSyori(Popped.CurrX - 1, Popped.CurrY);
            PushSyori(Popped.CurrX + 1, Popped.CurrY);
        }

        //外周の座標をRemove
        VisitedList.RemoveAll(A => A.X == 0 || A.X == UB_X);
        VisitedList.RemoveAll(A => A.Y == 0 || A.Y == UB_Y);

        return VisitedList;
    }

    //移動先空マスに、移動しない2個以上のコインが接しているかを判定
    static bool Is2MaiRinsetu(int pFromX, int pFromY, int pToX, int pToY, char[,] pBanArr)
    {
        Func<int, int, bool> IsOKFunc = (pX, pY) =>
            pBanArr[pX, pY] == '●' && (pX == pFromX && pY == pFromY) == false;

        bool Ue = IsOKFunc(pToX, pToY - 1);
        bool Migi = IsOKFunc(pToX + 1, pToY);
        bool Shita = IsOKFunc(pToX, pToY + 1);
        bool Hidari = IsOKFunc(pToX - 1, pToY);

        //上と右
        if (Ue && Migi) return true;
        //右と下
        if (Migi && Shita) return true;
        //下と左
        if (Shita && Hidari) return true;
        //左と上
        if (Hidari && Ue) return true;

        return false;
    }

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

実行結果

深さ制限=1で深さ優先探索を実行中
深さ制限=2で深さ優先探索を実行中
深さ制限=3で深さ優先探索を実行中
深さ制限=4で深さ優先探索を実行中
深さ制限=5で深さ優先探索を実行中
解を発見しました。
レベル0
□□□□□□
□●□□●□
□●●●●□
□●□□●□
□□□□□□

レベル1
□□□□□□
□●●□□□
□●●●●□
□●□□●□
□□□□□□

レベル2
□□□□□□
□●●●□□
□●●●●□
□●□□□□
□□□□□□

レベル3
□□□□□□
□●●●□□
□●●□●□
□●●□□□
□□□□□□

レベル4
□□□□□□
□●●●□□
□●□●●□
□●●□□□
□□□□□□

レベル5
□□□□□□
□●●●□□
□●□●□□
□●●●□□
□□□□□□

解説

外周を用意して、処理をシンプルにしてます。