Cマガ電脳クラブ(第082回) ひとふで数環

問題

8マスに分けられた環があり、各マスに1から7までの連続した7数が配置してある (Fig.1)
まず'1'からスタートして、
1マス目に'2'があり、
その'2'から2マス目に'3'があり、
その'3'から3マス目に'4'があり・・・と続き、
最後に'7' (ここでの最大の数) から7マス目に'1'があり、スタート地点に戻る。
このルールに従うと、この8マスの環には1から8までを配置することはできなくて、1から7までが最長である。

ではここで問題。
100マスに分けられた環には、最長1からいくつまで配置できるだろうか。

Fig.1 ひとふで数環

ソース

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

class Program
{
    const int UB = 100 - 1;

    struct JyoutaiDef
    {
        internal int CurrInd;
        internal int[] BanArr;
    }

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

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrInd = 1; //対称解の除外で、固定で右方向に1移動とする
        WillPush.BanArr = new int[UB + 1];
        WillPush.BanArr[0] = 1;
        WillPush.BanArr[1] = 2;
        stk.Push(WillPush);

        int AnswerLength = 0;
        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();
            int CurrNum = Popped.BanArr[Popped.CurrInd];

            //スタート地点に戻れる場合は、解候補
            if (AnswerLength <= CurrNum) {
                List<int> MasuIndList = DeriveMasuIndList(Popped.CurrInd, CurrNum);
                if (MasuIndList.Contains(0)) {
                    AnswerLength = CurrNum;

                    var sb = new System.Text.StringBuilder();
                    sb.AppendLine();
                    sb.AppendFormat("環の長さ{0}の解候補を発見。経過時間={1}", 
                        AnswerLength, sw.Elapsed);
                    sb.AppendLine();
                    for (int I = 0; I <= Popped.BanArr.GetUpperBound(0); I++) {
                        sb.AppendFormat("{0,2} ", Popped.BanArr[I]);
                        if (I % 10 == 9 || I == Popped.BanArr.GetUpperBound(0)) sb.AppendLine();
                    }
                    Console.WriteLine(sb.ToString());
                }
            }

            int[] SpaceMasuIndArr = DeriveSpaceMasuIndArr(Popped.CurrInd, Popped.BanArr);
            foreach (int EachSpaceMasuInd in SpaceMasuIndArr) {
                WillPush.CurrInd = EachSpaceMasuInd;
                WillPush.BanArr = (int[])Popped.BanArr.Clone();
                WillPush.BanArr[EachSpaceMasuInd] = CurrNum + 1;
                stk.Push(WillPush);
            }
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    //左方向もしくは右方向の、指定マス先の空欄のIndの配列を返す
    static int[] DeriveSpaceMasuIndArr(int pCurrInd, int[] pBanArr)
    {
        var WillReturn = new List<int>();

        List<int> MasuIndList = DeriveMasuIndList(pCurrInd, pBanArr[pCurrInd]);
        foreach (int EachMasuInd in MasuIndList) {
            if (pBanArr[EachMasuInd] == 0) WillReturn.Add(EachMasuInd);
        }
        return WillReturn.ToArray();
    }

    //左方向もしくは右方向の、指定マス先のIndのListを返す
    static List<int> DeriveMasuIndList(int pCurrInd, int pMasuCnt)
    {
        var WillReturn = new List<int>();

        //左方向の指定マス先のInd
        int LeftInd = pCurrInd - pMasuCnt;
        if (LeftInd < 0) LeftInd += UB + 1;
        WillReturn.Add(LeftInd);

        //右方向の指定マス先のInd
        int RightInd = pCurrInd + pMasuCnt;
        if (RightInd > UB) RightInd -= UB + 1;
        WillReturn.Add(RightInd);

        if (LeftInd == RightInd) WillReturn.RemoveAt(1);
        return WillReturn;
    }
}

実行結果

省略
環の長さ87の解候補を発見。経過時間=00:00:10.3127403
 1  2  0  3  0  0  4 11  9  7
 5 62 60 58 40  6  8 10  0 67
69 71 28 30 32  0 56 54 52 50
48 46 44 42  0  0  0 74 76 78
80 82 84  0 25 23 21 19  0 63
65 70 68 39 37 35 33  0 85 83
81 79 77 75 73 18 20 22 24 26
57 59 61 86 41 43 45 47 49 51
53 55 17 15 13 66 64 87  0 34
36 38 72 31 29 27 12 14 16  0

経過時間=00:02:06.4052023

解説

深さ優先探索でナイーブに解いてます。