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

Cマガ電脳クラブ(第109回) クロススクエアドナンバーパズル

問題

普通のクロスワードパズルでは、白マスに文字を入れて、
タテおよびヨコに2マス以上連続してできた単語が意味のあるものになっていなければならない。

このクロススクエアドナンバーパズルではちょっと違って、各マスには数字を入れる。
そして、タテおよびヨコに並んだ2桁以上の数を見ると、
すべて相異なる平方数(ある整数を2乗した数)になっていなければならないのだ。

Fig.1の白マスをすべて埋めて完成してほしい。
なお、各平方数の最上位の数字には0(ゼロ)は使えない。
また、タテの数は上から下へ、ヨコの数は左から右へ読むことはいうまでもない。

Fig.1 クロススクエアドナンバーパズル


ソース

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

class Program
{
    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal Char[,] BanArr;
        internal List<int> UsedKouhoNumList;
    }

    const int UB_X = 6 - 1;
    const int UB_Y = 6 - 1;

    static int[] AllKouhoNumArr;

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

        //埋める候補の数値の配列を作成
        AllKouhoNumArr = DeriveAllKouhoNumArr();

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrX = WillPush.CurrY = 0;
        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.BanArr[4, 0] = '■';
        WillPush.BanArr[2, 1] = '■';
        WillPush.BanArr[5, 2] = '■';
        WillPush.BanArr[0, 3] = '■';
        WillPush.BanArr[3, 4] = '■';
        WillPush.BanArr[1, 5] = '■';
        WillPush.UsedKouhoNumList = new List<int>();
        stk.Push(WillPush);

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

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

            //最終行を超えた場合
            if (Popped.CurrY > UB_Y) {
                Console.WriteLine("解を発見");
                PrintBan(Popped.BanArr);
                continue;
            }

            if (Popped.BanArr[Popped.CurrX, Popped.CurrY] == '■') {
                WillPush.CurrX = Popped.CurrX + 1;
                WillPush.CurrY = Popped.CurrY;
                WillPush.BanArr = Popped.BanArr;
                WillPush.UsedKouhoNumList = Popped.UsedKouhoNumList;
                stk.Push(WillPush);
                continue;
            }

            //横に埋める数値の桁数を求める
            int FillNumKetasuu = DeriveFillNumKetasuu(
                Popped.BanArr, Popped.CurrX, Popped.CurrY);

            //桁数を引数として平方数を抽出
            int[] KouhoNumArr = DeriveKouhoNumArr(FillNumKetasuu);

            foreach (int EachKouho in KouhoNumArr) {
                //2桁以上で使用済の数値ならNG
                if (EachKouho >= 10 && Popped.UsedKouhoNumList.Contains(EachKouho))
                    continue;

                WillPush.CurrX = Popped.CurrX + FillNumKetasuu;
                WillPush.CurrY = Popped.CurrY;
                WillPush.BanArr = (char[,])Popped.BanArr.Clone();

                string FillStr = EachKouho.ToString();
                for (int I = 0; I <= FillStr.Length - 1; I++) {
                    WillPush.BanArr[Popped.CurrX + I, Popped.CurrY] = FillStr[I];
                }

                WillPush.UsedKouhoNumList = new List<int>(Popped.UsedKouhoNumList);
                WillPush.UsedKouhoNumList.Add(EachKouho);

                bool WillEdakiri;
                TateCheck(out WillEdakiri, WillPush);
                if (WillEdakiri == false)
                    stk.Push(WillPush);
            }
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    //埋める候補の数値の配列を作成
    static int[] DeriveAllKouhoNumArr()
    {
        var HeihouSuuSet = new HashSet<int>();
        for (int I = 0; I * I <= 99999; I++) {
            HeihouSuuSet.Add(I * I);//平方数
        }
        for (int I = 0; I <= 9; I++)
            HeihouSuuSet.Add(I); //1桁の数値

        return HeihouSuuSet.OrderBy(X => X).ToArray();
    }

    //横に埋める数値の桁数を求める
    static int DeriveFillNumKetasuu(char[,] pBanArr, int pCurrX, int pCurrY)
    {
        int WillReturn = 0;
        for (int LoopX = pCurrX; LoopX <= UB_X; LoopX++) {
            if (pBanArr[LoopX, pCurrY] == '■')
                break;
            WillReturn++;
        }
        return WillReturn;
    }

    //桁数を引数として埋める数値の候補を抽出
    static int[] DeriveKouhoNumArr(int pKetasuu)
    {
        Predicate<int> IsOK = pInt =>
        {
            if (pKetasuu == 1)
                return 0 <= pInt && pInt <= 9;
            if (pKetasuu == 2)
                return 10 <= pInt && pInt <= 99;
            if (pKetasuu == 3)
                return 100 <= pInt && pInt <= 999;
            if (pKetasuu == 4)
                return 1000 <= pInt && pInt <= 9999;
            if (pKetasuu == 5)
                return 10000 <= pInt && pInt <= 99999;
            return 100000 <= pInt && pInt <= 999999;
        };
        return Array.FindAll(AllKouhoNumArr, X => IsOK(X));
    }

    //縦のラインでのチェックと枝切り
    static void TateCheck(out bool pWillEdakiri, JyoutaiDef pWillPush)
    {
        var TateLineStrList = new List<string>();

        if (pWillPush.CurrX == 6 && pWillPush.CurrY == 1) {
            TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 5, 0, 1));
        }
        if (pWillPush.CurrX == 5 && pWillPush.CurrY == 2) {
            TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 0, 0, 2));
        }
        if (pWillPush.CurrX == 6 && pWillPush.CurrY == 3) {
            TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 3, 0, 3));
        }
        if (pWillPush.CurrX == 3 && pWillPush.CurrY == 4) {
            TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 1, 0, 4));
        }
        if (pWillPush.CurrX == 1 && pWillPush.CurrY == 5) {
            TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 0, 4, 5));
        }
        if (pWillPush.CurrX == 6 && pWillPush.CurrY == 5) {
            TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 2, 2, 5));
        }
        if (pWillPush.CurrX == 6 && pWillPush.CurrY == 5) {
            TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 4, 1, 5));
        }
        if (pWillPush.CurrX == 6 && pWillPush.CurrY == 5) {
            TateLineStrList.Add(DeriveTateLineStrNum(pWillPush.BanArr, 5, 3, 5));
        }

        pWillEdakiri = false;
        foreach (string EachTateLineStr in TateLineStrList) {
            //前ゼロはNG
            if (EachTateLineStr != "0" && EachTateLineStr.StartsWith("0")) {
                pWillEdakiri = true; return;
            }

            int TateLineNum = int.Parse(EachTateLineStr);

            //使用可な数値でなければNG
            if (Array.BinarySearch(AllKouhoNumArr, TateLineNum) < 0) {
                pWillEdakiri = true; return;
            }

            //2桁以上で使用済の数値ならNG
            if (TateLineNum >= 10 && pWillPush.UsedKouhoNumList.Contains(TateLineNum)) {
                pWillEdakiri = true; return;
            }

            pWillPush.UsedKouhoNumList.Add(TateLineNum);
        }
    }

    //開始座標から終点座標までを縦に走査し、数値を抽出する
    static string DeriveTateLineStrNum(char[,] pBanArr,
                                       int pCurrX, int pStaY, int pEndY)
    {
        var sb = new System.Text.StringBuilder();
        for (int LoopY = pStaY; LoopY <= pEndY; LoopY++) {
            sb.Append(pBanArr[pCurrX, LoopY]);
        }
        return sb.ToString();
    }

    //盤面を出力
    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++) {
                char wkChar = pBanArr[X, Y];
                if (wkChar == '■') sb.Append('■');
                else sb.Append((char)('0' + wkChar - '0'));
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}


実行結果

解を発見
3249■4
64■289
10816■
■24649
256■36
5■4761

経過時間=00:01:49.1044238


解説

平方数を横方向に、順番に敷き詰めつつ、
縦方向の数値が確定したら、有効な数値かをチェックしてます。