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

Cマガ電脳クラブ(第010回) 偶数個の列

問題

4×4の枠の中にコインを置く。
たとえば10個をFig.1のように置くと、点線で示したように、
タテ、ヨコ、ナナメの方向に、「偶数個の列」が10本できている (この問題でのナナメは、45度方向に限定する) 。

さて、コインの配置をかえて、
「偶数個の列」の本数を最大何本まで増やせるだろうか。
その本数と置き方は何通りあるか (回転・鏡像解を除く) を答えてほしい。
ただし、4×4の枠の中であれば、コインは何個使ってもよいことにする。もちろん、17個以上は使えない。

Fig.1

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int Haba = 4;

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

        //var CombiList = new List<bool[,]>() {new bool[,] {{true,true,false,false},
        //                                                  {true,false,true,true},
        //                                                  {true,true,true,false},
        //                                                  {true, false, false,true}}};
        List<bool[,]> CombiList = DeriveCombiList();
        RemoveLittleCnt(CombiList);

        int AnswerCnt = 0;
        var AnswerArrList = new List<bool[,]>();

        foreach (var AnyBoolArr in CombiList) {
            //横方向のコインを数える
            Func<int, int> CntYokoCoin = pY =>
            {
                int WillReturn = 0;
                for (int X = 0; X <= Haba - 1; X++)
                    if (AnyBoolArr[X, pY]) WillReturn++;
                return WillReturn;
            };

            //縦方向のコインを数える
            Func<int, int> CntTateCoin = pX =>
            {
                int WillReturn = 0;
                for (int Y = 0; Y <= Haba - 1; Y++)
                    if (AnyBoolArr[pX, Y]) WillReturn++;
                return WillReturn;
            };

            //右上方向のコインを数える
            Func<int, int, int> CntMigiueCoin = (pX, pY) =>
            {
                int WillReturn = 0;
                for (int X = pX, Y = pY; X <= Haba - 1 && 0 <= Y; X++, Y--)
                    if (AnyBoolArr[X, Y]) WillReturn++;
                return WillReturn;
            };

            //左上方向のコインを数える
            Func<int, int, int> CntHidariueCoin = (pX, pY) =>
            {
                int WillReturn = 0;
                for (int X = pX, Y = pY; 0 <= X && 0 <= Y; X--, Y--)
                    if (AnyBoolArr[X, Y]) WillReturn++;
                return WillReturn;
            };

            int EvenLineCnt = 0;
            Action<int> EvenHyouka = (pTarget) =>
            {
                //問題文から0は偶数として扱わない
                if (pTarget % 2 == 0 && pTarget > 0) EvenLineCnt++;
            };

            for (int I = 0; I <= Haba - 1; I++) {
                EvenHyouka(CntYokoCoin(I));
                EvenHyouka(CntTateCoin(I));
            }

            EvenHyouka(CntMigiueCoin(0, 1));
            EvenHyouka(CntMigiueCoin(0, 2));
            EvenHyouka(CntMigiueCoin(0, 3));
            EvenHyouka(CntMigiueCoin(1, 3));
            EvenHyouka(CntMigiueCoin(2, 3));
            EvenHyouka(CntHidariueCoin(3, 1));
            EvenHyouka(CntHidariueCoin(3, 2));
            EvenHyouka(CntHidariueCoin(3, 3));
            EvenHyouka(CntHidariueCoin(2, 3));
            EvenHyouka(CntHidariueCoin(1, 3));

            if (AnswerCnt > EvenLineCnt) continue;
            AnswerCnt = EvenLineCnt;
            AnswerArrList.Clear();

            Console.WriteLine("偶数となるラインが{0}本の配置を発見。", EvenLineCnt);
            AnswerArrList.Add(AnyBoolArr);
        }

        RemoveKaiten(AnswerArrList);
        foreach (var AnyBoolArr in AnswerArrList)
            PrintJyoutai(AnyBoolArr);
    }

    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal bool[,] HaitiArr;
    }

    //2の16乗通りの組み合わせを求める
    static List<bool[,]> DeriveCombiList()
    {
        var WillReturnList = new List<bool[,]>();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrX = WillPush.CurrY = 0;

        WillPush.HaitiArr = new bool[Haba, Haba];
        stk.Push(WillPush);
        WillPush.HaitiArr = new bool[Haba, Haba];
        WillPush.HaitiArr[0, 0] = true;
        stk.Push(WillPush);

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

            WillPush.CurrX = Popped.CurrX;
            WillPush.CurrY = Popped.CurrY;

            if (++WillPush.CurrX > WillPush.HaitiArr.GetUpperBound(0)) {
                WillPush.CurrX = 0;
                WillPush.CurrY++;
            }
            if (WillPush.CurrY > WillPush.HaitiArr.GetUpperBound(1)) {
                WillReturnList.Add(Popped.HaitiArr);
                continue;
            }

            WillPush.HaitiArr = Popped.HaitiArr;
            stk.Push(WillPush);
            WillPush.HaitiArr = (bool[,])Popped.HaitiArr.Clone();
            WillPush.HaitiArr[WillPush.CurrX, WillPush.CurrY] = true;
            stk.Push(WillPush);
        }
        return WillReturnList;
    }

    //0個,1個,2個は除外
    static void RemoveLittleCnt(List<bool[,]> pTargetList)
    {
        for (int I = pTargetList.Count - 1; I >= 0; I--) {
            int CoinCnt = 0;
            for (int X = 0; X <= Haba - 1; X++) {
                for (int Y = 0; Y <= Haba - 1; Y++) {
                    if (pTargetList[I][X, Y]) CoinCnt++;
                }
            }
            if (CoinCnt <= 2) pTargetList.RemoveAt(I);
        }
    }

    //回転を除外
    static void RemoveKaiten(List<bool[,]> pTargetList)
    {
        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 = pTargetList[pCurrInd][X, Y];
                        if (pTargetList[I][UB - X, Y] != CurrVal) IsOK1 = true;
                        if (pTargetList[I][UB - X, UB - Y] != CurrVal) IsOK2 = true;
                        if (pTargetList[I][X, UB - Y] != CurrVal) IsOK3 = true;
                        if (pTargetList[I][Y, X] != CurrVal) IsOK4 = true;
                        if (pTargetList[I][UB - Y, X] != CurrVal) IsOK5 = true;
                        if (pTargetList[I][UB - Y, UB - X] != CurrVal) IsOK6 = true;
                        if (pTargetList[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 = pTargetList.Count - 1; I >= 0; I--) {
            if (IsExist(I)) pTargetList.RemoveAt(I);
        }
    }

    //盤面を表示
    static void PrintJyoutai(bool[,] pHaitiArr)
    {
        for (int Y = 0; Y <= Haba - 1; Y++) {
            for (int X = 0; X <= Haba - 1; X++) {
                Console.Write(pHaitiArr[X, Y] ? '●' : '□');
            }
            Console.WriteLine();
        }
    }
}

実行結果

偶数となるラインが14本の配置を発見。
偶数となるラインが16本の配置を発見。
偶数となるラインが16本の配置を発見。
偶数となるラインが18本の配置を発見。
●●●●
●□□●
●□□●
●●●●

解説

問題文から、コインの数が0個のラインをカウントしないようにしてます。