Cマガ電脳クラブ(第063回) 1本の紐

問題

4×4×4の立方体のどれかのマスを出発点にして、縦・横・高さに隣り合ったマスに移動していく。
ただし、いまいるマスは別として、すでに通ったマスと隣りあった所に移動してはいけない。
このルールだと、移動した跡は、途中で自分自身と接触しない、
1本の紐のようになる。Fig.1の例では25個のマスをたどったが、もうこれ以上進めなくなっている。

さてこの紐、最大だと何マスの長さになるだろうか。
また、回転、鏡像あるいは逆からたどって一致するものは同一とみなして、
紐の形は全部で何パターンあるだろうか。

Fig.1 「1本の紐」解答例

ソース(作成中)

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

class Program
{
    struct JyoutaiDef
    {
        internal int[, ,] BanArr;
        internal int CurrX;
        internal int CurrY;
        internal int CurrZ;
        internal int Level;
    }

    const int UB = 4 - 1;

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

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        Action<int, int, int> InitPushAct = (pX, pY, pZ) =>
        {
            WillPush.BanArr = new int[UB + 1, UB + 1, UB + 1];
            WillPush.CurrX = pX;
            WillPush.CurrY = pY;
            WillPush.CurrZ = pZ;
            WillPush.BanArr[pX, pY, pZ] = 1;
            WillPush.Level = 1;
            stk.Push(WillPush);
        };

        //回転、鏡像解の除外で
        //始点は、[0,0,0],[0,0,1],[0,1,1],[1,1,1]の4通り
        InitPushAct(0, 0, 0);
        InitPushAct(0, 0, 1);
        InitPushAct(0, 1, 1);
        InitPushAct(1, 1, 1);

        //紐の長さ別の、解の数
        var AnswerDict = new Dictionary<int, int>();

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

            bool IsPushed = false;

            //Push処理
            Action<int, int, int> PushSyori = (pNewX, pNewY, pNewZ) =>
            {
                if (pNewX < 0 || UB < pNewX) return;
                if (pNewY < 0 || UB < pNewY) return;
                if (pNewZ < 0 || UB < pNewZ) return;

                //再訪禁止
                if (Popped.BanArr[pNewX, pNewY, pNewZ] != 0) return;

                //すでに通ったマスと隣りあった所に移動してはいけない
                int[] RinsetuMasuLevelArr =
                    DeriveRinsetuMasuLevelArr(Popped.BanArr, pNewX, pNewY, pNewZ);
                if (Array.Exists(RinsetuMasuLevelArr, A => A != 0 && A < Popped.Level))
                    return;

                //★★★
                //逆からたどって一致する解の除外で、
                //始点の座標をULong化した数 < 終点の座標をULong化した数
                //★★★

                WillPush.BanArr = (int[, ,])Popped.BanArr.Clone();
                WillPush.CurrX = pNewX;
                WillPush.CurrY = pNewY;
                WillPush.CurrZ = pNewZ;
                WillPush.Level = Popped.Level + 1;
                WillPush.BanArr[pNewX, pNewY, pNewZ] = WillPush.Level;
                stk.Push(WillPush);
                IsPushed = true;
            };

            PushSyori(Popped.CurrX, Popped.CurrY, Popped.CurrZ - 1);
            PushSyori(Popped.CurrX, Popped.CurrY, Popped.CurrZ + 1);
            PushSyori(Popped.CurrX, Popped.CurrY - 1, Popped.CurrZ);
            PushSyori(Popped.CurrX, Popped.CurrY + 1, Popped.CurrZ);
            PushSyori(Popped.CurrX - 1, Popped.CurrY, Popped.CurrZ);
            PushSyori(Popped.CurrX + 1, Popped.CurrY, Popped.CurrZ);

            if (IsPushed == false) {
                int DictKey = Popped.Level;

                //if (DictKey == 7) {
                //    Console.WriteLine("紐の長さ{0}の解を発見", DictKey);
                //    PrintAnswer(Popped.BanArr);
                //    return;
                //}

                if (AnswerDict.ContainsKey(DictKey) == false)
                    AnswerDict[DictKey] = 1;
                else AnswerDict[DictKey]++;

                if (AnswerDict.Values.Sum() % 100000 == 1)
                    PrintAnswerCnt(AnswerDict);
            }
        }
        PrintAnswerCnt(AnswerDict);
    }

    //指定マスに隣接した6マスの訪問Levelの配列を返す
    static int[] DeriveRinsetuMasuLevelArr(int[, ,] pBanArr, int pX, int pY, int pZ)
    {
        var WillReturn = new List<int>();

        Action<int, int, int> AddAct = (pNewX, pNewY, pNewZ) =>
        {
            if (pNewX < 0 || UB < pNewX) return;
            if (pNewY < 0 || UB < pNewY) return;
            if (pNewZ < 0 || UB < pNewZ) return;

            WillReturn.Add(pBanArr[pNewX, pNewY, pNewZ]);
        };

        AddAct(pX, pY, pZ - 1);
        AddAct(pX, pY, pZ + 1);
        AddAct(pX, pY - 1, pZ);
        AddAct(pX, pY + 1, pZ);
        AddAct(pX - 1, pY, pZ);
        AddAct(pX + 1, pY, pZ);

        return WillReturn.ToArray();
    }

    //解を出力
    static void PrintAnswer(int[, ,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();

        for (int Z = 0; Z <= UB; Z++) {
            sb.AppendFormat("Z={0}の平面", Z);
            sb.AppendLine();
            for (int Y = 0; Y <= UB; Y++) {
                for (int X = 0; X <= UB; X++) {
                    sb.Append(pBanArr[X, Y, Z].ToString().PadLeft(2, ' ') + ",");
                }
                sb.AppendLine();
            }
        }
        Console.WriteLine(sb.ToString());
    }

    //解の総数を出力
    static void PrintAnswerCnt(Dictionary<int, int> pAnswerDict)
    {
        var sb = new System.Text.StringBuilder();

        foreach (int EachKey in pAnswerDict.Keys.OrderBy(A => A)) {
            sb.AppendFormat("紐の長さ={0}の解数={1}", EachKey, pAnswerDict[EachKey]);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
        Console.WriteLine("解の総数={0}", pAnswerDict.Values.Sum());
    }
}

実行結果

解説

メモ
解答を入手したら、続きに着手する