Cマガ電脳クラブ(第142回) 割り算の得意な金庫

問題

Fig.1のように、０〜９の数字が書かれたダイヤルが５つついた金庫がある。
この金庫、開け方がちょっと変わっている (［前提］、［操作手順］) 。
Fig.1の状態からたとえば03316→02316→12316→12315と動かすと、順に２、３、４、５で割り切れている。
しかし、次の６で割り切れる数を12315から作れないので、この場合はここでおしまい。

さて，金庫のセキュリティ上、できるだけ大きなNを設定したい。
ちゃんと金庫を開けることができる、最大のNはいくつだろうか。

［前提］
　１) 左のダイヤルから万の位/千の位/百の位/十の位/一の位の数字を表しており、
　    この5桁の数を「D数」と呼ぶ。Fig.1のD数は「03316」
　２) 除数nを考え、n=2 としてスタート

［操作手順］
　１) まず最初に、D数に偶数をセットする。当然、この数はn (=2)で割り切れる
　２) 除数nに1を足す
　３) どれか1つのダイヤルを選び、右か左に1だけ回す
　４) ３) でセットされたD数が、ｎで割り切れれば５) へ。割り切れなければ金庫は開かずに終了
　５) nがあらかじめ金庫に設定されている数Nと同じ場合、金庫が開く。n < Nなら２) へ

Fig.1　割り算の得意な金庫

　　万　　　　千　　　　百　　　　十　　　　一
　　↓　　　　↓　　　　↓　　　　↓　　　　↓
　９０１　　２３４　　２３４　　０１２　　５６７
 ８　　２　１　　５　１　　５　９　　３　４　　８
 ７　　３　０　　６　０　　６　８　　４　３　　９
　６５４　　９８７　　９８７　　７６５　　２１０

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB = 5 - 1;

    static void Main()
    {
        for (int LoopN = 2; LoopN < int.MaxValue; LoopN++) {
            Console.WriteLine("N={0}で解を調査中", LoopN);

            if (ExecDFS(LoopN) == false) {
                Console.WriteLine("N={0}での解は、ありません。", LoopN);
                break;
            }
        }
    }

    struct JyoutaiDef
    {
        internal int NumVal;
        internal int CurrJyouSuu;
        internal List<int> Log;
    }

    //Nを引数として、深さ優先探索で解を探す
    static bool ExecDFS(int pN)
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        for (int I = 0; I <= 99999; I += pN) {
            WillPush.NumVal = I;
            WillPush.CurrJyouSuu = pN;
            WillPush.Log = new List<int>() { I };
            stk.Push(WillPush);
        }

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

            //クリア判定
            if (Popped.CurrJyouSuu == 1) {
                Console.WriteLine("解を発見");
                Popped.Log.Reverse();
                for (int I = 0; I <= Popped.Log.Count - 1; I++) {
                    Console.Write(Popped.Log[I].ToString().PadLeft(5, '0'));

                    if (I == Popped.Log.Count - 1 || I % 10 == 9)
                        Console.WriteLine();
                    else
                        Console.Write(",");
                }
                return true;
            }

            Action<int, bool> PushSyori = (pTargetInd, pIsPlus) =>
            {
                List<int> NumList = DeriveNumList(Popped.NumVal);
                while (NumList.Count < 5) NumList.Add(0);

                int TargetIndNum = NumList[pTargetInd];
                if (pIsPlus) {
                    if (TargetIndNum == 9) TargetIndNum = 0;
                    else TargetIndNum++;
                }
                else {
                    if (TargetIndNum == 0) TargetIndNum = 9;
                    else TargetIndNum--;
                }
                NumList[pTargetInd] = TargetIndNum;
                WillPush.NumVal = DeriveReversedNum(NumList);

                WillPush.CurrJyouSuu = Popped.CurrJyouSuu;
                if (WillPush.NumVal % WillPush.CurrJyouSuu > 0) return;

                WillPush.Log = new List<int>(Popped.Log) { WillPush.NumVal };
                stk.Push(WillPush);
            };

            //桁のループ
            for (int I = 0; I <= UB; I++) {
                PushSyori(I, false);
                PushSyori(I, true);
            }
        }
        return false;
    }

    //数値から数字のListを求めて返す
    static List<int> DeriveNumList(int pVal)
    {
        var WillReturn = new List<int>();
        int CopiedVal = pVal;
        do {
            int ModVal = CopiedVal % 10;
            WillReturn.Add(ModVal);
            CopiedVal /= 10;
        } while (CopiedVal > 0);
        return WillReturn;
    }

    //数字を右から順に見た、数値を返す
    static int DeriveReversedNum(List<int> pNumList)
    {
        pNumList.Reverse();

        int ReversedNum = 0;
        foreach (int EachNum in pNumList) {
            ReversedNum *= 10;
            ReversedNum += EachNum;
        }
        return ReversedNum;
    }
}

実行結果

省略
N=32で解を調査中
解を発見
14320,04320,05320,95320,85320,75320,76320,76329,76320,76329
76320,76310,76300,76200,77200,78200,78210,68210,68200,67200
68200,78200,79200,69200,69290,69390,69300,69310,69210,59210
59200
N=33で解を調査中
N=33での解は、ありません。

解説

反復深化深さ優先探索チックに解いてます。