Cマガ電脳クラブ(第099回) スライドパズル9

問題

Fig.1のように、1〜9の数字が書かれた9枚の正方形のタイルが3×3の正方形に並べられている。
この3×3の正方形の周囲の12か所 (Fig.1の矢印) のうちひとつを選んでタイル1枚ぶん押してずらし、
このときとび出したタイルを、押されてタイルがなくなった位置に移動して3×3の正方形に戻す。

Fig.2にFig.1の矢印cを選んだ場合の動かし方を示す。
この操作を「1手」と数えることにすると、
たとえばFig.1のパターンから初めてFig.3のパターンを完成するには、2手 (矢印c、矢印k) 必要となる。
ここでいう「完成するまでの手数」は「完成するのに必要な最短の手数」を指す。

Fig.1のパターンはFig.3のパターンを完成するのに2手かかっているが、
では、もっとも手数がかかるのはどんなパターンだろうか。
また、それは何手かかり、そのとき何通りのパターンがあるかを答えていただきたい。

          

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB = 3 - 1;

    struct JyoutaiDef
    {
        internal int Level;
        internal int[,] BanArr;
    }

    static void Main()
    {
        var que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.Level = 0;
        WillEnqueue.BanArr = new int[UB + 1, UB + 1];
        Action<int, int, int> SetAct = (pX, pY, pSetVal) =>
            WillEnqueue.BanArr[pX, pY] = pSetVal;
        SetAct(0, 0, 1); SetAct(1, 0, 2); SetAct(2, 0, 3);
        SetAct(0, 1, 4); SetAct(1, 1, 5); SetAct(2, 1, 6);
        SetAct(0, 2, 7); SetAct(1, 2, 8); SetAct(2, 2, 9);
        que.Enqueue(WillEnqueue);

        //訪問済の盤面のHashSet
        var VisitedBan = new HashSet<int>();
        VisitedBan.Add(BanToInt(WillEnqueue.BanArr));

        int AnswerLevel = int.MinValue;
        var AnswerBanArrList = new List<int[,]>();

        while (que.Count > 0) {
            JyoutaiDef Dequeued = que.Dequeue();

            if (AnswerLevel < Dequeued.Level) {
                AnswerLevel = Dequeued.Level;
                AnswerBanArrList.Clear();
            }
            if (AnswerLevel == Dequeued.Level) {
                AnswerBanArrList.Add(Dequeued.BanArr);
            }

            WillEnqueue.Level = Dequeued.Level + 1;
            for (char I = 'a'; I <= 'l'; I++) {
                int[,] ChangedBan = DeriveChangedBan(I, Dequeued.BanArr);

                //訪問済なら枝切り
                if (VisitedBan.Add(BanToInt(ChangedBan)) == false)
                    continue;

                WillEnqueue.BanArr = ChangedBan;
                que.Enqueue(WillEnqueue);
            }
        }
        //最長手数な盤面を1つ表示する
        Console.WriteLine("最長手数は{0}手で、{1}通り", AnswerLevel, AnswerBanArrList.Count);
        Console.WriteLine();

        for (int I = 0; I <= 3; I++) {
            Console.WriteLine("解{0}は、",I+1);
            PrintBan(AnswerBanArrList[I]);
        }
    }

    //選んだ矢印を引数とし、動かした後の盤面を返す
    static int[,] DeriveChangedBan(char pArrow, int[,] pBanArr)
    {
        int[,] ChangedBan = (int[,])pBanArr.Clone();

        if (pArrow == 'a' || pArrow == 'b' || pArrow == 'c') {
            int X = 0;
            if (pArrow == 'a') X = 0;
            if (pArrow == 'b') X = 1;
            if (pArrow == 'c') X = 2;
            ChangedBan[X, 0] = pBanArr[X, 2];
            ChangedBan[X, 1] = pBanArr[X, 0];
            ChangedBan[X, 2] = pBanArr[X, 1];
        }
        if (pArrow == 'd' || pArrow == 'e' || pArrow == 'f') {
            int Y = 0;
            if (pArrow == 'd') Y = 0;
            if (pArrow == 'e') Y = 1;
            if (pArrow == 'f') Y = 2;
            ChangedBan[0, Y] = pBanArr[1, Y];
            ChangedBan[1, Y] = pBanArr[2, Y];
            ChangedBan[2, Y] = pBanArr[0, Y];
        }
        if (pArrow == 'g' || pArrow == 'h' || pArrow == 'i') {
            int X = 0;
            if (pArrow == 'g') X = 2;
            if (pArrow == 'h') X = 1;
            if (pArrow == 'i') X = 0;
            ChangedBan[X, 0] = pBanArr[X, 1];
            ChangedBan[X, 1] = pBanArr[X, 2];
            ChangedBan[X, 2] = pBanArr[X, 0];
        }
        if (pArrow == 'j' || pArrow == 'k' || pArrow == 'l') {
            int Y = 0;
            if (pArrow == 'j') Y = 2;
            if (pArrow == 'k') Y = 1;
            if (pArrow == 'l') Y = 0;
            ChangedBan[0, Y] = pBanArr[2, Y];
            ChangedBan[1, Y] = pBanArr[0, Y];
            ChangedBan[2, Y] = pBanArr[1, Y];
        }
        return ChangedBan;
    }

    //盤面をInt型に変換
    static int BanToInt(int[,] pBanArr)
    {
        int WillReturn = 0;
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                WillReturn *= 10;
                WillReturn += pBanArr[X, Y];
            }
        }
        return WillReturn;
    }

    //盤面を出力
    static void PrintBan(int[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
            for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

最長手数は8手で、2475通り

解1は、
845
936
712

解2は、
943
278
561

解3は、
294
817
635

解4は、
942
817
635

解説

ゴールから逆方向に、幅優先探索してます。