24-08 クロット

問題

ニコリのクロットを解きます。

例題と答え
    

1 盤面のいくつかのマスを黒くぬりましょう。

2 丸の中の数字は、その数字の入っているマスにタテヨコに隣り合うマスが含まれる、
  タテヨコでひとつながりになった黒マスの個数の合計を表します。
  数字のない丸では、いくつの黒マスになるかわかりません。

3 丸のあるマスを黒くぬってはいけません。

ソース

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

class Program
{
    static int UB_X;
    static int UB_Y;

    struct PointDef
    {
        internal int X;
        internal int Y;
    }

    struct JyoutaiDef
    {
        internal char[,] BanArr;
        internal int CurrP;
    }

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

        //盤面定義
        //黒マスは*
        //白マスは半角空白
        //白マス(確定)は/
        //数字のある丸は、0から9とAからZの36進数
        //数字のない丸は?

        char[,] Q01Arr = {{'2',' ',' ',' ',},
                          {'0','3',' ','?',},
                          {' ',' ',' ','1',},
                          {' ','1',' ',' ',}};

        char[,] WkArr = Q01Arr;

        UB_X = WkArr.GetUpperBound(1);
        UB_Y = WkArr.GetUpperBound(0);

        char[,] QuestionArr = new char[UB_X + 1, UB_Y + 1];
        for (int X = 0; X <= UB_X; X++)
            for (int Y = 0; Y <= UB_Y; Y++)
                QuestionArr[X, Y] = WkArr[Y, X];

        PointDef[] SortdSuujiMasuArr = DeriveSortdSuujiMasuArr(QuestionArr);

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanArr = QuestionArr;
        WillPush.CurrP = 0;
        stk.Push(WillPush);

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

            //最終的な解判定
            if (CheckBan(Popped.BanArr, true)) {
                Console.WriteLine("解を発見。経過時間={0}", sw.Elapsed);
                PrintAnswer(Popped.BanArr);
                return;
            }

            PointDef CurrPoint = SortdSuujiMasuArr[Popped.CurrP];
            char CurrMasu = Popped.BanArr[CurrPoint.X, CurrPoint.Y];

            //必要な連結黒マス数
            int NeedRenketuBlackCnt = StrToDec(CurrMasu);

            //数字マスに隣接した黒マスの座標List
            List<PointDef> RinsetuBlackList =
                DeriveRinsetuMasuList(Popped.BanArr, CurrPoint.X, CurrPoint.Y, '*');

            //数字マスに連結した黒マスの座標List
            List<PointDef> RenketuBlackList =
                DeriveRenketuMasuList(Popped.BanArr, RinsetuBlackList, '*', NeedRenketuBlackCnt + 1);

            //現在の連結黒マス数
            int CurrRenketuBlackCnt = RenketuBlackList.Count;

            //現在の数字マスを黒マスとしてAdd
            RenketuBlackList.Add(new PointDef() { X = CurrPoint.X, Y = CurrPoint.Y });

            //連結黒マスに、隣接した白マスの座標List
            List<PointDef> RenketuWhiteListAll = new List<PointDef>();

            foreach (var EachPoint in RenketuBlackList) {
                List<PointDef> RenketuWhiteListEach =
                    DeriveRinsetuMasuList(Popped.BanArr, EachPoint.X, EachPoint.Y, ' ');

                RenketuWhiteListAll.AddRange(RenketuWhiteListEach);
            }

            //現在の連結黒マス数 > 必要な連結黒マス数の場合は、Pushする前に枝切り済

            //現在の連結黒マス数 = 必要な連結黒マス数なら、Push処理
            if (CurrRenketuBlackCnt == NeedRenketuBlackCnt) {
                WillPush.BanArr = (char[,])Popped.BanArr.Clone();

                //連結した白マスを、確定白マスに設定
                RenketuWhiteListAll.ForEach(A => WillPush.BanArr[A.X, A.Y] = '/');

                WillPush.CurrP = Popped.CurrP + 1;
                stk.Push(WillPush);
                continue;
            }

            //現在の連結黒マス数 < 必要な連結黒マス数なら、黒マスを配置

            //黒マス配置不可な白マスを確定白マスに設定
            for (int I = RenketuWhiteListAll.Count - 1; 0 <= I; I--) {
                PointDef wkPoint = RenketuWhiteListAll[I];

                char[,] wkBan = (char[,])Popped.BanArr.Clone();
                wkBan[wkPoint.X, wkPoint.Y] = '*';

                if (CheckBan(wkBan, false) == false) {
                    Popped.BanArr[wkPoint.X, wkPoint.Y] = '/';
                    RenketuWhiteListAll.RemoveAt(I);
                }
            }

            //黒マスを配置
            for (int I = 0; I <= RenketuWhiteListAll.Count - 1; I++) {
                PointDef wkPoint1 = RenketuWhiteListAll[I];

                WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                WillPush.BanArr[wkPoint1.X, wkPoint1.Y] = '*';

                //黒マスを配置しなかった白マスは、確定白マスに設定しておく
                for (int J = 0; J <= I - 1; J++) {
                    PointDef wkPoint2 = RenketuWhiteListAll[J];
                    WillPush.BanArr[wkPoint2.X, wkPoint2.Y] = '/';
                }

                WillPush.CurrP = Popped.CurrP;
                stk.Push(WillPush);
            }
        }
    }

    //小さい数字の黒マスから埋めていくので、
    //必要黒マス数でソートした座標の配列を返す
    static PointDef[] DeriveSortdSuujiMasuArr(char[,] pQuestionArr)
    {
        var WillReturnList = new List<PointDef>();

        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                char CurrMasu = pQuestionArr[LoopX, LoopY];
                //黒マスを埋める必要があるマスの場合
                if ('0' <= CurrMasu && CurrMasu <= '9' ||
                    'A' <= CurrMasu && CurrMasu <= 'Z') {
                    WillReturnList.Add(new PointDef() { X = LoopX, Y = LoopY });
                }
            }
        }

        var tmp1 = WillReturnList.OrderBy(A => StrToDec(pQuestionArr[A.X, A.Y]));
        var tmp2 = tmp1.ThenBy(A => A.X * A.X + A.Y * A.Y);
        return tmp1.ToArray();
    }

    //char型を10進数に変換
    static int StrToDec(char pStr)
    {
        if (pStr == ' ') return 0;
        if ('A' <= pStr) return 10 + pStr - 'A';
        return (int)(pStr - '0');
    }

    //pIsAnswerHanteiがTrueなら、盤面の解判定の結果を返す
    //pIsAnswerHanteiがFalseなら、盤面の有効判定の結果を返す
    static bool CheckBan(char[,] pBanArr, bool pIsAnswerHantei)
    {
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                char CurrMasu = pBanArr[X, Y];

                //黒マスの数が指定されてる場合
                if ('0' <= CurrMasu && CurrMasu <= '9' ||
                    'A' <= CurrMasu && CurrMasu <= 'Z') {

                    //数字マスに隣接した黒マスか白マスの座標List
                    List<PointDef> RinsetuKouhoList =
                        DeriveRinsetuMasuList(pBanArr, X, Y, 'B');

                    //必要な連結黒マス数
                    int NeedRenketuBlackCnt = StrToDec(CurrMasu);

                    //数字マスに連結した黒マスか白マスの座標List
                    List<PointDef> RenketuKouhoList =
                        DeriveRenketuMasuList(pBanArr, RinsetuKouhoList, 'B', NeedRenketuBlackCnt);

                    //数字マスに隣接した黒マスの座標List
                    List<PointDef> RinsetuBlackList =
                        DeriveRinsetuMasuList(pBanArr, X, Y, '*');

                    //数字マスに連結した黒マスの座標List
                    List<PointDef> RenketuBlackList =
                        DeriveRenketuMasuList(pBanArr, RinsetuBlackList, '*', NeedRenketuBlackCnt + 1);

                    //確定白マスにより、必要黒マス数を満たせなくなった場合
                    if (NeedRenketuBlackCnt > RenketuKouhoList.Count)
                        return false;

                    //黒マス必要数 < 現在の黒マス数 な場合
                    if (NeedRenketuBlackCnt < RenketuBlackList.Count)
                        return false;

                    //黒マス数が不一致だったら、解判定ではNG
                    if (pIsAnswerHantei && RenketuBlackList.Count != NeedRenketuBlackCnt)
                        return false;
                }
            }
        }
        return true;
    }

    //指定座標に隣接した、指定マスの、座標Listを返す
    static List<PointDef> DeriveRinsetuMasuList(char[,] pBanArr, int pBaseX, int pBaseY,
                                                char pMasuKind)
    {
        var WillReturnList = new List<PointDef>();

        Action<int, int> wkAct = (pX, pY) =>
        {
            //指定マスでない場合
            if (pMasuKind == ' ' && pBanArr[pX, pY] != ' ') return;
            if (pMasuKind == '*' && pBanArr[pX, pY] != '*') return;
            if (pMasuKind == 'B' && pBanArr[pX, pY] != ' ' && pBanArr[pX, pY] != '*') return;

            WillReturnList.Add(new PointDef() { X = pX, Y = pY });
        };

        if (pBaseX > 0) wkAct(pBaseX - 1, pBaseY);
        if (pBaseX < UB_X) wkAct(pBaseX + 1, pBaseY);
        if (pBaseY > 0) wkAct(pBaseX, pBaseY - 1);
        if (pBaseY < UB_Y) wkAct(pBaseX, pBaseY + 1);

        return WillReturnList;
    }

    //指定マスの座標Listを引数として、連結した指定マスを含めた、座標Listを返す
    static List<PointDef> DeriveRenketuMasuList(char[,] pBanArr, List<PointDef> pRinsetuBlackList,
                                                char pMasuKind, int pJyougen)
    {
        var VisitedList = new List<PointDef>(); //訪問済座標のセット

        var stk = new Stack<PointDef>();
        PointDef WillPush;

        Action<int, int> PushSyori = (pNewX, pNewY) =>
        {
            //指定マスでない場合
            if (pMasuKind == ' ' && pBanArr[pNewX, pNewY] != ' ') return;
            if (pMasuKind == '*' && pBanArr[pNewX, pNewY] != '*') return;
            if (pMasuKind == 'B' && pBanArr[pNewX, pNewY] != ' ' && pBanArr[pNewX, pNewY] != '*') return;

            //訪問済なら再訪できない
            if (VisitedList.Exists(A => A.X == pNewX && A.Y == pNewY))
                return;
            VisitedList.Add(new PointDef() { X = pNewX, Y = pNewY });

            WillPush.X = pNewX;
            WillPush.Y = pNewY;
            stk.Push(WillPush);
        };

        foreach (PointDef EachStaPoint in pRinsetuBlackList) {
            PushSyori(EachStaPoint.X, EachStaPoint.Y);

            while (stk.Count > 0 && VisitedList.Count < pJyougen) {
                PointDef Popped = stk.Pop();

                if (Popped.X > 0) PushSyori(Popped.X - 1, Popped.Y); //左に移動
                if (Popped.X < UB_X) PushSyori(Popped.X + 1, Popped.Y); //右に移動
                if (Popped.Y > 0) PushSyori(Popped.X, Popped.Y - 1); //上に移動
                if (Popped.Y < UB_Y) PushSyori(Popped.X, Popped.Y + 1); //下に移動
            }
        }
        return VisitedList;
    }

    //解を出力
    static void PrintAnswer(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 CurrMasu = pBanArr[X, Y];
                if (CurrMasu == '/') sb.Append(' ');
                else sb.Append(CurrMasu);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

解を発見。経過時間=00:00:00.0451554
2**
03 ?
 * 1
 1 *

追加問題02 パズルBox12の05問目

char[,] Q02Arr = {{' ','2','1','2',' ','3',' ',' ',' ','1'},
                  {' ',' ',' ',' ',' ','3',' ',' ',' ','2'},
                  {' ',' ',' ','?',' ',' ',' ','1',' ',' '},
                  {'2',' ',' ','1',' ',' ','1',' ',' ',' '},
                  {'2',' ',' ',' ',' ','1',' ',' ',' ','5'},
                  {'2',' ',' ',' ','1',' ',' ',' ',' ','3'},
                  {' ',' ',' ','2',' ',' ','1',' ',' ','1'},
                  {' ',' ','1',' ',' ',' ','?',' ',' ',' '},
                  {'1',' ',' ',' ','?',' ',' ',' ',' ',' '},
                  {'?',' ',' ',' ','2',' ','1','2','1',' '}};

解説

UnionFindのアルゴリズムで、隣接したマスを列挙してます。