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

Cマガ電脳クラブ(第107回) Hoppers

問題

下記のように、13個の円が直線でつながれた盤がある。コインを12個用意し、真ん中 (図中のG) 以外の円の上に置く。
この状態からスタートして、以下のルールに従ってコインを取り除き、
最後の1個のコインを、はじめに空所とした真ん中の円に残すのが目的である。
 1) あるコインXから見て、すぐ隣にコインYがあり、その先が空所のときは、XはYを跳び越せる。
     このとき跳び越されたコインYは取り除かれる
 2) 跳び越しは直線に沿って「まっすぐ」に行われる
     (たとえばBにあるコインがGにあるコインを跳び越えてFに行く「曲がり跳び」は許されない)
 3) コインは跳び越しによってのみ移動できる
 4) 1個のコインによる連続跳びは1手と数える
さて、今回問題とするのは、「最少手数は何手か」である。そのときの跳ぶ手順も添えてお答えいただきたい。

Fig1. Hoppers盤


ソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB = 5 - 1;

    struct PointDef
    {
        internal int X;
        internal int Y;
    }

    struct JyoutaiDef
    {
        internal int Level;
        internal bool[,] BanArr;
        internal PointDef CurrPos;
        internal List<bool[,]> Log;
    }

    static void Main()
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.Level = 0;
        WillPush.BanArr = InitBan();
        WillPush.CurrPos = new PointDef() { X = -1, Y = -1 };
        WillPush.Log = new List<bool[,]>() { WillPush.BanArr };
        Stk.Push(WillPush);

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

            //クリア判定
            if (IsClear(Popped.BanArr)) {
                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;

            for (int LoopX = 0; LoopX <= UB; LoopX++) {
                for (int LoopY = 0; LoopY <= UB; LoopY++) {
                    //対称解の除外で、最初はAからジャンプ
                    if (Popped.CurrPos.X == -1)
                        if (LoopX != 0 || LoopY != 0) continue;

                    if (Popped.BanArr[LoopX, LoopY] == false) continue;
                    JumpedInfoDef[] JumpedInfoArr =
                        DeriveJumpedInfoArr(Popped.BanArr, LoopX, LoopY);

                    foreach (JumpedInfoDef EachJumoedInfo in JumpedInfoArr) {
                        if (Popped.CurrPos.X != LoopX || Popped.CurrPos.Y != LoopY)
                            WillPush.Level = Popped.Level + 1;
                        else WillPush.Level = Popped.Level;

                        WillPush.BanArr = EachJumoedInfo.BanArr;
                        WillPush.CurrPos = EachJumoedInfo.NewCurrPos;
                        WillPush.Log = new List<bool[,]>(Popped.Log) { WillPush.BanArr };
                        Stk.Push(WillPush);
                    }
                }
            }
        }
    }

    //盤の初期状態を返す
    static bool[,] InitBan()
    {
        bool[,] WillReturn = new bool[UB + 1, UB + 1];
        WillReturn[0, 0] = WillReturn[2, 0] = WillReturn[4, 0] = true;
        WillReturn[1, 1] = WillReturn[3, 1] = true;
        WillReturn[0, 2] = WillReturn[4, 2] = true;
        WillReturn[1, 3] = WillReturn[3, 3] = true;
        WillReturn[0, 4] = WillReturn[2, 4] = WillReturn[4, 4] = true;
        return WillReturn;
    }

    //クリア判定
    static bool IsClear(bool[,] pBanArr)
    {
        if (pBanArr[2, 2] == false) return false;
        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                if (LoopX == 2 && LoopY == 2) continue;
                if (pBanArr[LoopX, LoopY]) return false;
            }
        }
        return true;
    }

    //ジャンプ後の盤情報
    struct JumpedInfoDef
    {
        internal bool[,] BanArr;
        internal PointDef NewCurrPos;
    }

    //カエルのジャンプ後の盤情報の配列を返す
    static JumpedInfoDef[] DeriveJumpedInfoArr(bool[,] pBanArr, int pFromX, int pFromY)
    {
        var WillReturn = new List<JumpedInfoDef>();

        Action<int, int> JumpAct = (pHeniX, pHeniY) =>
        {
            if (CanJump(pBanArr, pFromX, pFromY, pHeniX, pHeniY) == false)
                return;

            bool[,] wkArr = (bool[,])pBanArr.Clone();
            wkArr[pFromX, pFromY] = false;
            wkArr[pFromX + pHeniX, pFromY + pHeniY] = false;
            wkArr[pFromX + pHeniX * 2, pFromY + pHeniY * 2] = true;

            JumpedInfoDef WillAdd;
            WillAdd.BanArr = wkArr;
            WillAdd.NewCurrPos =
                new PointDef() { X = pFromX + pHeniX * 2, Y = pFromY + pHeniY * 2 };
            WillReturn.Add(WillAdd);
        };

        if (pFromX == 0 && pFromY == 0) { //Aからジャンプする場合
            JumpAct(0, 2);
            JumpAct(1, 1);
            JumpAct(2, 0);
        }
        if (pFromX == 2 && pFromY == 0) { //Bからジャンプする場合
            JumpAct(-1, 1);
            JumpAct(0, 2);
            JumpAct(1, 1);
        }
        if (pFromX == 4 && pFromY == 0) { //Cからジャンプする場合
            JumpAct(-1, 1);
            JumpAct(0, 2);
        }
        if (pFromX == 1 && pFromY == 1) { //Dからジャンプする場合
            JumpAct(1, 1);
        }
        if (pFromX == 3 && pFromY == 1) { //Eからジャンプする場合
            JumpAct(-1, 1);
        }
        if (pFromX == 0 && pFromY == 2) { //Fからジャンプする場合
            JumpAct(1, -1);
            JumpAct(2, 0);
            JumpAct(1, 1);
        }
        if (pFromX == 2 && pFromY == 2) { //Gからジャンプする場合
            JumpAct(-1, -1);
            JumpAct(1, -1);
            JumpAct(-1, 1);
            JumpAct(1, 1);
        }
        if (pFromX == 4 && pFromY == 2) { //Hからジャンプする場合
            JumpAct(-1, -1);
            JumpAct(-2, 0);
            JumpAct(-1, 1);
        }
        if (pFromX == 1 && pFromY == 3) { //Iからジャンプする場合
            JumpAct(1, -1);
        }
        if (pFromX == 3 && pFromY == 3) { //Jからジャンプする場合
            JumpAct(-1, -1);
        }
        if (pFromX == 0 && pFromY == 4) { //Kからジャンプする場合
            JumpAct(0, -2);
            JumpAct(1, -1);
            JumpAct(2, 0);
        }
        if (pFromX == 2 && pFromY == 4) { //Lからジャンプする場合
            JumpAct(-1, -1);
            JumpAct(0, -2);
            JumpAct(1, -1);
        }
        if (pFromX == 4 && pFromY == 4) { //Mからジャンプする場合
            JumpAct(0, -2);
            JumpAct(-1, -1);
            JumpAct(-2, 0);
        }
        return WillReturn.ToArray();
    }

    //カエルがジャンプできるかを判定
    static bool CanJump(bool[,] pBanArr, int pFromX, int pFromY, int pHeniX, int pHeniY)
    {
        if (pBanArr[pFromX + pHeniX, pFromY + pHeniY] == false) return false;
        if (pBanArr[pFromX + pHeniX * 2, pFromY + pHeniY * 2]) return false;
        return true;
    }

    //盤面を出力
    static void PrintBan(bool[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                if ((X + Y) % 2 == 0) {
                    if (pBanArr[X, Y]) sb.Append('カ');
                    else sb.Append('○');
                }
                else sb.Append(' ');
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}


実行結果

省略
7手の解候補を発見
レベル0
カ カ カ
 カ カ
カ ○ カ
 カ カ
カ カ カ

レベル1
○ カ カ
 ○ カ
カ カ カ
 カ カ
カ カ カ

レベル2
○ カ カ
 カ カ
カ ○ カ
 カ ○
カ カ カ

レベル3
○ カ ○
 カ ○
カ カ カ
 カ ○
カ カ カ

レベル4
○ カ ○
 カ カ
カ ○ カ
 ○ ○
カ カ カ

レベル5
カ カ ○
 カ カ
○ ○ カ
 ○ ○
○ カ カ

レベル6
○ ○ カ
 カ カ
○ ○ カ
 ○ ○
○ カ カ

レベル7
○ ○ ○
 カ ○
○ カ カ
 ○ ○
○ カ カ

レベル8
○ ○ ○
 カ ○
カ ○ ○
 ○ ○
○ カ カ

レベル9
○ ○ ○
 カ ○
カ ○ ○
 ○ ○
カ ○ ○

レベル10
カ ○ ○
 カ ○
○ ○ ○
 ○ ○
○ ○ ○

レベル11
○ ○ ○
 ○ ○
○ カ ○
 ○ ○
○ ○ ○


解説

変位ベクトルを使って、カエルの移動を表現してます。

22-02 Hoppers