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

Cマガ電脳クラブ(第005回) コインの距離

問題

Fig.1のように、格子の上にコインを4個置く。ひとつの格子間の距離を1とすると
AB=ルート(17)
AC=3*ルート(2)
AD=5
BC=ルート(5)
BD=ルート(10)
CD=1
となり、すべてのコインの中心間の距離が異なっている。

では、Fig.2の格子の上に6個のコインをFig.1と同じ条件で置くには、どのようにしたらよいだろう。

もちろん、コインを重ねてはいけない。
回転や裏返しは別の解とはせずに同じものとみなすとすると、全部で何通りの置き方があるだろうか。

Fig.1               Fig.2
A--+--+--+--+       +--+--+--+--+--+
|  |  |  |  |       |  |  |  |  |  |
+--+--+--+--+       +--+--+--+--+--+
|  |  |  |  |       |  |  |  |  |  |
+--+--+--+--+       +--+--+--+--+--+
|  |  |  |  |       |  |  |  |  |  |
+--+--+--C--D       +--+--+--+--+--+
|  |  |  |  |       |  |  |  |  |  |
+--B--+--+--+       +--+--+--+--+--+
                    |  |  |  |  |  |
                    +--+--+--+--+--+


ソース

using System;
using System.Collections.Generic;

class Program
{
    //const int Haba = 5; const int OKCnt = 4;
    const int Haba = 6; const int OKCnt = 6;

    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal bool[,] HaitiArr;
        internal int HaitiCnt;
        internal HashSet<int> KyouriSet;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        for (int X = 0; X <= Haba - 1; X++) {
            for (int Y = 0; Y <= Haba - 1; Y++) {
                WillPush.CurrX = X;
                WillPush.CurrY = Y;
                WillPush.HaitiArr = new bool[Haba, Haba];
                WillPush.HaitiArr[X, Y] = true;
                WillPush.HaitiCnt = 1;
                WillPush.KyouriSet = new HashSet<int>();
                stk.Push(WillPush);
            }
        }

        var AnswerHaitiList = new List<bool[,]>();

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

            if (Popped.HaitiCnt == OKCnt) {
                //if (Popped.KyouriSet.Contains(17) == false) continue;
                //if (Popped.KyouriSet.Contains(9 * 2) == false) continue;
                //if (Popped.KyouriSet.Contains(25) == false) continue;
                //if (Popped.KyouriSet.Contains(5) == false) continue;
                //if (Popped.KyouriSet.Contains(10) == false) continue;
                //if (Popped.KyouriSet.Contains(1) == false) continue;

                AnswerHaitiList.Add(Popped.HaitiArr);
                continue;
            }

            if (++Popped.CurrY > Haba - 1) {
                Popped.CurrX++;
                Popped.CurrY = 0;
            }

            for (int X = Popped.CurrX; X <= Haba - 1; X++) {
                for (int Y = Popped.CurrY; Y <= Haba - 1; Y++) {
                    WillPush.CurrX = X;
                    WillPush.CurrY = Y;
                    WillPush.KyouriSet = new HashSet<int>(Popped.KyouriSet);
                    if (AddCalcKyouri(X, Y, Popped.HaitiArr, WillPush.KyouriSet)) {
                        WillPush.HaitiArr = (bool[,])Popped.HaitiArr.Clone();
                        WillPush.HaitiArr[X, Y] = true;
                        WillPush.HaitiCnt = Popped.HaitiCnt + 1;
                        stk.Push(WillPush);
                    }
                }
            }
        }
        RemoveKaitenKai(AnswerHaitiList);
        for(int I=0;I<=AnswerHaitiList.Count-1;I++){
            Console.WriteLine();
            Console.WriteLine("解{0}", I + 1);
            PrintJyoutai(AnswerHaitiList[I]);
        }
    }

    static bool AddCalcKyouri(int pX, int pY, bool[,] pSetArr, HashSet<int> pKyouriSet)
    {
        for (int X = 0; X <= pSetArr.GetUpperBound(0); X++) {
            for (int Y = 0; Y <= pSetArr.GetUpperBound(1); Y++) {
                if (pSetArr[X, Y]) {
                    bool wkBool = pKyouriSet.Add((X - pX) * (X - pX) + (Y - pY) * (Y - pY));
                    if (wkBool == false) return false;
                }
            }
        }
        return true;
    }

    //回転した解を除外
    static void RemoveKaitenKai(List<bool[,]> pAnswerSetList)
    {
        const int UB = Haba - 1;

        Predicate<int> IsExist = (pCurrInd) =>
        {
            for (int I = 0; I <= pCurrInd - 1; I++) {
                bool IsOK1 = false, IsOK2 = false, IsOK3 = false, IsOK4 = false;
                bool IsOK5 = false, IsOK6 = false, IsOK7 = false; //回転1から7

                for (int X = 0; X <= UB; X++) {
                    for (int Y = 0; Y <= UB; Y++) {
                        bool CurrVal = pAnswerSetList[pCurrInd][X, Y];
                        if (pAnswerSetList[I][UB - X, Y] != CurrVal) IsOK1 = true;
                        if (pAnswerSetList[I][UB - X, UB - Y] != CurrVal) IsOK2 = true;
                        if (pAnswerSetList[I][X, UB - Y] != CurrVal) IsOK3 = true;
                        if (pAnswerSetList[I][Y, X] != CurrVal) IsOK4 = true;
                        if (pAnswerSetList[I][UB - Y, X] != CurrVal) IsOK5 = true;
                        if (pAnswerSetList[I][UB - Y, UB - X] != CurrVal) IsOK6 = true;
                        if (pAnswerSetList[I][Y, UB - X] != CurrVal) IsOK7 = true;
                    }
                }
                if (IsOK1 == false || IsOK2 == false || IsOK3 == false || IsOK4 == false
                 || IsOK5 == false || IsOK6 == false || IsOK7 == false)
                    return true;
            }
            return false;
        };

        for (int I = pAnswerSetList.Count - 1; I >= 0; I--) {
            if (IsExist(I)) pAnswerSetList.RemoveAt(I);
        }
    }

    //盤面を表示
    static void PrintJyoutai(bool[,] pHaitiArr)
    {
        char wkChar = 'A';

        for (int X = 0; X <= Haba - 1; X++) {
            for (int Y = 0; Y <= Haba - 1; Y++) {
                if (pHaitiArr[X, Y]) {
                    Console.Write(wkChar++);
                }
                else {
                    Console.Write('+');
                }
                if (Y < Haba - 1) Console.Write('-');
            }
            Console.WriteLine();
            if (X == Haba - 1) return;
            for (int Y = 0; Y <= Haba - 1; Y++) {
                if (Y < Haba - 1) Console.Write("| ");
                else Console.WriteLine('|');
            }
        }
    }
}


実行結果

解1
+-+-+-+-+-A
| | | | | |
B-C-+-+-+-+
| | | | | |
+-+-D-+-+-+
| | | | | |
+-+-+-+-+-E
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-F

解2
A-B-+-+-+-+
| | | | | |
+-+-+-C-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-D
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-E-+-+-F


解説

HashSetジェネリックで重複した距離の管理をしてます。