Cマガ電脳クラブ(第043回) ひろいもの

問題

『勘者御伽双紙』(1743年)など日本の古来の数学遊戯である「ひろいもの」が、いま世界の注目を浴びている。
碁盤上に置かれた石を、次のルールで全部取るのがその目的である。
１) 出発点として1個を選んで拾う
２) その場所から縦か横の線に沿って進み、その線上に別の石があったらそれを拾うことができる
３) 石を拾ったらその場所からまた縦か横の線に沿って進み、次の石を拾う。
    ただしこのときバックの方向にだけは進んではいけない
４) バック以外のどの方向に向かっても石がなかったら、終点である
５) 手前に石があるのにその先の石を拾うことはできない

ひとつ例をあげよう(Fig.1)。「正」の解答例だ。数の順に拾えばいいのである。
さて、今月の問題は Fig.2 の5段の菱形である。その解答は何通りあるか、すべてを探してほしい。
同じものを登録しないようにどうぞ。

Fig.1 「ひろいもの」の「正」の解答


Fig.2 「ひろいもの」5段の菱形

ソース

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

class Program
{
    static int UB_X;
    static int UB_Y;

    struct JyoutaiDef
    {
        internal int Level;
        internal char[,] BanArr;
    }

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

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

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

        //bool IsSentaisyou = false; //問題が線対称か？
        //char[,] RevArr = new char[,] {{' ','*','*','*','*','*','*','*'},
        //                              {' ',' ',' ',' ','*',' ',' ',' '},
        //                              {' ',' ','*',' ','*',' ',' ',' '},
        //                              {' ',' ','*',' ','*',' ',' ',' '},
        //                              {'*','*','*','*','*','*','*','*'}};

        bool IsSentaisyou = true; //問題が線対称か？
        char[,] RevArr = new char[,] {{'*','*','*','*','*',' ',' ',' ',' '},
                                      {' ','*','*','*','*','*',' ',' ',' '},
                                      {' ',' ','*','*','*','*','*',' ',' '},
                                      {' ',' ',' ','*','*','*','*','*',' '},
                                      {' ',' ',' ',' ','*','*','*','*','*'}};

        //縦横変換してセット
        UB_X = RevArr.GetUpperBound(1);
        UB_Y = RevArr.GetUpperBound(0);

        char[,] wkArr = new char[UB_X + 1, UB_Y + 1];
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                wkArr[X, Y] = RevArr[Y, X];
            }
        }

        //開始位置の数だけStackにPush
        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                //線対称な解を除外
                if (IsSentaisyou && UB_X / 2 < X) break;

                if (wkArr[X, Y] != '*') continue;

                WillPush.Level = 1;
                WillPush.BanArr = (char[,])wkArr.Clone();
                WillPush.BanArr[X, Y] = '1';
                stk.Push(WillPush);
            }
        }

        int AnwserCnt = 0;

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

            //クリア判定
            if (Popped.BanArr.Cast<char>().All(X => X != '*')) {
                Console.WriteLine("解{0}を発見。経過時間={1}", ++AnwserCnt, sw.Elapsed);
                PrintAnswer(Popped.BanArr);
                continue;
            }

            //移動可能な座標の配列
            PointDef[] CanMovePointArr =
                DeriveCanMovePointArr(Popped.Level, Popped.BanArr);

            foreach (PointDef EachPoint in CanMovePointArr) {
                WillPush.Level = Popped.Level + 1;
                WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                WillPush.BanArr[EachPoint.X, EachPoint.Y] = DecToStr(WillPush.Level);
                stk.Push(WillPush);
            }
        }
    }

    //10進数をchar型に変換
    static char DecToStr(int pInt)
    {
        if (pInt < 10) return (char)((int)'1' + pInt - 1);
        return (char)((int)'A' + pInt - 10);
    }

    //移動可能な座標の配列を返す
    static PointDef[] DeriveCanMovePointArr(int pCurrLevel, char[,] pBanArr)
    {
        var CanMovePointList = new List<PointDef>();

        //Levelを元に、現在地を求める
        PointDef CurrPoint = DeriveLevelPoint(pCurrLevel, pBanArr);

        var HeniList = new List<PointDef>();
        HeniList.Add(new PointDef() { X = 0, Y = -1 });
        HeniList.Add(new PointDef() { X = 0, Y = 1 });
        HeniList.Add(new PointDef() { X = -1, Y = 0 });
        HeniList.Add(new PointDef() { X = 1, Y = 0 });

        if (pCurrLevel >= 2) {
            //Levelを元に、ひとつ前の位置を求める
            PointDef PrevPoint = DeriveLevelPoint(pCurrLevel - 1, pBanArr);

            //直近の移動の変位ベクトルを求める
            PointDef PrevHeni;
            PrevHeni.X = CurrPoint.X - PrevPoint.X;
            PrevHeni.Y = CurrPoint.Y - PrevPoint.Y;

            if (PrevHeni.X > 1) PrevHeni.X = 1;
            if (PrevHeni.X < -1) PrevHeni.X = -1;
            if (PrevHeni.Y > 1) PrevHeni.Y = 1;
            if (PrevHeni.Y < -1) PrevHeni.Y = -1;

            //逆ベクトルを変位ベクトルのListからRemove(バックできないから)
            HeniList.RemoveAll(A => A.X == -PrevHeni.X && A.Y == -PrevHeni.Y);
        }

        //変位ごとに、拾う石があったら、移動可能な座標となる
        foreach (PointDef EachHeni in HeniList) {
            for (PointDef wkPoint = CurrPoint;
                 0 <= wkPoint.X && wkPoint.X <= UB_X &&
                 0 <= wkPoint.Y && wkPoint.Y <= UB_Y;
                 wkPoint.X += EachHeni.X, wkPoint.Y += EachHeni.Y) {
                if (pBanArr[wkPoint.X, wkPoint.Y] == '*') {
                    CanMovePointList.Add(wkPoint);
                    break;
                }
            }
        }
        return CanMovePointList.ToArray();
    }

    //引数のレベルの座標を返す
    static PointDef DeriveLevelPoint(int pTargetLevel, char[,] pBanArr)
    {
        PointDef WillReturn = new PointDef() { X = -1, Y = -1 };
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                if (pBanArr[X, Y] != DecToStr(pTargetLevel)) continue;
                WillReturn.X = X;
                WillReturn.Y = Y;
                return WillReturn;
            }
        }
        return WillReturn;
    }

    //解を出力
    static void PrintAnswer(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

省略
解22を発見。経過時間=00:00:14.5480121
12HIJ
 345KL
  G6FED
   78MCN
    9ABOP

解23を発見。経過時間=00:00:14.5941992
12KLM
 345AB
  J69CI
   78DEF
    NOHGP

解24を発見。経過時間=00:00:14.6219589
12LMN
 345AB
  K69CJ
   78DIH
    OEFGP

解説

座標と変位ベクトルで移動の管理をしてます。

13-03 イージースフィア