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

20-007 L-60(フレーム作成)

問題

小田原充宏さんのL−60のフレーム作成問題を解きます。



11個のピースは下記となります。
各ピースは回転や裏返しても使えます。



いずれも、すべてのL型ピースを使う問題です。

Q9 幅1の四角形のフレームを4つ、つくる
を4つ


ソース

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

class Program
{
    static char[] PieceNameArr = { '1', '2', '3', '4',
                                   '5', '6', '7', '8', '9', 'A'};
    static int[] MensekiArr = { 9, 8, 7, 6,
                                7, 6, 5, 5, 4, 3};
    static int[] MaxHabaArr = { 5, 5, 5, 5,
                                4, 4, 4, 3, 3, 2};
    static int PieceNameArrUB = PieceNameArr.GetUpperBound(0);

    //ピースごとの配置候補
    static Dictionary<char, List<bool[,]>> HaitiKouhoListDict =
        new Dictionary<char, List<bool[,]>>();

    //組み合わせの状態Def
    struct CombinationJyoutaiDef
    {
        internal int CurrInd; //現在の配列のインデックス
        internal Dictionary<int, List<int>> SelectedIndListDict; //選択済インデックスListのDict
    }

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

        //ピースの組み合わせ候補を返す
        List<CombinationJyoutaiDef> PieceCombinationList = DerivePieceCombinationList();
        Console.WriteLine("ピースの組み合わせは{0}通りです", PieceCombinationList.Count);
        Console.WriteLine();

        foreach (char AnyPiece in PieceNameArr) {
            HaitiKouhoListDict[AnyPiece] = DeriveHaitiKouhoList(AnyPiece);
        }

        var sb = new System.Text.StringBuilder();
        int CombinationCnt = 0;

        foreach (CombinationJyoutaiDef EachCombination in PieceCombinationList) {
            sb.Length = 0;
            sb.AppendFormat("■■■■■組み合わせ{0}■■■■■", ++CombinationCnt);
            sb.AppendLine();

            for (int I = 1; I <= 4; I++) {
                sb.AppendFormat("{0}個目の組み合わせ", I);
                foreach (int EachInt in EachCombination.SelectedIndListDict[I]) {
                    sb.AppendFormat("{0},", PieceNameArr[EachInt]);
                }
                sb.AppendLine();
            }
            sb.AppendFormat("幅1のフレームの長方形複数を作成可能か検証中。経過時間={0}", sw.Elapsed);
            sb.AppendLine();
            Console.WriteLine(sb.ToString());

            if (CanCreateHukusuu(EachCombination.SelectedIndListDict)) {
                return;
            }
        }
    }

    //ピースの組み合わせ候補のListを返す
    static List<CombinationJyoutaiDef> DerivePieceCombinationList()
    {
        var WillReturnList = new List<CombinationJyoutaiDef>();

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

        WillPush.CurrInd = 0;
        WillPush.SelectedIndListDict = new Dictionary<int, List<int>>();
        for (int P = 1; P <= 4; P++) WillPush.SelectedIndListDict[P] = new List<int>();
        stk.Push(WillPush);

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

            if (IsOKPieceCombination(Popped.SelectedIndListDict)) {
                WillReturnList.Add(Popped);
            }

            if (Popped.CurrInd > PieceNameArrUB) continue;

            for (int I = Popped.CurrInd; I <= PieceNameArrUB; I++) {
                //使用済ピースは使用不可
                bool WillContinue = false;
                for (int P = 1; P <= 4; P++) {
                    if (Popped.SelectedIndListDict[P].Contains(I))
                        WillContinue = true;
                }
                if (WillContinue) continue;

                //4つの固まりに追加
                Action<int> wkAct = (pKeyVal) =>
                {
                    WillPush.CurrInd = I + 1;
                    WillPush.SelectedIndListDict =
                        new Dictionary<int, List<int>>(Popped.SelectedIndListDict);
                    WillPush.SelectedIndListDict[pKeyVal] =
                        new List<int>(Popped.SelectedIndListDict[pKeyVal]);
                    WillPush.SelectedIndListDict[pKeyVal].Add(I);
                    if (IsValidCombination(WillPush))
                        stk.Push(WillPush);
                };
                for (int P = 1; P <= 4; P++) wkAct(P);

                //ピースを使わない経路
                WillPush.CurrInd = I + 1;
                WillPush.SelectedIndListDict = Popped.SelectedIndListDict;
                stk.Push(WillPush);
            }
        }
        return WillReturnList;
    }

    //有効な組み合わせかを返す
    static bool IsValidCombination(CombinationJyoutaiDef pCombinationJyoutai)
    {
        //ピース5個以上では、フレームを作成不可
        for (int I = 1; I <= 4; I++) {
            if (pCombinationJyoutai.SelectedIndListDict[I].Count >= 5) return false;
        }

        List<int> IndList1 = pCombinationJyoutai.SelectedIndListDict[1];
        List<int> IndList2 = pCombinationJyoutai.SelectedIndListDict[2];
        List<int> IndList3 = pCombinationJyoutai.SelectedIndListDict[3];
        List<int> IndList4 = pCombinationJyoutai.SelectedIndListDict[4];

        //1つめの固まりの[0] < 2つめの固まりの[0] < 3つめの固まりの[0] < 4つめの固まりの[0] 
        if (IndList1.Count > 0 && IndList2.Count > 0)
            if (IndList1[0] > IndList2[0]) return false;
        if (IndList2.Count > 0 && IndList3.Count > 0)
            if (IndList2[0] > IndList3[0]) return false;
        if (IndList4 != null && IndList3.Count > 0 && IndList4.Count > 0)
            if (IndList3[0] > IndList4[0]) return false;

        //固まりごとで[0] < [1] < [2] < [3] < [4] < [n] として対称解の除外
        Predicate<List<int>> wkPred = (pIndList) =>
        {
            for (int I = 1; I <= pIndList.Count - 1; I++) {
                if (pIndList[I - 1] > pIndList[I])
                    return false;
            }
            return true;
        };
        if (wkPred(IndList1) == false) return false;
        if (wkPred(IndList2) == false) return false;
        if (wkPred(IndList3) == false) return false;
        if (IndList4 != null && wkPred(IndList4) == false) return false;
        return true;
    }

    //4つの固まりの組み合わせがOKかを判定
    static bool IsOKPieceCombination(Dictionary<int, List<int>> pSelectedIndListDict)
    {
        //長方形を作るので、固まり1つにつき、最低2ピース必要
        for (int I = 1; I <= 4; I++) {
            if (pSelectedIndListDict[I].Count <= 1)
                return false;
        }

        //幅1のフレームを作成するので、面積合計は2の倍数となる
        int[] wkSumArr = new int[4 + 1];
        for (int I = 1; I <= 4; I++) {
            foreach (int EachInd in pSelectedIndListDict[I]) {
                wkSumArr[I] += MensekiArr[EachInd];
            }
        }
        for (int I = 1; I <= 4; I++) {
            if (wkSumArr[I] % 2 != 0) return false;
        }

        return true;
    }

    //選択済インデックスのカンマ区切りと、幅1のフレームの長方形の配置のDict
    static SortedDictionary<string, char[,]> CanCreateFrameDict = new SortedDictionary<string, char[,]>();

    //選択済インデックスListのDictを引数として、
    //幅1のフレームを複数作成可能かをチェック
    static bool CanCreateHukusuu(Dictionary<int, List<int>> pSelectedIndListDict)
    {
        string[] SelectedIndStrArr = new string[4 + 1];
        for (int P = 1; P <= 4; P++) {
            SelectedIndStrArr[P] = "";
            pSelectedIndListDict[P].ForEach(X => SelectedIndStrArr[P] += X.ToString() + ",");
        }

        for (int P = 1; P <= 4; P++) {
            //幅1のフレームを作成不可な組み合わせが1つでもあったら、NG
            if (CanCreateFrameDict.ContainsKey(SelectedIndStrArr[P])) {
                if (CanCreateFrameDict[SelectedIndStrArr[P]] == null) return false;
            }
        }

        //選択のピースの少ない組み合わせからチェックできるようにする
        int[] wkIndArr = Enumerable.Range(1, 4).OrderBy(X => SelectedIndStrArr[X].Length).ToArray();

        foreach (int EachInd in wkIndArr) {
            //幅1のフレームが作成可能であることをメモ化してある場合
            if (CanCreateFrameDict.ContainsKey(SelectedIndStrArr[EachInd])) continue;

            char[,] CanCreateFrame = DeriveCanCreateFrame(pSelectedIndListDict[EachInd]);
            if (CanCreateFrame == null) {
                CanCreateFrameDict[SelectedIndStrArr[EachInd]] = null;
                return false;
            }
            CanCreateFrameDict[SelectedIndStrArr[EachInd]] = CanCreateFrame;
        }

        Console.WriteLine("解を発見");
        for (int P = 1; P <= 4; P++) {
            Console.WriteLine("{0}つ目の配置", P);
            PrintAnswer(CanCreateFrameDict[SelectedIndStrArr[P]]);
        }
        return true;
    }

    //選択済インデックスListを引数として、
    //幅1のフレームの長方形の配置を返す(配置不可ならnullを返す)
    static char[,] DeriveCanCreateFrame(List<int> pSelectedIndList)
    {
        //ピース配列から面積を求める
        int MensekiSum = 0;
        pSelectedIndList.ForEach(X => MensekiSum += MensekiArr[X]);

        //選択したピースの合計面積から、長方形の横幅と縦幅の候補を求める。
        //対称解の除外で、 横幅 <= 縦幅 とする。
        //フレームを作成するので、幅は最低でも3となる。
        for (int X = 3; X <= MensekiSum; X++) {
            for (int Y = X; Y <= MensekiSum; Y++) {
                if (2 * X + 2 * (Y - 2) > MensekiSum) break;
                if (2 * X + 2 * (Y - 2) != MensekiSum) continue;

                char[,] ShikitumeTarget = DeriveShikitumeTarget(X, Y);
                char[,] wkHaitiArr = DeriveCanHaiti(pSelectedIndList, ShikitumeTarget);
                if (wkHaitiArr == null) continue;
                return wkHaitiArr;
            }
        }
        return null;
    }

    //長方形の横幅と縦幅を引数として、敷き詰め対象となる長方形を作成
    static char[,] DeriveShikitumeTarget(int pX, int pY)
    {
        char[,] ShikitumeTarget = new char[pX, pY];

        for (int X = 0; X <= ShikitumeTarget.GetUpperBound(0); X++) {
            for (int Y = 0; Y <= ShikitumeTarget.GetUpperBound(1); Y++) {
                bool IsHashi = false;
                if (X == 0 || X == ShikitumeTarget.GetUpperBound(0)) IsHashi = true;
                if (Y == 0 || Y == ShikitumeTarget.GetUpperBound(1)) IsHashi = true;

                ShikitumeTarget[X, Y] = (IsHashi ? '?' : ' ');
            }
        }
        return ShikitumeTarget;
    }

    //敷き詰めの状態Def
    struct ShikitumeJyoutaiDef
    {
        internal int Level;
        internal char[,] BanArr;
        internal int CurrX;
        internal int CurrY;
    }

    //選択済インデックスListと配置を引数として、
    //幅1のフレームの長方形が作成可能かをチェック
    static char[,] DeriveCanHaiti(List<int> pSelectedIndList, char[,] pBanArr)
    {
        int UB_X = pBanArr.GetUpperBound(0);
        int UB_Y = pBanArr.GetUpperBound(1);

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

        WillPush.Level = 0;
        WillPush.BanArr = pBanArr;
        WillPush.CurrX = WillPush.CurrY = 0;
        stk.Push(WillPush);

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

            //クリア判定
            if (Popped.BanArr.Cast<char>().All(X => X != '?'))
                return Popped.BanArr;

            //X座標の繰上げ処理(必ずX軸方向の長さは2以上)
            if (Popped.CurrX > UB_X - 1) {
                Popped.CurrX = 0;
                Popped.CurrY++;
            }

            //最終行の1行前を超えた場合(必ずY軸方向の長さが2以上なので)
            if (Popped.CurrY > UB_Y - 1) continue;

            //使用済のピース名の配列
            char[] UsedPieceArr = Popped.BanArr.Cast<char>().Distinct().ToArray();

            foreach (char AnyPiece in PieceNameArr) {
                //最初の配置は、0番目を使うこと
                if (Popped.Level == 0 && AnyPiece != PieceNameArr[pSelectedIndList[0]])
                    continue;

                //使用済ピースだったらContinue
                if (Array.IndexOf(UsedPieceArr, AnyPiece) >= 0) continue;

                //使用できないピースだったらContinue
                if (pSelectedIndList.Exists(
                    X => AnyPiece == PieceNameArr[X]) == false) continue;

                //ピースの配置候補リスト
                List<bool[,]> HaitiKouhoList = new List<bool[,]>();
                HaitiKouhoList.AddRange(HaitiKouhoListDict[AnyPiece]);

                //現在のマス目が空きマスの場合は、マス目を埋める必要あり
                if (Popped.BanArr[Popped.CurrX, Popped.CurrY] == '?')
                    HaitiKouhoList.RemoveAll(X => X[0, 0] == false);

                //マス目にピースを埋めれない候補をRemove
                HaitiKouhoList.RemoveAll(X =>
                    CanFillPiece(X, Popped.CurrX, Popped.CurrY, Popped.BanArr) == false);

                //ピースを配置する経路のPush処理
                foreach (bool[,] AnyPieceMap in HaitiKouhoList) {
                    WillPush.Level = Popped.Level + 1;
                    WillPush.BanArr = (char[,])Popped.BanArr.Clone();

                    if (AnyPiece == '4') WillPush.CurrX = Popped.CurrX + 1;
                    else WillPush.CurrX = Popped.CurrX;

                    WillPush.CurrY = Popped.CurrY;

                    for (int X = 0; X <= AnyPieceMap.GetUpperBound(0); X++) {
                        for (int Y = 0; Y <= AnyPieceMap.GetUpperBound(1); Y++) {
                            if (AnyPieceMap[X, Y] == false) continue;
                            WillPush.BanArr[Popped.CurrX + X, Popped.CurrY + Y] = AnyPiece;
                        }
                    }
                    stk.Push(WillPush);
                }

                //現在のマス目が空きマスでない場合は、ピースを配置しない経路のPush
                if (Popped.BanArr[Popped.CurrX, Popped.CurrY] != '?') {
                    WillPush.Level = Popped.Level;
                    WillPush.BanArr = Popped.BanArr;
                    WillPush.CurrX = Popped.CurrX + 1;
                    WillPush.CurrY = Popped.CurrY;
                    stk.Push(WillPush);
                }
            }
        }
        return null;
    }

    //ピース名を引数として、回転させた配置のListを返す
    static List<bool[,]> DeriveHaitiKouhoList(char pPieceName)
    {
        bool[,] wkArr = null;

        //■
        //■
        //■
        //■
        //■■■■■
        if (pPieceName == '1') {
            wkArr = new bool[5, 5];
            wkArr[0, 0] = true; wkArr[1, 0] = wkArr[2, 0] = wkArr[3, 0] = wkArr[4, 0] = false;
            wkArr[0, 1] = true; wkArr[1, 1] = wkArr[2, 1] = wkArr[3, 1] = wkArr[4, 1] = false;
            wkArr[0, 2] = true; wkArr[1, 2] = wkArr[2, 2] = wkArr[3, 2] = wkArr[4, 2] = false;
            wkArr[0, 3] = true; wkArr[1, 3] = wkArr[2, 3] = wkArr[3, 3] = wkArr[4, 3] = false;
            wkArr[0, 4] = wkArr[1, 4] = wkArr[2, 4] = wkArr[3, 4] = wkArr[4, 4] = true;
        }

        //■
        //■
        //■
        //■
        //■■■■
        if (pPieceName == '2') {
            wkArr = new bool[4, 5];
            wkArr[0, 0] = true; wkArr[1, 0] = wkArr[2, 0] = wkArr[3, 0] = false;
            wkArr[0, 1] = true; wkArr[1, 1] = wkArr[2, 1] = wkArr[3, 1] = false;
            wkArr[0, 2] = true; wkArr[1, 2] = wkArr[2, 2] = wkArr[3, 2] = false;
            wkArr[0, 3] = true; wkArr[1, 3] = wkArr[2, 3] = wkArr[3, 3] = false;
            wkArr[0, 4] = wkArr[1, 4] = wkArr[2, 4] = wkArr[3, 4] = true;
        }

        //■
        //■
        //■
        //■
        //■■■
        if (pPieceName == '3') {
            wkArr = new bool[3, 5];
            wkArr[0, 0] = true; wkArr[1, 0] = wkArr[2, 0] = false;
            wkArr[0, 1] = true; wkArr[1, 1] = wkArr[2, 1] = false;
            wkArr[0, 2] = true; wkArr[1, 2] = wkArr[2, 2] = false;
            wkArr[0, 3] = true; wkArr[1, 3] = wkArr[2, 3] = false;
            wkArr[0, 4] = wkArr[1, 4] = wkArr[2, 4] = true;
        }

        //■
        //■
        //■
        //■
        //■■
        if (pPieceName == '4') {
            wkArr = new bool[2, 5];
            wkArr[0, 0] = true; wkArr[1, 0] = false;
            wkArr[0, 1] = true; wkArr[1, 1] = false;
            wkArr[0, 2] = true; wkArr[1, 2] = false;
            wkArr[0, 3] = true; wkArr[1, 3] = false;
            wkArr[0, 4] = wkArr[1, 4] = true;
        }

        //■
        //■
        //■
        //■■■■
        if (pPieceName == '5') {
            wkArr = new bool[4, 4];
            wkArr[0, 0] = true; wkArr[1, 0] = wkArr[2, 0] = wkArr[3, 0] = false;
            wkArr[0, 1] = true; wkArr[1, 1] = wkArr[2, 1] = wkArr[3, 1] = false;
            wkArr[0, 2] = true; wkArr[1, 2] = wkArr[2, 2] = wkArr[3, 2] = false;
            wkArr[0, 3] = wkArr[1, 3] = wkArr[2, 3] = wkArr[3, 3] = true;
        }

        //■
        //■
        //■
        //■■■
        if (pPieceName == '6') {
            wkArr = new bool[3, 4];
            wkArr[0, 0] = true; wkArr[1, 0] = wkArr[2, 0] = false;
            wkArr[0, 1] = true; wkArr[1, 1] = wkArr[2, 1] = false;
            wkArr[0, 2] = true; wkArr[1, 2] = wkArr[2, 2] = false;
            wkArr[0, 3] = wkArr[1, 3] = wkArr[2, 3] = true;
        }

        //■
        //■
        //■
        //■■
        if (pPieceName == '7') {
            wkArr = new bool[2, 4];
            wkArr[0, 0] = true; wkArr[1, 0] = false;
            wkArr[0, 1] = true; wkArr[1, 1] = false;
            wkArr[0, 2] = true; wkArr[1, 2] = false;
            wkArr[0, 3] = wkArr[1, 3] = true;
        }

        //■
        //■
        //■■■
        if (pPieceName == '8') {
            wkArr = new bool[3, 3];
            wkArr[0, 0] = true; wkArr[1, 0] = wkArr[2, 0] = false;
            wkArr[0, 1] = true; wkArr[1, 1] = wkArr[2, 0] = false;
            wkArr[0, 2] = wkArr[1, 2] = wkArr[2, 2] = true;
        }

        //■
        //■
        //■■
        if (pPieceName == '9') {
            wkArr = new bool[2, 3];
            wkArr[0, 0] = true; wkArr[1, 0] = false;
            wkArr[0, 1] = true; wkArr[1, 1] = false;
            wkArr[0, 2] = wkArr[1, 2] = true;
        }

        //■
        //■■
        if (pPieceName == 'A') {
            wkArr = new bool[2, 2];
            wkArr[0, 0] = true; wkArr[1, 0] = false;
            wkArr[0, 1] = wkArr[1, 1] = true;
        }

        return DeriveKaitenArrList(wkArr);
    }

    //配列を引数として、回転させた配列のリストをDistinctして返す
    static List<bool[,]> DeriveKaitenArrList(bool[,] pBaseArr)
    {
        var KaitenArrList = new List<bool[,]>();

        int BaseArrUB_X = pBaseArr.GetUpperBound(0);
        int BaseArrUB_Y = pBaseArr.GetUpperBound(1);

        for (int I = 1; I <= 8; I++) KaitenArrList.Add(null);
        for (int P = 0; P <= 6; P += 2) KaitenArrList[P] = new bool[BaseArrUB_X + 1, BaseArrUB_Y + 1];
        for (int P = 1; P <= 7; P += 2) KaitenArrList[P] = new bool[BaseArrUB_Y + 1, BaseArrUB_X + 1];

        for (int X = 0; X <= BaseArrUB_X; X++) {
            for (int Y = 0; Y <= BaseArrUB_Y; Y++) {
                bool SetVal = pBaseArr[X, Y];
                KaitenArrList[0][X, Y] = SetVal;
                KaitenArrList[1][Y, BaseArrUB_X - X] = SetVal;
                KaitenArrList[2][BaseArrUB_X - X, BaseArrUB_Y - Y] = SetVal;
                KaitenArrList[3][BaseArrUB_Y - Y, X] = SetVal;

                KaitenArrList[4][X, BaseArrUB_Y - Y] = SetVal;
                KaitenArrList[5][BaseArrUB_Y - Y, BaseArrUB_X - X] = SetVal;
                KaitenArrList[6][BaseArrUB_X - X, Y] = SetVal;
                KaitenArrList[7][Y, X] = SetVal;
            }
        }

        //Distinctする
        for (int I = KaitenArrList.Count - 1; 0 <= I; I--) {
            for (int J = 0; J <= I - 1; J++) {
                if (KaitenArrList[I].GetUpperBound(0) !=
                    KaitenArrList[J].GetUpperBound(0)) continue;
                if (KaitenArrList[I].GetUpperBound(1) !=
                    KaitenArrList[J].GetUpperBound(1)) continue;

                IEnumerable<bool> wkEnum1 = KaitenArrList[I].Cast<bool>();
                IEnumerable<bool> wkEnum2 = KaitenArrList[J].Cast<bool>();
                if (wkEnum1.SequenceEqual(wkEnum2) == false) continue;

                KaitenArrList.RemoveAt(I);
                break;
            }
        }
        return KaitenArrList;
    }

    //マス目にピースを埋めれるか
    static bool CanFillPiece(bool[,] pPieceMap, int pTargetX, int pTargetY, char[,] pBanArr)
    {
        for (int X = 0; X <= pPieceMap.GetUpperBound(0); X++) {
            if (pTargetX + X > pBanArr.GetUpperBound(0)) return false;
            for (int Y = 0; Y <= pPieceMap.GetUpperBound(1); Y++) {
                if (pTargetY + Y > pBanArr.GetUpperBound(1)) return false;
                if (pPieceMap[X, Y] && pBanArr[pTargetX + X, pTargetY + Y] != '?')
                    return false;
            }
        }
        return true;
    }

    //解を出力
    static void PrintAnswer(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
            for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
                sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}


実行結果

省略
■■■■■組み合わせ192■■■■■
1個目の組み合わせ1,5,
2個目の組み合わせ3,7,
3個目の組み合わせ6,9,
4個目の組み合わせ8,A,
幅1のフレームの長方形複数を作成可能か検証中。経過時間=00:00:58.1730074

解を発見
1つ目の配置
11111
1   5
1   5
1   5
15555

2つ目の配置
333
3 7
3 7
3 7
377

3つ目の配置
666
6 9
6 9
699

4つ目の配置
888
8 A
8AA


解説

20-076 ポリックス(同一形複数)のアルゴリズムを流用してます。

ピースの組み合わせの列挙後に、
ピースの組み合わせの合計面積から、
候補となるフレームを列挙して、
敷き詰め可能かをチェックしてます。

ピースの組み合わせごとに、
フレームを作成可能かをSortedDictionaryにメモしてます。