Q69 男女平等な席替え

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB_X = 6 - 1;
    const int UB_Y = 5 - 1;

    struct JyoutaiDef
    {
        internal char[,] BanArr;
        internal int CurrX;
        internal int CurrY;
        internal int MenCnt;
        internal int WomenCnt;
    }

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

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanArr = new char[UB_X + 1, UB_Y + 1];
        for (int X = 0; X <= UB_X; X++)
            for (int Y = 0; Y <= UB_Y; Y++)
                WillPush.BanArr[X, Y] = ' ';

        WillPush.CurrX = WillPush.CurrY = 0;
        WillPush.MenCnt = WillPush.WomenCnt = 0;
        stk.Push(WillPush);

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

            //X座標の繰上げ処理
            if (Popped.CurrX > UB_X) {
                Popped.CurrX = 0;
                Popped.CurrY++;
            }

            //最終行を超えた場合
            if (Popped.CurrY > UB_Y) {
                AnswerCnt++;
                if (AnswerCnt % 200000 == 0) {
                    Console.WriteLine("解{0}を発見。経過時間={1}",
                        AnswerCnt, sw.Elapsed);
                    PrintBan(Popped.BanArr);
                }
                continue;
            }

            Action<char> PushSyori = (pSeibetu) =>
            {
                WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                WillPush.BanArr[Popped.CurrX, Popped.CurrY] = pSeibetu;
                if (WillEdakiri(WillPush.BanArr, Popped.CurrX, Popped.CurrY))
                    return;
                WillPush.CurrX = Popped.CurrX + 1;
                WillPush.CurrY = Popped.CurrY;
                WillPush.MenCnt = Popped.MenCnt;
                WillPush.WomenCnt = Popped.WomenCnt;
                if (pSeibetu == '男') WillPush.MenCnt++;
                if (pSeibetu == '女') WillPush.WomenCnt++;
                stk.Push(WillPush);
            };

            if (Popped.MenCnt < 15) PushSyori('男');
            //[0,0]は固定で男として、最後に、場合の数を2倍する
            if (Popped.CurrX == 0 && Popped.CurrY == 0) continue;
            if (Popped.WomenCnt < 15) PushSyori('女');
        }
        Console.WriteLine("解は{0}通り", AnswerCnt * 2);
    }

    //枝切り判定
    static bool WillEdakiri(char[,] pBanArr, int pCurrX, int pCurrY)
    {
        //1つ上のマスをチェック
        if (pCurrY > 0) {
            if (IsIseiRinsetu(pBanArr, pCurrX, pCurrY - 1) == false)
                return true;
        }

        if (pCurrY == UB_Y) {
            //1つ左のマスをチェック
            if (0 < pCurrX) {
                if (IsIseiRinsetu(pBanArr, pCurrX - 1, pCurrY) == false)
                    return true;
            }
            //当該マスをチェック
            if (pCurrX == UB_X) {
                if (IsIseiRinsetu(pBanArr, pCurrX, pCurrY) == false)
                    return true;
            }
        }
        return false;
    }

    //そのマス目が異性に隣接かをチェック
    static bool IsIseiRinsetu(char[,] pBanArr, int pTargetX, int pTargetY)
    {
        Func<int, int, bool> CheckFunc = (pRinsetuX, pRinsetuY) =>
        {
            if (pRinsetuX < 0 || UB_X < pRinsetuX) return false;
            if (pRinsetuY < 0 || UB_Y < pRinsetuY) return false;

            char wkChar1 = pBanArr[pTargetX, pTargetY];
            char wkChar2 = pBanArr[pRinsetuX, pRinsetuY];
            return wkChar1 != wkChar2;
        };
        if (CheckFunc(pTargetX, pTargetY - 1)) return true;
        if (CheckFunc(pTargetX, pTargetY + 1)) return true;
        if (CheckFunc(pTargetX - 1, pTargetY)) return true;
        if (CheckFunc(pTargetX + 1, pTargetY)) return true;
        return false;
    }

    //盤面を出力
    static void PrintBan(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());
    }
}

実行結果

省略
解6200000を発見。経過時間=00:01:11.8996676
男男男女女男
女女男女女男
男男女男女男
女女男女女男
女男男女男女

解6400000を発見。経過時間=00:01:14.1034148
男男男女男女
女女男男女男
男女女女女男
女男男女女女
男女男男男女

解6600000を発見。経過時間=00:01:16.3639560
男男男男女男
女女女男女女
男女女男男男
女女女女女男
女男男男女男

解は13374192通り

解説

左上の隅を固定で男として、最後に場合の数を2倍してます。