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

Cマガ電脳クラブ(第013回) 線上に欠けるコイン

問題

16個のコインを8×8の盤の上に置いたところ、
どの3個のコインを見ても一直線上に並んでいるものがなかった。

さて、どのように並べたのだろうか。
ただし、これだとたくさんの解があるので、
「Fig.1の斜線のついたマス目にはコインを置かない」という条件をつけることにする。
何通りの置き方があるだろうか。

もちろん、コインは1マスに1個しか置けないし、回転・鏡像の解は除く。
「一直線」というのは縦、横、斜めだが、斜めが45度方向だけでないことに注意!

Fig.1


ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal int CoinCnt;
        internal bool[,] IsSetArr;
    }

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

        JyoutaiDef WillPush;
        WillPush.CurrX = WillPush.CurrY = 0;
        WillPush.CoinCnt = 0;
        WillPush.IsSetArr = new bool[8, 8];
        stk.Push(WillPush);

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

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

            if (Popped.CoinCnt == 16) {
                AnswerArrList.Add(Popped.IsSetArr);
                continue;
            }

            //次に配置するコインのX座標は、配置済のコイン数/2で求まる
            int X = Popped.CoinCnt / 2;

            for (int Y = 0; Y <= Popped.IsSetArr.GetUpperBound(1); Y++) {
                //コインが配置不可ならContinue
                if (IsOKMasu(X, Y) == false) continue;

                //Currentより後の座標でない場合は、Continue
                if (X < Popped.CurrX) continue;
                if (X == Popped.CurrX && Y <= Popped.CurrY) continue;

                //コインが2枚並んだライン上ならContinue
                if (Popped.CoinCnt >= 2 && IsExist2CoinsLine(Popped.IsSetArr, X, Y))
                    continue;

                WillPush.CurrX = X;
                WillPush.CurrY = Y;
                WillPush.CoinCnt = Popped.CoinCnt + 1;
                WillPush.IsSetArr = (bool[,])Popped.IsSetArr.Clone();
                WillPush.IsSetArr[X, Y] = true;

                stk.Push(WillPush);
            }
        }
        RemoveKaiten(AnswerArrList);
        for (int I = 0; I <= AnswerArrList.Count - 1; I++) {
            Console.WriteLine("解{0}を発見。", I + 1);
            PrintBan(AnswerArrList[I]);
        }
    }

    //コインが配置可能なマスかを返す
    static bool IsOKMasu(int pX, int pY)
    {
        if (pX == pY) return false;
        if (pX + pY == 7) return false;
        return true;
    }

    //コインが2枚並んだラインの有無を返す
    static bool IsExist2CoinsLine(bool[,] pIsSetArr, int pX1, int pY1)
    {
        Func<int, int, bool> Is2CoinsLine = (pX2, pY2) =>
        {
            int HeniX = pX2 - pX1;
            int HeniY = pY2 - pY1;
            DeriveHeniNBai(ref HeniX, ref HeniY);

            int CoinCnt = 0;
            for (int X = pX1, Y = pY1;
                0 <= X && X <= pIsSetArr.GetUpperBound(0)
             && 0 <= Y && Y <= pIsSetArr.GetUpperBound(1); X += HeniX, Y += HeniY) {
                if (pIsSetArr[X, Y] && ++CoinCnt == 2) return true;
            }
            for (int X = pX1, Y = pY1;
                0 <= X && X <= pIsSetArr.GetUpperBound(0)
             && 0 <= Y && Y <= pIsSetArr.GetUpperBound(1); X -= HeniX, Y -= HeniY) {
                if (pIsSetArr[X, Y] && ++CoinCnt == 2) return true;
            }

            return false;
        };

        for (int X = 0; X <= pIsSetArr.GetUpperBound(0); X++) {
            for (int Y = 0; Y <= pIsSetArr.GetUpperBound(1); Y++) {
                if (pIsSetArr[X, Y] && Is2CoinsLine(X, Y))
                    return true;
            }
        }
        return false;
    }

    //2点間の変位ベクトルのn分の1倍を求める
    static void DeriveHeniNBai(ref int pX, ref int pY)
    {
        if (pX == 0) { pY = 1; return; }
        if (pY == 0) { pX = 1; return; }

        while (true) { //互いに素になるまで最大公約数で割る
            int GCD = DeriveGCD(Math.Abs(pX), Math.Abs(pY));
            if (GCD == 1) return;
            pX /= GCD;
            pY /= GCD;
        }
    }

    //ユークリッドの互除法で2数の最大公約数を求める
    static int DeriveGCD(int pVal1, int pVal2)
    {
        int WarareruKazu = Math.Max(pVal1, pVal2);
        int WaruKazu = Math.Min(pVal1, pVal2);

        while (true) {
            int Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }

    //回転を除外
    static void RemoveKaiten(List<bool[,]> pTargetList)
    {
        const int UB = 8 - 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 PrintBan(bool[,] pIsSetArr)
    {
        var sb = new System.Text.StringBuilder();

        for (int Y = 0; Y <= pIsSetArr.GetUpperBound(0); Y++) {
            for (int X = 0; X <= pIsSetArr.GetUpperBound(1); X++) {
                if (pIsSetArr[X, Y]) sb.Append('●');
                else sb.Append('□');
            }
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }
}


実行結果

解1を発見。
□□●□●□□□
□□●□□●□□
□●□□□□□●
□□□□□●●□
□●□□□□□●
●□□●□□□□
●□□□●□□□
□□□●□□●□
解2を発見。
□□□●□●□□
□□●□□□□●
□□□●□□●□
□●□□□□□●
●□□□□□●□
□●□□●□□□
●□□□□●□□
□□●□●□□□
解3を発見。
□□□□●●□□
□□●□●□□□
□●□□□□□●
□□□□□□●●
●□●□□□□□
□□□●□□●□
●□□□□●□□
□●□●□□□□
解4を発見。
□□●●□□□□
□□●●□□□□
□□□□□□●●
□□□□□□●●
●●□□□□□□
●●□□□□□□
□□□□●●□□
□□□□●●□□
解5を発見。
□□●□●□□□
□□□□□●□●
□●□●□□□□
●□□□□□●□
□●□□□□□●
□□□□●□●□
●□●□□□□□
□□□●□●□□
解6を発見。
□□●□●□□□
□□●●□□□□
□□□□□□●●
●□□□□□●□
□●□□□□□●
●●□□□□□□
□□□□●●□□
□□□●□●□□
解7を発見。
□□●□●□□□
□□□●□●□□
□●□□□□□●
●□□□□□●□
□●□□□□□●
●□□□□□●□
□□●□●□□□
□□□●□●□□
解8を発見。
□□●□●□□□
□□□□●●□□
□●□□□□□●
●●□□□□□□
□□□□□□●●
●□□□□□●□
□□●●□□□□
□□□●□●□□


解説

8×8の盤に16枚のコインを置くのですから、1列に置けるコインは2枚となることを、
枝切り条件に使ってます。