トップページに戻る    次のC#のサンプルへ    前のC#のサンプルへ

Cマガ電脳クラブ(第125回) REV STAR

問題

Fig.1のように、星型が描かれた盤がある。
その頂点と交点には黒丸が描かれており、
この10か所の黒丸のうち、9か所に10円玉を表向きにして置く (Fig.2) 。
これをスタートとして、以下のルールで10円玉を移動していく。

 1) 1か所空いた場所 (黒丸) に移動できる10円玉は、ほかの1枚あるいは2枚の10円玉を跳び越してくるもののみ
 2) 跳び越しは線に沿って直線状に行われ、曲がり跳びは許されない
 3) 跳び越された10円玉は裏返される (表向きだったものは裏向きに、裏向きだったものは表向きになる) 。
     跳び越した10円玉の向きはそのまま。
 
さて、上記の操作を繰り返してすべての10円玉を裏向きにするには、
1回の10円玉の移動を1手と数えるとすると、最低何手必要だろうか。
もちろん、10円玉は黒丸以外の場所に移動できないし、1か所に2枚以上重ねることもできない。

          


ソース

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

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

        //ジャンプ情報の配列を作成
        DeriveJumpInfoArr();

        //反復深化深さ優先探索で解く
        for (int I = 2; I < int.MaxValue; I++) {
            Console.WriteLine("レベル制限={0}で深さ優先探索中。経過時間={1}", I, sw.Elapsed);
            if (ExecDFS(I)) break;
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    //ジャンプ情報
    struct JumpInfoDef
    {
        internal char SpacePos;
        internal char FromPos;
        internal char[] JumpedPosArr;
    }
    static JumpInfoDef[] JumpInfoArr;

    //ジャンプ情報の配列を作成
    static void DeriveJumpInfoArr()
    {
        var JumpInfoList = new List<JumpInfoDef>();
        Action<char, char, char[]> AddAct = (pSpacePos, pFromPos, pJumpedPosArr) =>
        {
            JumpInfoDef WillAdd;
            WillAdd.SpacePos = pSpacePos;
            WillAdd.FromPos = pFromPos;
            WillAdd.JumpedPosArr = pJumpedPosArr;
            JumpInfoList.Add(WillAdd);
        };
        AddAct('A', 'F', new char[] { 'C' });
        AddAct('A', 'G', new char[] { 'D' });
        AddAct('A', 'I', new char[] { 'F', 'C' });
        AddAct('A', 'J', new char[] { 'G', 'D' });
        AddAct('B', 'D', new char[] { 'C' });
        AddAct('B', 'E', new char[] { 'D', 'C' });
        AddAct('B', 'H', new char[] { 'F' });
        AddAct('B', 'J', new char[] { 'H', 'F' });
        AddAct('C', 'E', new char[] { 'D' });
        AddAct('C', 'I', new char[] { 'F' });
        AddAct('D', 'B', new char[] { 'C' });
        AddAct('D', 'J', new char[] { 'G' });
        AddAct('E', 'B', new char[] { 'C', 'D' });
        AddAct('E', 'C', new char[] { 'D' });
        AddAct('E', 'H', new char[] { 'G' });
        AddAct('E', 'I', new char[] { 'H', 'G' });
        AddAct('F', 'A', new char[] { 'C' });
        AddAct('F', 'J', new char[] { 'H' });
        AddAct('G', 'A', new char[] { 'D' });
        AddAct('G', 'I', new char[] { 'H' });
        AddAct('H', 'B', new char[] { 'F' });
        AddAct('H', 'E', new char[] { 'G' });
        AddAct('I', 'A', new char[] { 'C', 'F' });
        AddAct('I', 'C', new char[] { 'F' });
        AddAct('I', 'E', new char[] { 'G', 'H' });
        AddAct('I', 'G', new char[] { 'H' });
        AddAct('J', 'A', new char[] { 'D', 'G' });
        AddAct('J', 'B', new char[] { 'H', 'F' });
        AddAct('J', 'D', new char[] { 'G' });
        AddAct('J', 'F', new char[] { 'H' });
        JumpInfoArr = JumpInfoList.ToArray();
    }

    struct JyoutaiDef
    {
        internal Dictionary<char, char> BanDict;
        internal int Level;
        internal List<string> Log;
    }

    //深さ制限を引数として、深さ優先探索する
    static bool ExecDFS(int pLimitLevel)
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;

        Action<char> wkAct = pChar =>
        {
            WillPush.BanDict = new Dictionary<char, char>();
            for (char I = 'A'; I <= 'J'; I++) {
                WillPush.BanDict.Add(I, I == pChar ? '空' : '○');
            }
            WillPush.Log = new List<string>();
            WillPush.Log.Add(BanToStr(WillPush.BanDict));
            stk.Push(WillPush);
        };
        //対称解の排除で、初期盤面の空白は、AかC
        wkAct('A'); wkAct('C');

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

            //クリア判定
            if (Popped.BanDict.Values.Any(X => X == '○') == false) {
                Console.WriteLine("{0}手の解を発見", pLimitLevel);
                for (int I = 0; I <= Popped.Log.Count - 1; I++) {
                    Console.WriteLine("■■■■■{0}手目■■■■■", I);
                    Console.WriteLine(Popped.Log[I]);
                }
                return true;
            }

            //下限値枝切り
            if (Popped.Level + DeriveNeedMinTesuu(Popped.BanDict) > pLimitLevel)
                continue;

            char wkSpacePos =
                Popped.BanDict.Keys.First(X => Popped.BanDict[X] == '空');

            foreach (JumpInfoDef EachJumpInfo in JumpInfoArr) {
                if (EachJumpInfo.SpacePos != wkSpacePos) continue;

                //対称解の除外
                if (wkSpacePos == 'A' && Popped.Level == 0) {
                    if (EachJumpInfo.FromPos == 'G') continue;
                    if (EachJumpInfo.FromPos == 'J') continue;
                }
                if (wkSpacePos == 'C' && Popped.Level == 0) {
                    if (EachJumpInfo.FromPos == 'I') continue;
                }

                WillPush.BanDict = new Dictionary<char, char>(Popped.BanDict);
                WillPush.BanDict[wkSpacePos] = WillPush.BanDict[EachJumpInfo.FromPos];
                WillPush.BanDict[EachJumpInfo.FromPos] = '空';
                Array.ForEach(EachJumpInfo.JumpedPosArr, A =>
                    WillPush.BanDict[A] = (WillPush.BanDict[A] == '●' ? '○' : '●'));

                WillPush.Level = Popped.Level + 1;

                WillPush.Log = new List<string>(Popped.Log);
                WillPush.Log.Add(BanToStr(WillPush.BanDict));

                stk.Push(WillPush);
            }
        }
        return false;
    }

    //最小の残り手数を返す(下限値枝切り用)
    static int DeriveNeedMinTesuu(Dictionary<char, char> pBanDict)
    {
        //表の枚数 / 2 の余りを切り上げ
        int OmoteCnt = pBanDict.Values.Count(X => X == '○');
        if (OmoteCnt % 2 == 0) return OmoteCnt / 2;
        return OmoteCnt / 2 + 1;
    }

    //盤面をString型で表現
    static string BanToStr(Dictionary<char, char> pBanDict)
    {
        var wkP = pBanDict;
        var sb = new System.Text.StringBuilder();
        sb.AppendFormat("     {0}", wkP['A']);
        sb.AppendLine();
        sb.AppendLine();
        sb.AppendFormat("{0}  {1}{2}  {3}", wkP['B'], wkP['C'], wkP['D'], wkP['E']);
        sb.AppendLine();
        sb.AppendFormat("   {0}  {1}", wkP['F'], wkP['G']);
        sb.AppendLine();
        sb.AppendFormat("     {0}", wkP['H']);
        sb.AppendLine();
        sb.AppendFormat("  {0}    {1}", wkP['I'], wkP['J']);
        sb.AppendLine();
        return sb.ToString();
    }
}


実行結果

省略
15手の解を発見
■■■■■0手目■■■■■
     ○

○  空○  ○
   ○  ○
     ○
  ○    ○

■■■■■1手目■■■■■
     ○

○  ○●  空
   ○  ○
     ○
  ○    ○

■■■■■2手目■■■■■
     ○

○  ○●  ○
   ○  ●
     ●
  空    ○

■■■■■3手目■■■■■
     ○

○  ○●  ○
   ○  空
     ○
  ●    ○

■■■■■4手目■■■■■
     空

○  ○○  ○
   ○  ○
     ○
  ●    ○

■■■■■5手目■■■■■
     ○

○  ○●  ○
   ○  ●
     ○
  ●    空

■■■■■6手目■■■■■
     ○

○  ○空  ○
   ○  ○
     ○
  ●    ●

■■■■■7手目■■■■■
     ○

空  ●○  ○
   ○  ○
     ○
  ●    ●

■■■■■8手目■■■■■
     ○

●  ●○  ○
   ●  ○
     ●
  ●    空

■■■■■9手目■■■■■
     ○

●  ●○  ○
   空  ○
     ○
  ●    ●

■■■■■10手目■■■■■
     空

●  ○○  ○
   ○  ○
     ○
  ●    ●

■■■■■11手目■■■■■
     ●

●  ●○  ○
   ●  ○
     ○
  空    ●

■■■■■12手目■■■■■
     ●

●  ●○  空
   ●  ●
     ●
  ○    ●

■■■■■13手目■■■■■
     ●

●  空●  ●
   ●  ●
     ●
  ○    ●

■■■■■14手目■■■■■
     ●

●  ○●  ●
   ○  ●
     ●
  空    ●

■■■■■15手目■■■■■
     空

●  ●●  ●
   ●  ●
     ●
  ●    ●

経過時間=00:00:14.2787949


解説

反復深化深さ優先探索で解いてます。

1手で最大2枚のコインを裏返せるので、
表の枚数 / 2 の余りを切り上げ
を下限値枝切りで使ってます。