Cマガ電脳クラブ(第044回) ハーフペニーパズル

問題

Fig.1のようなワクの盤を作り、10円玉1個、1円玉12個を置く。14の○は空所である。
以下のルールに従って、すべての1円玉を盤から取り去るのが目的である。
　１) コインはすべて線に沿って移動する
　２) あるコインXから見て、すぐ隣にコインYがあり、その先が空所のときは、XはYを飛び越せる
　３) どのコインも隣の空所に移動できる
　４) 隅 (2、5、10、13) の位置では、たとえば「3から2のコインを飛んで空所の6にいく」といった、
　    曲がり飛びができる (ただし、1または14の位置を含んだ曲がり飛びは不可)
　５) 飛ばれたコインは盤面から取り除かれる
　６) 1個のコインが連続して飛ぶかぎり、1手と数える
さて今回問題にするのは、「最少手数は何手か」である。

Fig.1 ハーフペニーパズル

ソース

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

class Program
{
    const int UB = 14;

    struct JyoutaiDef
    {
        internal int[] CoinArr; //添字の0は使用しない
        internal int Level;
        internal List<int[]> Log;
    }

    static void Main()
    {
        //ノード間のネットワーク図を作成
        DeriveNodeNetWork();

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

        IEnumerable<int> wkEnum = (new int[] { 0, 10 });
        wkEnum = wkEnum.Concat(Enumerable.Repeat(1, 12));
        wkEnum = wkEnum.Concat(new int[] { 0 });
        WillPush.CoinArr = wkEnum.ToArray();
        WillPush.Level = 0;
        WillPush.Log = new List<int[]>() { WillPush.CoinArr };
        Stk.Push(WillPush);

        int AnswerLevel = int.MaxValue;

        //盤面に対する最少手数のDict
        var MinTesuuDict = new Dictionary<ulong, int>();

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

            //クリア判定
            if (IsClear(Popped.CoinArr)) {
                if (Popped.Level < AnswerLevel) {
                    AnswerLevel = Popped.Level;
                    Console.WriteLine("{0}手の解候補を発見", Popped.Level);

                    for (int I = 0; I <= Popped.Log.Count - 1; I++) {
                        Console.WriteLine("手順{0}", I);
                        PrintBan(Popped.Log[I]);
                    }
                }
                continue;
            }
            //下限値枝切り
            if (AnswerLevel <= Popped.Level) continue;

            //移動後の盤面のListを返す
            List<MoveInfoDef> MovedInfoList = DeriveMovedInfoList(Popped.CoinArr);

            foreach (MoveInfoDef EachMoveInfo in MovedInfoList) {
                WillPush.CoinArr = EachMoveInfo.CoinArr;
                WillPush.Level = Popped.Level + 1;

                //メモ化探索
                int MinTesuu;
                ulong Hash = GetHash(EachMoveInfo.CoinArr);
                if (MinTesuuDict.TryGetValue(Hash, out MinTesuu)) {
                    if (MinTesuu <= WillPush.Level) continue;
                }
                MinTesuuDict[Hash] = WillPush.Level;

                WillPush.Log = new List<int[]>(Popped.Log);
                WillPush.Log.AddRange(EachMoveInfo.Log);
                Stk.Push(WillPush);
            }
        }
        Console.WriteLine("最少手数は{0}手です", AnswerLevel);
    }

    struct MoveInfoDef
    {
        internal int[] CoinArr;
        internal int FromInd;
        internal List<int[]> Log;
    }

    //移動情報のListを返す
    static List<MoveInfoDef> DeriveMovedInfoList(int[] pCoinArr)
    {
        var WillReturn = new List<MoveInfoDef>();

        var Stk = new Stack<MoveInfoDef>();
        MoveInfoDef WillPush;
        WillPush.CoinArr = pCoinArr;
        WillPush.FromInd = -1;
        WillPush.Log = new List<int[]>();
        Stk.Push(WillPush);

        var VisitedSet = new HashSet<ulong>();
        while (Stk.Count > 0) {
            MoveInfoDef Popped = Stk.Pop();

            Action<bool, int, int, int> PushSyori = (pIsSpace1, pFromPos, pJumpPos, pToPos) =>
            {
                //連続飛びの場合
                if (Popped.FromInd != -1) {
                    if (pJumpPos == 0) return;
                    if (pFromPos != Popped.FromInd && pToPos != Popped.FromInd)
                        return;
                }

                WillPush.CoinArr = (int[])Popped.CoinArr.Clone();
                WillPush.CoinArr[pFromPos] = Popped.CoinArr[pToPos];
                if (pJumpPos != 0) WillPush.CoinArr[pJumpPos] = 0;
                WillPush.CoinArr[pToPos] = Popped.CoinArr[pFromPos];

                //再訪不可
                ulong Hash = GetHash(WillPush.CoinArr);
                if (VisitedSet.Add(Hash) == false) return;

                WillPush.Log = new List<int[]>(Popped.Log);
                WillPush.Log.Add(WillPush.CoinArr);

                WillReturn.Add(WillPush);
                if (pJumpPos != 0) {
                    if (WillPush.CoinArr[pFromPos] != 0) WillPush.FromInd = pFromPos;
                    if (WillPush.CoinArr[pToPos] != 0) WillPush.FromInd = pToPos;
                    Stk.Push(WillPush);
                }
            };

            //コインの1マス移動
            foreach (NodeNetWork1 EachFromTo in NodeNetWork1Arr) {
                //片方のみ空白ならコインが移動可
                bool IsSpace1 = (Popped.CoinArr[EachFromTo.FromPos] == 0);
                bool IsSpace2 = (Popped.CoinArr[EachFromTo.ToPos] == 0);
                if (IsSpace1 && IsSpace2) continue;
                if (IsSpace1 == false && IsSpace2 == false) continue;

                PushSyori(IsSpace1, EachFromTo.FromPos, 0, EachFromTo.ToPos);
            }

            //コインの2マス移動
            foreach (NodeNetWork2 EachFromTo in NodeNetWork2Arr) {
                //間にコインがあり、もう片方のみ空白ならコインが移動可
                bool IsSpace1 = (Popped.CoinArr[EachFromTo.FromPos] == 0);
                bool IsSpace2 = (Popped.CoinArr[EachFromTo.JumpPos] == 0);
                bool IsSpace3 = (Popped.CoinArr[EachFromTo.ToPos] == 0);
                bool WillContinue = true;
                if (IsSpace1 && IsSpace2 == false && IsSpace3 == false) WillContinue = false;
                if (IsSpace1 == false && IsSpace2 == false && IsSpace3) WillContinue = false;
                if (WillContinue) continue;

                PushSyori(IsSpace1, EachFromTo.FromPos, EachFromTo.JumpPos, EachFromTo.ToPos);
            }
        }
        return WillReturn;
    }

    //移動のネットワーク図 (飛び越しなし)
    struct NodeNetWork1
    {
        internal int FromPos;
        internal int ToPos;
    }
    static NodeNetWork1[] NodeNetWork1Arr;

    //移動のネットワーク図 (飛び越しあり)
    struct NodeNetWork2
    {
        internal int FromPos;
        internal int JumpPos;
        internal int ToPos;
    }
    static NodeNetWork2[] NodeNetWork2Arr;

    //移動のネットワーク図を作成
    static void DeriveNodeNetWork()
    {
        var NodeNetWork1List = new List<NodeNetWork1>();
        //横の1マス移動
        foreach (int EachInt in new int[] { 2, 3, 4, 6, 7, 8, 10, 11, 12 })
            NodeNetWork1List.Add(new NodeNetWork1() { FromPos = EachInt, ToPos = EachInt + 1 });

        //縦の1マス移動
        foreach (int EachInt in new int[] { 2, 3, 4, 5, 6, 7, 8, 9 })
            NodeNetWork1List.Add(new NodeNetWork1() { FromPos = EachInt, ToPos = EachInt + 4 });

        NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 1, ToPos = 2 });
        NodeNetWork1List.Add(new NodeNetWork1() { FromPos = 13, ToPos = 14 });

        var NodeNetWork2List = new List<NodeNetWork2>();
        //横の2マス移動
        foreach (int EachInt in new int[] { 2, 3, 6, 7, 10, 11 })
            NodeNetWork2List.Add(
                new NodeNetWork2() { FromPos = EachInt, JumpPos = EachInt + 1, ToPos = EachInt + 2 });

        NodeNetWork1Arr = NodeNetWork1List.ToArray();

        //縦の2マス移動
        NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 1, JumpPos = 2, ToPos = 6 });
        NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 9, JumpPos = 13, ToPos = 14 });
        foreach (int EachInt in new int[] { 2, 3, 4, 5 })
            NodeNetWork2List.Add(
                new NodeNetWork2() { FromPos = EachInt, JumpPos = EachInt + 4, ToPos = EachInt + 8 });

        //斜めの移動
        NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 3, JumpPos = 2, ToPos = 6 });
        NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 4, JumpPos = 5, ToPos = 9 });
        NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 6, JumpPos = 10, ToPos = 11 });
        NodeNetWork2List.Add(new NodeNetWork2() { FromPos = 9, JumpPos = 13, ToPos = 12 });

        NodeNetWork2Arr = NodeNetWork2List.ToArray();
    }

    //クリア判定
    static bool IsClear(int[] pCoinArr)
    {
        //1円玉がなくなったらクリア
        for (int I = 1; I <= UB; I++)
            if (pCoinArr[I] == 1) return false;
        return true;
    }

    //盤面をULong型で表現
    static ulong GetHash(int[] pCoinArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int I = 1; I <= UB; I++) {
            if (pCoinArr[I] == 0) sb.Append(0);
            if (pCoinArr[I] == 1) sb.Append(1);
            if (pCoinArr[I] == 10) sb.Append(2);
        }
        return Convert.ToUInt64(sb.ToString(), 8);
    }

    //盤面を表示
    static void PrintBan(int[] pCoinArr)
    {
        var sb = new System.Text.StringBuilder();

        Func<int, char> FuncConv = pCoin =>
        {
            if (pCoin == 1) return '壱';
            if (pCoin == 10) return '十';
            return '＊';
        };

        sb.AppendFormat("{0}", FuncConv(pCoinArr[1]));
        sb.AppendLine();

        sb.AppendFormat("{0}{1}{2}{3}", FuncConv(pCoinArr[2]), FuncConv(pCoinArr[3])
            , FuncConv(pCoinArr[4]), FuncConv(pCoinArr[5]));
        sb.AppendLine();

        sb.AppendFormat("{0}{1}{2}{3}", FuncConv(pCoinArr[6]), FuncConv(pCoinArr[7])
            , FuncConv(pCoinArr[8]), FuncConv(pCoinArr[9]));
        sb.AppendLine();

        sb.AppendFormat("{0}{1}{2}{3}", FuncConv(pCoinArr[10]), FuncConv(pCoinArr[11])
            , FuncConv(pCoinArr[12]), FuncConv(pCoinArr[13]));
        sb.AppendLine();

        sb.AppendFormat("      {0}", FuncConv(pCoinArr[14]));

        Console.WriteLine(sb.ToString());
    }
}

実行結果

省略
手順12
＊
＊＊壱＊
＊壱＊＊
＊十＊＊
      ＊
手順13
＊
＊十壱＊
＊＊＊＊
＊＊＊＊
      ＊
手順14
＊
＊＊＊十
＊＊＊＊
＊＊＊＊
      ＊
最少手数は7手です

解説

盤面ごとの最少手数をメモして枝切りしつつ、深さ優先探索してます。

Cマガ電脳クラブ(第036回) 入れ換えてと同じく、
ノード間のネットワーク図を配列で作成して、移動可能なノードの判定を行ってます。