19-01 カラーマッチ とり

問題

匹見パズルのカラーマッチ とりを解きます。




9ピースを、下の図のように3*3に並べて下さい。これだけなら誰でもできる。
しかし、隣り合う辺がどこも同じ色にならないといけない(12箇所)。


答えは、6通り。

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB = 8;

    struct PieceInfoDef
    {
        internal int PieceID;
        internal List<char[]> HaitiArrList;
    }
    static PieceInfoDef[] mPieceInfoArr;

    struct JyoutaiDef
    {
        internal char[,] BanArr;
        internal int Level;
        internal List<int> UsedPieceIDList;
    }

    static void Main()
    {
        //ピースごとの情報を取得
        DerivePieceInfo();

        //回転解の排除で、ピース1は回転させない
        mPieceInfoArr[0].HaitiArrList.RemoveRange(1, mPieceInfoArr[0].HaitiArrList.Count - 1);

        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.Level = 0;
        WillPush.UsedPieceIDList = new List<int>();
        Stk.Push(WillPush);

        int AnswerCnt = 0;
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            //クリア判定
            if (Popped.Level == 9) {
                Console.WriteLine("解{0}を発見", ++AnswerCnt);
                PrintBan(Popped.BanArr, Popped.UsedPieceIDList);
                continue;
            }

            int BaseX, BaseY;
            DeriveShikitumePos(Popped.Level, out BaseX, out BaseY);
            foreach (PieceInfoDef EachPieceInfo in mPieceInfoArr) {
                if (Popped.UsedPieceIDList.Contains(EachPieceInfo.PieceID))
                    continue;

                foreach (char[] EachHaitiArr in EachPieceInfo.HaitiArrList) {
                    WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                    WillPush.BanArr[BaseX + 1, BaseY] = EachHaitiArr[0];
                    WillPush.BanArr[BaseX + 2, BaseY + 1] = EachHaitiArr[1];
                    WillPush.BanArr[BaseX + 1, BaseY + 2] = EachHaitiArr[2];
                    WillPush.BanArr[BaseX, BaseY + 1] = EachHaitiArr[3];
                    if (IsValid(WillPush.BanArr, Popped.Level) == false) continue;

                    WillPush.Level = Popped.Level + 1;
                    WillPush.UsedPieceIDList = new List<int>(Popped.UsedPieceIDList);
                    WillPush.UsedPieceIDList.Add(EachPieceInfo.PieceID);

                    Stk.Push(WillPush);
                }
            }
        }
    }

    //ピースごとの情報を取得
    static void DerivePieceInfo()
    {
        var PieceInfoList = new List<PieceInfoDef>();

        Action<int, string> AddAct = (pID, pStr) =>
        {
            PieceInfoDef WillAdd;
            WillAdd.PieceID = pID;
            WillAdd.HaitiArrList = DeriveHaitiArrList(pStr.ToCharArray());
            PieceInfoList.Add(WillAdd);
        };
        AddAct(1, "紫緑赤水");
        AddAct(2, "赤水黄紫");
        AddAct(3, "黄赤紫水");
        AddAct(4, "緑水黄赤");
        AddAct(5, "黄緑赤水");
        AddAct(6, "紫黄緑水");
        AddAct(7, "水紫赤緑");
        AddAct(8, "赤紫緑黄");
        AddAct(9, "緑黄水紫");

        mPieceInfoArr = PieceInfoList.ToArray();
    }

    //回転させた配置を返す(4通り)
    static List<char[]> DeriveHaitiArrList(char[] pBaseArr)
    {
        var WillReturn = new List<char[]>();

        for (int I = 0; I <= pBaseArr.GetUpperBound(0); I++) {
            var WillAdd = new List<char>();
            int CurrInd = I;
            for (int J = 1; J <= pBaseArr.Length; J++) {
                WillAdd.Add(pBaseArr[I]);
                if (++I > pBaseArr.GetUpperBound(0)) I = 0;
            }
            WillReturn.Add(WillAdd.ToArray());
        }
        return WillReturn;
    }

    //レベルを引数として、敷き詰めの座標を返す
    static void DeriveShikitumePos(int pLevel, out int pX, out int pY)
    {
        pX = pY = -1;
        if (pLevel == 0) { pX = 0; pY = 0; }
        if (pLevel == 1) { pX = 3; pY = 0; }
        if (pLevel == 2) { pX = 6; pY = 0; }

        if (pLevel == 3) { pX = 0; pY = 3; }
        if (pLevel == 4) { pX = 3; pY = 3; }
        if (pLevel == 5) { pX = 6; pY = 3; }

        if (pLevel == 6) { pX = 0; pY = 6; }
        if (pLevel == 7) { pX = 3; pY = 6; }
        if (pLevel == 8) { pX = 6; pY = 6; }
    }

    //盤面とレベルを引数として、有効な盤面かをチェック
    static bool IsValid(char[,] pBanArr, int pLevel)
    {
        if (pLevel == 1 && pBanArr[2, 1] != pBanArr[3, 1]) return false;
        if (pLevel == 2 && pBanArr[5, 1] != pBanArr[6, 1]) return false;
        if (pLevel == 3 && pBanArr[1, 2] != pBanArr[1, 3]) return false;

        if (pLevel == 4 && pBanArr[2, 4] != pBanArr[3, 4]) return false;
        if (pLevel == 4 && pBanArr[4, 2] != pBanArr[4, 3]) return false;

        if (pLevel == 5 && pBanArr[5, 4] != pBanArr[6, 4]) return false;
        if (pLevel == 5 && pBanArr[7, 2] != pBanArr[7, 3]) return false;

        if (pLevel == 6 && pBanArr[1, 5] != pBanArr[1, 6]) return false;

        if (pLevel == 7 && pBanArr[2, 7] != pBanArr[3, 7]) return false;
        if (pLevel == 7 && pBanArr[4, 5] != pBanArr[4, 6]) return false;

        if (pLevel == 8 && pBanArr[5, 7] != pBanArr[6, 7]) return false;
        if (pLevel == 8 && pBanArr[7, 5] != pBanArr[7, 6]) return false;

        return true;
    }

    //解を出力
    static void PrintBan(char[,] pBanArr, List<int> pUsedPieceIDList)
    {
        var sb = new System.Text.StringBuilder();

        sb.AppendLine("ピースIDの配置");
        for (int I = 0; I <= pUsedPieceIDList.Count - 1; I++) {
            if (I == 3 || I == 6)
                sb.AppendLine();
            sb.Append(pUsedPieceIDList[I]);
        }
        sb.AppendLine();

        sb.AppendLine("色の配置");
        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());
    }
}

実行結果

省略
解6を発見
ピースIDの配置
169
485
327
色の配置
□紫□□水□□緑□
水□緑緑□紫紫□黄
□赤□□黄□□水□
□赤□□黄□□水□
黄□緑緑□赤赤□黄
□水□□紫□□緑□
□水□□紫□□緑□
紫□黄黄□赤赤□水
□赤□□水□□紫□

解説

深さ優先探索でピースを敷き詰めてます。