Q47 オンリーワンな○×

C#のソース

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

class Program
{
    const int UB = 4 - 1;

    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal char[,] BanArr;
        internal int[] YokoSumArr;
        internal int[] TateSumArr;
    }

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

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

        WillPush.CurrX = WillPush.CurrY = 0;
        WillPush.YokoSumArr = new int[UB + 1];
        WillPush.TateSumArr = new int[UB + 1];
        stk.Push(WillPush);

        var AnswerJyoutaiList = new List<JyoutaiDef>();

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

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

            //最終行を超えた場合
            if (Popped.CurrY > UB) {
                //PrintBan(Popped.BanArr);
                AnswerJyoutaiList.Add(Popped);
                continue;
            }

            Action<char> PushSyori = pChar =>
            {
                WillPush.CurrX = Popped.CurrX + 1;
                WillPush.CurrY = Popped.CurrY;
                WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                WillPush.BanArr[Popped.CurrX, Popped.CurrY] = pChar;

                if (pChar == '○') {
                    WillPush.YokoSumArr = (int[])Popped.YokoSumArr.Clone();
                    WillPush.TateSumArr = (int[])Popped.TateSumArr.Clone();
                    WillPush.YokoSumArr[Popped.CurrY]++;
                    WillPush.TateSumArr[Popped.CurrX]++;

                    //横方向での○の数を(広義の)単調減少とする
                    for (int I = 0; I <= Popped.CurrY - 1; I++) {
                        if (WillPush.YokoSumArr[I] < WillPush.YokoSumArr[I + 1])
                            return;
                    }
                }
                else {
                    WillPush.YokoSumArr = Popped.YokoSumArr;
                    WillPush.TateSumArr = Popped.TateSumArr;
                }
                stk.Push(WillPush);
            };
            PushSyori('○'); 
            PushSyori('×');
        }
        Console.WriteLine("解は{0}通り。経過時間={1}",
            CntOnlyOne(AnswerJyoutaiList), sw.Elapsed);
    }

    //オンリーワンな配置を数える
    static int CntOnlyOne(List<JyoutaiDef> pAnswerJyoutaiList)
    {
        int WillReturn = 0;
        for (int I = 0; I <= pAnswerJyoutaiList.Count - 1; I++) {
            bool IsOnlyOne = true;
            for (int J = 0; J <= pAnswerJyoutaiList.Count - 1; J++) {
                if (I == J) continue;
                if (pAnswerJyoutaiList[I].YokoSumArr.
                    SequenceEqual(pAnswerJyoutaiList[J].YokoSumArr) == false)
                    continue;
                if (pAnswerJyoutaiList[I].TateSumArr.
                    SequenceEqual(pAnswerJyoutaiList[J].TateSumArr) == false)
                    continue;

                IsOnlyOne = false;
                break;
            }
            if (IsOnlyOne) {
                //横方向での○の数の(広義の)単調減少を解除し、場合の数を調整
                int[] wkArr = pAnswerJyoutaiList[I].YokoSumArr;
                int wkPatternCnt = DeriveKaijyou(wkArr.Length);
                foreach (int EachCnt in wkArr.GroupBy(X => X).Select(X => X.Count())) {
                    wkPatternCnt /= DeriveKaijyou(EachCnt);
                }
                WillReturn += wkPatternCnt;
            }
        }
        return WillReturn;
    }

    //階乗を求める
    static int DeriveKaijyou(int pTarget)
    {
        int WillReturn = 1;
        for (int I = 2; I <= pTarget; I++)
            WillReturn *= I;
        return WillReturn;
    }

    //盤面を出力
    static void PrintBan(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();

        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

解は6902通り。経過時間=00:00:25.2248433

解説

○と×を深さ優先探索で敷き詰めてます。

横方向での○の数を(広義の)単調減少とし、
最後に、同じものを含む場合の順列の公式で、場合の数を調整してます。