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

24-31 橋をかけろ

問題

ニコリの橋をかけろを解きます。

例題と答え
          

1 数字と数字の間にタテヨコに橋をかけて(線を引いて)、全体をひとつながりにしましょう。

2 数字は、その数字につながる橋の本数を表します。

3 橋は1カ所に2本までかけられます。

4 橋を交差させたり、ナナメにかけたり、数字を飛び越えてかけたりしてはいけません。


ソース

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

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

    //数値情報の構造体
    struct NumInfoDef
    {
        internal PointDef Point; //数値の座標
        internal LinkInfoDef[] LinkInfoArr; //リンク情報の配列
    }
    static NumInfoDef[] mNumInfoArr; //数値情報の配列

    //リンク情報の構造体
    struct LinkInfoDef
    {
        internal PointDef StaPos; //始点の座標
        internal PointDef EndPos; //終点の座標
        internal int HeniX; //変位ベクトルのX成分
        internal int HeniY; //変位ベクトルのY成分
    }

    static char[,] mQuestionArr;
    static int mNodeCnt;
    static int UB_X;
    static int UB_Y;

    //問題を定義
    static void QuestionDef()
    {
        string[] Q01Arr ={"4□4□□2□□3",
                          "□□□□□□□□□",
                          "6□8□4□□1□",
                          "□□□□□□1□3",
                          "□□2□2□□1□",
                          "4□□3□2□□□",
                          "□□□□□□2□3",
                          "□1□5□4□□□",
                          "3□3□2□3□2"};

        string[] wkArr = Q01Arr;

        UB_X = wkArr[0].Length - 1;
        UB_Y = wkArr.GetUpperBound(0);

        //半角文字で盤面を保持
        mQuestionArr = new char[UB_X + 1, UB_Y + 1];
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                char CurrChar = wkArr[Y][X];
                if (CurrChar == '□') mQuestionArr[X, Y] = ' ';
                else {
                    mQuestionArr[X, Y] = (char)('0' + CurrChar - '0');
                    mNodeCnt++;
                }
            }
        }
    }

    static void Main()
    {
        //問題を定義
        QuestionDef();

        //第1フェーズ 数値情報を作成する
        CreateNumInfoArr();

        //デバッグ用の数値情報を出力
        //DebugPrintNumInfo();

        char[,] wkBanArr = (char[,])mQuestionArr.Clone();

        //第2フェーズ 確定探索
        ExecKakuteiTansaku(wkBanArr);

        //第3フェーズ 確定探索付の深さ優先探索
        ExecDFS(wkBanArr);
    }

    //第1フェーズ 数値情報を作成する
    static void CreateNumInfoArr()
    {
        var NumInfoList = new List<NumInfoDef>();

        for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
            for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                //数値マスでない場合
                if (mQuestionArr[LoopX, LoopY] == ' ') continue;

                NumInfoDef wkNumInfo;
                PointDef CurrPoint = new PointDef() { X = LoopX, Y = LoopY };
                wkNumInfo.Point = CurrPoint;
                wkNumInfo.LinkInfoArr = DeriveLinkInfoArr(CurrPoint);
                NumInfoList.Add(wkNumInfo);
            }
        }
        mNumInfoArr = NumInfoList.ToArray();
    }

    //数値マスの座標を引数として、リンク情報の配列を返す
    static LinkInfoDef[] DeriveLinkInfoArr(PointDef pNumPos)
    {
        var LinkInfoList = new List<LinkInfoDef>();

        Action<int, int> AddAct = (pHeniX, pHeniY) =>
        {
            LinkInfoDef wkLinkInfo;
            int LoopX = pNumPos.X, LoopY = pNumPos.Y;
            LoopX += pHeniX; LoopY += pHeniY;
            wkLinkInfo.StaPos = new PointDef() { X = LoopX, Y = LoopY };
            wkLinkInfo.HeniX = pHeniX;
            wkLinkInfo.HeniY = pHeniY;

            while (true) {
                //範囲外の場合
                if (LoopX < 0 || UB_X < LoopX) break;
                if (LoopY < 0 || UB_Y < LoopY) break;

                //リンクを貼れる場合
                if ('1' <= mQuestionArr[LoopX, LoopY]
                 && mQuestionArr[LoopX, LoopY] <= '8') {
                    wkLinkInfo.EndPos = new PointDef() { X = LoopX, Y = LoopY };
                    LinkInfoList.Add(wkLinkInfo);
                    break;
                }
                LoopX += pHeniX; LoopY += pHeniY;
            }
        };

        AddAct(0, -1); AddAct(0, 1);
        AddAct(-1, 0); AddAct(1, 0);
        return LinkInfoList.ToArray();
    }

    //デバッグ用の数値情報を出力
    static void DebugPrintNumInfo()
    {
        for (int I = 0; I <= mNumInfoArr.GetUpperBound(0); I++) {
            Console.WriteLine("■■■■■■■■■■■■■");
            Console.WriteLine("{0}個目の数値情報", I + 1);
            Console.WriteLine("Point=({0},{1})", mNumInfoArr[I].Point.X, mNumInfoArr[I].Point.Y);

            Console.WriteLine("リンク情報の配列 ");
            foreach (LinkInfoDef EachLinkInfo in mNumInfoArr[I].LinkInfoArr) {
                Console.WriteLine("始点({0},{1}),終点({2},{3})",
                    EachLinkInfo.StaPos.X, EachLinkInfo.StaPos.Y,
                    EachLinkInfo.EndPos.X, EachLinkInfo.EndPos.Y);
            }
            Console.WriteLine();
        }
    }

    //第2フェーズ 確定探索を行い有効な盤面かを返す
    static bool ExecKakuteiTansaku(char[,] pBanArr)
    {
        while (true) {
            char[,] PrevBanArr = (char[,])pBanArr.Clone();

            //確定探索1 ノード間のリンクを貼れることが確定する場合
            if (KakuteiTansaku1(pBanArr) == false) return false;

            //確定探索で確定するマスがなくなったらBreak
            if (pBanArr.Cast<char>().SequenceEqual(PrevBanArr.Cast<char>())) break;
        }
        return true;
    }

    //確定探索1 ノード間のリンクを貼れることが確定する場合
    //戻り値として、有効な盤面かを返す
    static bool KakuteiTansaku1(char[,] pBanArr)
    {
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                bool WillContinue = true;
                if ('1' <= pBanArr[LoopX, LoopY] && pBanArr[LoopX, LoopY] <= '8')
                    WillContinue = false;
                if (WillContinue) continue;

                //数値の座標を引数として、設置できるリンクのListを返す
                PointDef CurrPoint = new PointDef() { X = LoopX, Y = LoopY };
                int StaRestCnt = pBanArr[LoopX, LoopY] - '0';
                List<CanSetLinkInfoDef> CanSetLinkList =
                    DeriveCanSetLinkList(pBanArr, StaRestCnt, CurrPoint);

                //閉路ができるリンクをRemove
                HeiroRemove(pBanArr, CanSetLinkList, StaRestCnt, CurrPoint);

                //橋の数の昇順にソートしておく
                CanSetLinkList.Sort((A, B) => A.LinkCnt.CompareTo(B.LinkCnt));

                //座標ごとの最大値を求めておく
                var MaxDict = new Dictionary<string, int>();
                foreach (CanSetLinkInfoDef EachCanSetLink in CanSetLinkList) {
                    PointDef EndPos = EachCanSetLink.LinkInfo.EndPos;
                    string CurrKey = GetHash(EndPos);
                    int CurrVal;

                    if (MaxDict.TryGetValue(CurrKey, out CurrVal)) {
                        if (CurrVal < EachCanSetLink.LinkCnt)
                            MaxDict[CurrKey] = EachCanSetLink.LinkCnt;
                    }
                    else MaxDict[CurrKey] = EachCanSetLink.LinkCnt;
                }
                int MaxSum = MaxDict.Values.Sum();

                //リンクを引かなければ、解なしになる場合は、リンクを貼る
                //橋の数でソート済なので、1本、2本の順序で調べる
                foreach (CanSetLinkInfoDef EachCanSetLink in CanSetLinkList) {
                    int JyogaiVal = MaxDict[GetHash(EachCanSetLink.LinkInfo.EndPos)];

                    if (StaRestCnt > MaxSum - JyogaiVal) {
                        SetHashi(pBanArr, EachCanSetLink);
                        return true;
                    }
                }

                if (CanSetLinkList.Count == 0) return false;
                if (CanSetLinkList.Count == 1) {
                    SetHashi(pBanArr, CanSetLinkList[0]);
                }
            }
        }
        return true;
    }

    //設置できるリンク情報の構造体
    struct CanSetLinkInfoDef
    {
        internal LinkInfoDef LinkInfo;
        internal int LinkCnt;
    }

    //数値の座標を引数として、設置できるリンクのListを返す
    static List<CanSetLinkInfoDef> DeriveCanSetLinkList(char[,] pBanArr, int pStaRestCnt, PointDef pPoint)
    {
        var WillReturn = new List<CanSetLinkInfoDef>();

        int CurrX = pPoint.X;
        int CurrY = pPoint.Y;

        int wkInd = Array.FindIndex(mNumInfoArr, A => A.Point.X == CurrX && A.Point.Y == CurrY);
        NumInfoDef CurrNumInfo = mNumInfoArr[wkInd];

        foreach (LinkInfoDef EachLinkInfo in CurrNumInfo.LinkInfoArr) {
            WillReturn.AddRange(DeriveCanSetLinkListHelper(pBanArr, pStaRestCnt, EachLinkInfo));
        }
        return WillReturn;
    }

    //リンク情報を引数として、設置できるリンク情報のListを返す
    static List<CanSetLinkInfoDef> DeriveCanSetLinkListHelper(
        char[,] pBanArr, int pStaRestCnt, LinkInfoDef pLinkInfo)
    {
        var WillReturn = new List<CanSetLinkInfoDef>();

        //既に別の橋が引かれていたら引けない
        var NGList = new List<char>();
        //横のリンクなら、縦の橋があってはいけない
        if (Math.Abs(pLinkInfo.HeniX) > 0) NGList.AddRange(new char[] { 'C', 'D' });
        //縦のリンクなら、横の橋があってはいけない
        if (Math.Abs(pLinkInfo.HeniY) > 0) NGList.AddRange(new char[] { 'A', 'B' });

        int CurrX = pLinkInfo.StaPos.X;
        int CurrY = pLinkInfo.StaPos.Y;
        while (true) {
            if (NGList.IndexOf(pBanArr[CurrX, CurrY]) >= 0) {
                return WillReturn;
            }
            CurrX += pLinkInfo.HeniX;
            CurrY += pLinkInfo.HeniY;

            if (CurrX == pLinkInfo.EndPos.X && CurrY == pLinkInfo.EndPos.Y)
                break;
        }

        //既に引かれている橋の数
        int KizonCnt = 0;
        int StaX = pLinkInfo.StaPos.X;
        int StaY = pLinkInfo.StaPos.Y;
        char StaMasu = pBanArr[StaX, StaY];
        if (StaMasu == 'A' || StaMasu == 'C') KizonCnt = 1;
        if (StaMasu == 'B' || StaMasu == 'D') KizonCnt = 2;
        if (KizonCnt == 2) return WillReturn;

        //終点ノードへの残りの橋の数
        int EndRestCnt = pBanArr[pLinkInfo.EndPos.X, pLinkInfo.EndPos.Y] - '0';
        if (EndRestCnt == 0) return WillReturn;

        //橋を2本引ける場合
        if (KizonCnt == 0 && pStaRestCnt >= 2 && EndRestCnt >= 2) {
            CanSetLinkInfoDef WillAdd;
            WillAdd.LinkInfo = pLinkInfo;
            WillAdd.LinkCnt = 2;
            WillReturn.Add(WillAdd);
        }
        //橋を1本引ける場合
        if (pStaRestCnt >= 1 && EndRestCnt >= 1) {
            CanSetLinkInfoDef WillAdd;
            WillAdd.LinkInfo = pLinkInfo;
            WillAdd.LinkCnt = 1;
            WillReturn.Add(WillAdd);
        }
        return WillReturn;
    }

    //閉路ができるリンクをRemove
    static void HeiroRemove(char[,] pBanArr, List<CanSetLinkInfoDef> pCanSetLinkList,
        int pStaRestCnt, PointDef pCurrPoint)
    {
        for (int I = pCanSetLinkList.Count - 1; 0 <= I; I--) {
            if (pStaRestCnt - pCanSetLinkList[I].LinkCnt > 0) continue;

            char[,] CheckBanArr = (char[,])pBanArr.Clone();
            SetHashi(CheckBanArr, pCanSetLinkList[I]);

            int ZeroNodeCnt;
            bool IsRenketuNonZeroNode;
            DeriveZeroNodeShima(CheckBanArr, pCurrPoint,
                out ZeroNodeCnt, out IsRenketuNonZeroNode);

            if (ZeroNodeCnt < mNodeCnt && IsRenketuNonZeroNode == false)
                pCanSetLinkList.RemoveAt(I);
        }
    }

    //設置するリンク情報を引数として、橋を設置
    static void SetHashi(char[,] pBanArr, CanSetLinkInfoDef pCanSetLinkInfo)
    {
        int StaX = pCanSetLinkInfo.LinkInfo.StaPos.X;
        int StaY = pCanSetLinkInfo.LinkInfo.StaPos.Y;
        int EndX = pCanSetLinkInfo.LinkInfo.EndPos.X;
        int EndY = pCanSetLinkInfo.LinkInfo.EndPos.Y;
        int HeniX = pCanSetLinkInfo.LinkInfo.HeniX;
        int HeniY = pCanSetLinkInfo.LinkInfo.HeniY;
        int LinkCnt = pCanSetLinkInfo.LinkCnt;

        char SetChar = '\0';
        bool IsYokoLink = Math.Abs(HeniX) > 0;

        if (LinkCnt == 1 && IsYokoLink) {
            if (pBanArr[StaX, StaY] == ' ') SetChar = 'A';
            if (pBanArr[StaX, StaY] == 'A') SetChar = 'B';
        }
        if (LinkCnt == 1 && IsYokoLink == false) {
            if (pBanArr[StaX, StaY] == ' ') SetChar = 'C';
            if (pBanArr[StaX, StaY] == 'C') SetChar = 'D';
        }
        if (LinkCnt == 2 && IsYokoLink) SetChar = 'B';
        if (LinkCnt == 2 && IsYokoLink == false) SetChar = 'D';

        int LoopX = StaX;
        int LoopY = StaY;
        while (true) {
            pBanArr[LoopX, LoopY] = SetChar;

            LoopX += HeniX;
            LoopY += HeniY;

            if (LoopX == EndX && LoopY == EndY) break;
        }
        //残りの橋の数をデクリメント
        int wkX = StaX - HeniX;
        int wkY = StaY - HeniY;

        for (int I = 1; I <= LinkCnt; I++) {
            pBanArr[wkX, wkY]--;
            pBanArr[EndX, EndY]--;
        }
    }

    struct JyoutaiDefUnionFind
    {
        internal int CurrX;
        internal int CurrY;
    }

    //0のノードの座標を引数として、連結した0ノードの数と、0以外のノードと連結しているかを返す
    static void DeriveZeroNodeShima(char[,] pBanArr, PointDef pZeroNodePos,
        out int pZeroNodeCnt, out bool pIsRenketuNonZeroNode)
    {
        pZeroNodeCnt = 0;
        pIsRenketuNonZeroNode = false;

        var VisitedSet = new HashSet<string>();
        VisitedSet.Add(GetHash(pZeroNodePos));

        var Stk = new Stack<JyoutaiDefUnionFind>();
        JyoutaiDefUnionFind WillPush;
        WillPush.CurrX = pZeroNodePos.X;
        WillPush.CurrY = pZeroNodePos.Y;
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDefUnionFind Popped = Stk.Pop();
            int CurrX = Popped.CurrX;
            int CurrY = Popped.CurrY;

            //0以外のノードと連結していたら終了
            if ('0' < pBanArr[CurrX, CurrY]) {
                pIsRenketuNonZeroNode = true;
                return;
            }
            pZeroNodeCnt++;

            int wkInd = Array.FindIndex(mNumInfoArr, A => A.Point.X == CurrX && A.Point.Y == CurrY);
            foreach (LinkInfoDef EachLinkInfo in mNumInfoArr[wkInd].LinkInfoArr) {
                int StaX = EachLinkInfo.StaPos.X;
                int StaY = EachLinkInfo.StaPos.Y;

                int EndX = EachLinkInfo.EndPos.X;
                int EndY = EachLinkInfo.EndPos.Y;

                bool IsYokoLink = Math.Abs(EachLinkInfo.HeniX) > 0;
                if (IsYokoLink) {
                    if (pBanArr[StaX, StaY] != 'A' && pBanArr[StaX, StaY] != 'B')
                        continue;
                }
                else {
                    if (pBanArr[StaX, StaY] != 'C' && pBanArr[StaX, StaY] != 'D')
                        continue;
                }

                //再訪禁止
                if (VisitedSet.Add(GetHash(EndX, EndY)) == false) {
                    continue;
                }
                WillPush.CurrX = EndX;
                WillPush.CurrY = EndY;
                Stk.Push(WillPush);
            }
        }
    }

    //第3フェーズ 確定探索付の深さ優先探索
    static void ExecDFS(char[,] pBanArr)
    {
        var Stk = new Stack<char[,]>();
        char[,] WillPushBanArr = pBanArr;
        Stk.Push(WillPushBanArr);

        while (Stk.Count > 0) {
            char[,] PoppedBanArr = Stk.Pop();

            //クリア判定
            if (IsClear(PoppedBanArr)) {
                Console.WriteLine("解を発見");
                PrintAnswer(PoppedBanArr);
                return;
            }

            bool WillBreak = false;
            for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
                for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                    bool WillContinue = true;
                    if ('1' <= PoppedBanArr[LoopX, LoopY] && PoppedBanArr[LoopX, LoopY] <= '8')
                        WillContinue = false;

                    if (WillContinue) continue;

                    //数値の座標を引数として、設置できるリンクのListを返す
                    PointDef CurrPoint = new PointDef() { X = LoopX, Y = LoopY };
                    int StaRestCnt = pBanArr[LoopX, LoopY] - '0';
                    List<CanSetLinkInfoDef> CanSetLinkList =
                        DeriveCanSetLinkList(pBanArr, StaRestCnt, CurrPoint);

                    //閉路ができるリンクをRemove
                    HeiroRemove(pBanArr, CanSetLinkList, StaRestCnt, CurrPoint);

                    foreach (CanSetLinkInfoDef EachCanSetLink in CanSetLinkList) {
                        WillPushBanArr = (char[,])PoppedBanArr.Clone();
                        SetHashi(WillPushBanArr, EachCanSetLink);

                        //確定探索を行い、有効な盤面ならPush処理
                        if (ExecKakuteiTansaku(WillPushBanArr)) {
                            Stk.Push(WillPushBanArr);
                        }
                    }
                    WillBreak = true;
                    break;
                }
                if (WillBreak) break;
            }
        }
    }

    //クリア判定
    static bool IsClear(char[,] pBanArr)
    {
        int ZeroX = 0;
        int ZeroY = 0;

        //数値マスは全て0であること
        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {
                if ('1' <= pBanArr[X, Y] && pBanArr[X, Y] <= '8')
                    return false;
                if (pBanArr[X, Y] == '0') {
                    ZeroX = X; ZeroY = Y;
                }
            }
        }

        int ZeroNodeCnt;
        bool IsRenketuNonZeroNode;
        DeriveZeroNodeShima(pBanArr, new PointDef() { X = ZeroX, Y = ZeroY },
            out ZeroNodeCnt, out IsRenketuNonZeroNode);
        return ZeroNodeCnt == mNodeCnt && IsRenketuNonZeroNode == false;
    }

    static string GetHash(int pX, int pY)
    {
        return string.Format("{0},{1}", pX, pY);
    }

    static string GetHash(PointDef pPoint)
    {
        return string.Format("{0},{1}", pPoint.X, pPoint.Y);
    }

    //解を出力
    static void PrintAnswer(char[,] pBanArr)
    {
        //半角数字を全角数字に変換
        Func<int, char> SingleToWideFunc = (pStr) => (char)('0' + pStr - '0');

        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                char CurrChar = pBanArr[X, Y];
                if (CurrChar == 'A') sb.Append('ー');
                if (CurrChar == 'B') sb.Append('=');
                if (CurrChar == 'C') sb.Append('|');
                if (CurrChar == 'D') sb.Append('‖');
                if (CurrChar == ' ') sb.Append(' ');
                if ('0' <= CurrChar && CurrChar <= '8')
                    sb.Append(SingleToWideFunc(mQuestionArr[X, Y]));
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}


実行結果

解を発見
4=4  2==3
‖ ‖     |
6=8=4ーー1|
‖ ‖ | 1ー3
‖ 2 2ーー1|
4ーー3 2  |
|  ‖ ‖2ー3
|1ー5=4| |
3=3ー2ー3ー2


追加問題02 ペンシルパズル入門の例題

string[] Q02Arr ={"4□□3□",
                  "□1□□1",
                  "3□□□□",
                  "□2□2□",
                  "3□4□3"};


追加問題03 ペンシルパズル入門の6問目

string[] Q03Arr ={"3□□4□□□3□3",
                  "□□3□4□3□1□",
                  "□□□3□2□3□6",
                  "4□2□□□□□□□",
                  "□2□8□4□2□4",
                  "□□□□1□2□4□",
                  "5□3□□□□□□2",
                  "□□□2□3□□4□",
                  "□□3□4□1□□□",
                  "2□□3□□□4□3"};


追加問題04 パズルBox10の08問目

string[] Q04Arr ={"1□1□□3□2□1□□3□4□3□□2□□3□3",
                  "□□□□□□□□□□2□□3□2□3□□□1□□□",
                  "2□□5□3□□1□□□□□□□3□□□2□□□3",
                  "□□□□□□□□□□1□2□□2□2□2□3□3□",
                  "3□1□□1□3□1□2□□2□5□2□□□2□□",
                  "□□□3□□1□□□□□□□□□□□□□3□□□2",
                  "□□1□□□□3□□□□3□2□□2□2□3□1□",
                  "4□□□1□3□□□□2□1□□□□1□3□□□2",
                  "□3□3□2□1□□3□3□□□□2□□□□3□□",
                  "2□□□1□□□□□□□□□□□□□1□□4□□□",
                  "□□2□□□2□2□2□□2□3□3□3□□2□3",
                  "□2□2□2□2□5□□5□2□□□□□□□□□□",
                  "3□□□3□□□3□□□□□□□2□□4□3□□3",
                  "□□□3□□□2□4□2□□1□□□□□□□□□□",
                  "3□4□□2□□4□3□3□□3□2□3□□3□3"};


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

string[] Q05Arr ={"4□□□2□3□□3□□2□□4□□2□4□□□3",
                  "□□□1□□□□1□□3□1□□3□□□□2□□□",
                  "□1□□□1□□□1□□□□□3□□□3□□□4□",
                  "□□□□□□3□7□□6□2□□5□2□□□□□□",
                  "□3□5□6□1□□□□□□□□□3□4□2□4□",
                  "□□□□□□□□□1□3□4□3□□□□□□□□□",
                  "3□□□□4□□6□6□2□2□4□□3□□□□3",
                  "□2□4□□□2□□□□□□□□□1□□□2□2□",
                  "1□□□□3□□4□4□3□3□5□□8□□□□4",
                  "□□□□□□□□□1□3□6□3□□□□□□□□□",
                  "□4□5□6□1□□□□□□□□□1□4□1□3□",
                  "□□□□□□3□7□□4□4□□5□2□□□□□□",
                  "□2□□□1□□□1□□□□□3□□□3□□□4□",
                  "□□□1□□□□1□□2□2□□3□□□□1□□□",
                  "3□□□3□2□□3□□4□□6□□3□3□□□2"};


解説

確定探索付の深さ優先探索で解いてます。