Cマガ電脳クラブ(第089回) 四を聞いて二十五を知る

問題

Fig.1のような5×5の盤がある。
この各マスすべてにA、B、C、D、Eのどれか1文字を置いて、
「縦5本横5本斜め2本 (Fig.1の点線) の線上に同じ文字がこないようにする」のが今回の条件だ。

さて、いまFig.2のように、A、B、C、Dをそれぞれ1文字ずつ置いた。
そしてこれを元に前述の条件を満たすようにほかのマスにも置いてみると、
Fig.3のようになり、これ以外にはなかった。

このように、盤全体の配置がただひとつ決まる、
最初に置くA、B、C、Dという4つの文字の置き方は何通りあるか。
もちろん、全体の回転・鏡像、およびA、B、C、Dの場所をお互いに入れ替えたものは別の解とはしない。

          

ソース

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

class Program
{
    const int UB = 5 - 1;

    struct AnswerKouhoDef
    {
        internal char[,] BanArr;
        internal int HashVal;
    }

    static void Main()
    {
        //A,B,C,Dの配置候補を求める
        List<AnswerKouhoDef> AnswerKouhoList = DeriveAnswerKouhoList();

        Console.WriteLine("回転除外前の配置候補は{0}通り", AnswerKouhoList.Count);

        //回転した配置を除外する
        RemoveKaiten(AnswerKouhoList);
        Console.WriteLine("回転除外後の配置候補は{0}通り", AnswerKouhoList.Count);

        //ABCDを盤に埋める
        AnswerKouhoList.ForEach(X => ExecFillChar(X.BanArr));

        int AnswerCnt = AnswerKouhoList.Count(X => HasUniqAnswer(X.BanArr));
        Console.WriteLine("答えは{0}通り", AnswerCnt);
    }

    struct JyoutaiDef1
    {
        internal int SelectedCnt;
        internal int CurrX;
        internal int CurrY;
        internal char[,] BanArr;
    }

    //A,B,C,Dの配置候補を求める
    static List<AnswerKouhoDef> DeriveAnswerKouhoList()
    {
        var WillReturn = new List<AnswerKouhoDef>();

        var stk = new Stack<JyoutaiDef1>();
        JyoutaiDef1 WillPush;
        WillPush.SelectedCnt = 0;
        WillPush.CurrX = WillPush.CurrY = 0;
        WillPush.BanArr = new char[UB + 1, UB + 1];
        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                WillPush.BanArr[LoopX, LoopY] = ' ';
            }
        }
        stk.Push(WillPush);

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

            //クリア判定
            if (Popped.SelectedCnt == 4) {
                AnswerKouhoDef WillAdd;
                WillAdd.BanArr = Popped.BanArr;
                WillAdd.HashVal = GetHash(WillAdd.BanArr);
                WillReturn.Add(WillAdd);
                continue;
            }

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

            //最終行を超えた場合
            if (Popped.CurrY > UB) continue;

            //マスを選択する経路
            WillPush.SelectedCnt = Popped.SelectedCnt + 1;
            WillPush.CurrX = Popped.CurrX + 1;
            WillPush.CurrY = Popped.CurrY;
            WillPush.BanArr = (char[,])Popped.BanArr.Clone();
            WillPush.BanArr[Popped.CurrX, Popped.CurrY] = '*';
            stk.Push(WillPush);

            //マスを選択しない経路
            WillPush.SelectedCnt = Popped.SelectedCnt;
            WillPush.CurrX = Popped.CurrX + 1;
            WillPush.CurrY = Popped.CurrY;
            WillPush.BanArr = Popped.BanArr;
            stk.Push(WillPush);
        }
        return WillReturn;
    }

    //回転した配置を除外
    static void RemoveKaiten(List<AnswerKouhoDef> pTargetList)
    {
        for (int I = pTargetList.Count - 1; I >= 0; I--) {
            int[] KaitenHashArr = GetKaitenHashArr(pTargetList[I].BanArr);
            for (int J = 0; J <= I - 1; J++) {
                if (Array.IndexOf(KaitenHashArr, pTargetList[J].HashVal) >= 0) {
                    pTargetList.RemoveAt(I);
                    break;
                }
            }
        }
    }

    //ハッシュ値を求める
    static int GetHash(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                sb.Append(pBanArr[X, Y] == '*' ? 1 : 0);
            }
        }
        return Convert.ToInt32(sb.ToString(), 2);
    }

    //回転も含めたハッシュ値を求める
    static int[] GetKaitenHashArr(char[,] pBanArr)
    {
        var sbArr = new System.Text.StringBuilder[8];
        for (int I = 0; I <= sbArr.GetUpperBound(0); I++)
            sbArr[I] = new System.Text.StringBuilder();

        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                sbArr[0].Append(pBanArr[X, Y] == '*' ? 1 : 0);
                sbArr[1].Append(pBanArr[UB - X, Y] == '*' ? 1 : 0);
                sbArr[2].Append(pBanArr[UB - X, UB - Y] == '*' ? 1 : 0);
                sbArr[3].Append(pBanArr[X, UB - Y] == '*' ? 1 : 0);
                sbArr[4].Append(pBanArr[Y, X] == '*' ? 1 : 0);
                sbArr[5].Append(pBanArr[UB - Y, X] == '*' ? 1 : 0);
                sbArr[6].Append(pBanArr[UB - Y, UB - X] == '*' ? 1 : 0);
                sbArr[7].Append(pBanArr[Y, UB - X] == '*' ? 1 : 0);
            }
        }
        var WillReturn = new List<int>();
        for (int I = 0; I <= sbArr.GetUpperBound(0); I++)
            WillReturn.Add(Convert.ToInt32(sbArr[I].ToString(), 2));
        return WillReturn.ToArray();
    }

    //ABCDを盤に埋める
    static void ExecFillChar(char[,] pBanArr)
    {
        char FillChar = 'A';
        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                if (pBanArr[LoopX, LoopY] == ' ')
                    continue;
                pBanArr[LoopX, LoopY] = FillChar++;
            }
        }
    }

    struct JyoutaiDef2
    {
        internal int CurrX;
        internal int CurrY;
        internal char[,] BanArr;
    }

    //盤面を引数として、ユニーク解を持つかを調べる
    static bool HasUniqAnswer(char[,] pBanArr)
    {
        int HaitiCnt = 0;
        var stk = new Stack<JyoutaiDef2>();
        JyoutaiDef2 WillPush;
        WillPush.CurrX = WillPush.CurrY = 0;
        WillPush.BanArr = pBanArr;
        stk.Push(WillPush);

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

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

            //最終行を超えた場合
            if (Popped.CurrY > UB) {
                HaitiCnt++;
                //Console.WriteLine("{0}個目の解を発見", HaitiCnt);
                //PrintAnswer(Popped.BanArr);
                if (HaitiCnt == 2) break;
                continue;
            }

            //現在のマス目が空白の場合は、マス目を埋める必要あり
            if (Popped.BanArr[Popped.CurrX, Popped.CurrY] == ' ') {
                for (char I = 'A'; I <= 'E'; I++) {
                    WillPush.CurrX = Popped.CurrX + 1;
                    WillPush.CurrY = Popped.CurrY;
                    WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                    WillPush.BanArr[Popped.CurrX, Popped.CurrY] = I;
                    if (IsValid(WillPush.BanArr, Popped.CurrX, Popped.CurrY))
                        stk.Push(WillPush);
                }
            }
            //現在のマス目が空白でない場合は、マス目を埋めない経路のPush
            else {
                WillPush.CurrX = Popped.CurrX + 1;
                WillPush.CurrY = Popped.CurrY;
                WillPush.BanArr = Popped.BanArr;
                stk.Push(WillPush);
            }
        }
        return HaitiCnt == 1;
    }

    //座標を引数として、既存の文字と重複するならFalseを返す
    static bool IsValid(char[,] pBanArr, int pTargetX, int pTargetY)
    {
        char CurrChar = pBanArr[pTargetX, pTargetY];

        //上チェック
        for (int Y = pTargetY - 1; 0 <= Y; Y--) {
            if (pBanArr[pTargetX, Y] == CurrChar) return false;
        }

        //下チェック
        for (int Y = pTargetY + 1; Y <= UB; Y++) {
            if (pBanArr[pTargetX, Y] == CurrChar) return false;
        }

        //左チェック
        for (int X = pTargetX - 1; 0 <= X; X--) {
            if (pBanArr[X, pTargetY] == CurrChar) return false;
        }

        //右チェック
        for (int X = pTargetX + 1; X <= UB; X++) {
            if (pBanArr[X, pTargetY] == CurrChar) return false;
        }

        if (pTargetX == pTargetY) {
            //左上チェック
            for (int X = pTargetX - 1, Y = pTargetY - 1;
                 0 <= X && X <= UB && 0 <= Y && Y <= UB; X--, Y--) {
                if (pBanArr[X, Y] == CurrChar) return false;
            }

            //右下チェック
            for (int X = pTargetX + 1, Y = pTargetY + 1;
                 0 <= X && X <= UB && 0 <= Y && Y <= UB; X++, Y++) {
                if (pBanArr[X, Y] == CurrChar) return false;
            }
        }

        if (pTargetX + pTargetY == UB) {
            //左下チェック
            for (int X = pTargetX - 1, Y = pTargetY + 1;
                 0 <= X && X <= UB && 0 <= Y && Y <= UB; X--, Y++) {
                if (pBanArr[X, Y] == CurrChar) return false;
            }

            //右上チェック
            for (int X = pTargetX + 1, Y = pTargetY - 1;
                 0 <= X && X <= UB && 0 <= Y && Y <= UB; X++, Y--) {
                if (pBanArr[X, Y] == CurrChar) return false;
            }
        }
        return true;
    }

    //解を出力
    static void PrintAnswer(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());
    }
}

実行結果

回転除外前の配置候補は12650通り
回転除外後の配置候補は1666通り
答えは246通り

解説

4箇所の選び方は、25C4で12650通りしかないので、
ナイーブに調べてます。