Q55 横着なそろばん

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal int SumVal;
        internal int SumMoveCnt;
        internal List<int> UsedNumList;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.SumVal = 0;
        WillPush.SumMoveCnt = 0;
        WillPush.UsedNumList = new List<int>();
        stk.Push(WillPush);

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

            //クリア判定
            if (Popped.UsedNumList.Count == 10) {
                if (AnswerMoveCnt > Popped.SumMoveCnt) {
                    AnswerMoveCnt = Popped.SumMoveCnt;
                    Console.WriteLine("玉の移動回数={0}の解候補を発見", AnswerMoveCnt);
                    Popped.UsedNumList.ForEach(X => Console.Write("{0},", X));
                    Console.WriteLine();
                }
                continue;
            }

            //下限値枝切り
            if (AnswerMoveCnt <= Popped.SumMoveCnt + 1) continue;

            for (int I = 1; I <= 10; I++) {
                if (Popped.UsedNumList.Contains(I)) continue;

                WillPush.SumVal = Popped.SumVal + I;
                int CurrMoveCnt = DeriveMoveCnt(Popped.SumVal, WillPush.SumVal);
                WillPush.SumMoveCnt = Popped.SumMoveCnt + CurrMoveCnt;

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

    //加算前と加算後での移動する玉数を返す
    static int DeriveMoveCnt(int pFrom, int pTo)
    {
        int Tama1From, Tama2From, Tama3From, Tama4From;
        DeriveTamaCmt(pFrom, out Tama1From, out Tama2From, out Tama3From, out Tama4From);
        int Tama1To, Tama2To, Tama3To, Tama4To;
        DeriveTamaCmt(pTo, out Tama1To, out Tama2To, out Tama3To, out Tama4To);

        return Math.Abs(Tama1From - Tama1To) + Math.Abs(Tama2From - Tama2To)
             + Math.Abs(Tama3From - Tama3To) + Math.Abs(Tama4From - Tama4To);
    }

    //数値を引数として、各玉の数を返す
    static void DeriveTamaCmt(int pVal, out int pTama1, out int pTama2, out int pTama3, out int pTama4)
    {
        pTama1 = (pVal >= 50) ? 1 : 0;
        pTama2 = (pVal / 10) % 5;
        pTama3 = (pVal % 10 >= 5) ? 1 : 0;
        pTama4 = (pVal % 10) % 5;
    }
}

実行結果

玉の移動回数=38の解候補を発見
10,9,8,7,6,5,4,3,2,1,
玉の移動回数=36の解候補を発見
10,9,8,7,6,5,4,3,1,2,
玉の移動回数=34の解候補を発見
10,9,8,7,6,5,3,4,1,2,
玉の移動回数=32の解候補を発見
10,9,8,7,6,5,2,4,1,3,
玉の移動回数=30の解候補を発見
10,9,8,6,7,5,2,4,1,3,
玉の移動回数=28の解候補を発見
10,8,9,6,7,5,2,4,1,3,
玉の移動回数=26の解候補を発見
10,7,9,6,8,5,2,4,1,3,

解説

深さ優先探索で下限値枝切りを使ってます。