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

23-08 チェックメイク

問題

ハナヤマのWOODY STYLE チェックメイクを解きます。



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

□　　　□
■□　　■□

■　　　■
□■　　□■

□　　　■
■□■　□■□

問題1 解数は、右下白が647、右下黒が411
■■□■■
□□□□□
□■■■□
□■□■□
□■■■□

問題11 解数は、右下白が603、右下黒が6
□□□□□
■□□□□
■■□□□
■■■□□
■■■■□

問題14 解数は、右下白が374、右下黒が3
□■■■□
■■□■■
■□□□■
■■□■■
□□■□□

問題15 解数は、右下白が26、右下黒が24
□□□□□
□□■□□
□□■□□
□■■■□
□□■□□

ソース

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

class Program
{
    //右下のマスの色
    const char MigishitaColor = '■';
    //const char MigishitaColor = '□';

    const int UB = 4;

    struct JyoutaiDef
    {
        internal char[,] BanArr;
        internal int[,] PieceHaitiArr;
        internal int CurrX;
        internal int CurrY;
    }

    static void Main()
    {
        //問01
        //char[,] wkBan = {{'■','■','□','■','■'},
        //                 {'□','□','□','□','□'},
        //                 {'□','■','■','■','□'},
        //                 {'□','■','□','■','□'},
        //                 {'□','■','■','■','□'}};

        //問02
        //char[,] wkBan = {{'■','■','□','■','■'},
        //                 {'□','■','□','■','□'},
        //                 {'□','□','□','□','□'},
        //                 {'□','■','□','■','□'},
        //                 {'□','■','■','■','□'}};

        //問11
        //char[,] wkBan = {{'□','□','□','□','□'},
        //                 {'■','□','□','□','□'},
        //                 {'■','■','□','□','□'},
        //                 {'■','■','■','□','□'},
        //                 {'■','■','■','■','□'}};

        //問14
        char[,] wkBan = {{'□','■','■','■','□'},
                         {'■','■','□','■','■'},
                         {'■','□','□','□','■'},
                         {'■','■','□','■','■'},
                         {'□','■','■','■','□'}};

        //問15
        //char[,] wkBan = {{'□','□','□','□','□'},
        //                 {'□','□','■','□','□'},
        //                 {'□','□','■','□','□'},
        //                 {'□','■','■','■','□'},
        //                 {'□','□','■','□','□'}};

        //X座標とY座標の入れ替え
        char[,] XYRevBan = new char[UB + 1, UB + 1];
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                XYRevBan[X, Y] = wkBan[Y, X];
            }
        }

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanArr = XYRevBan;
        WillPush.PieceHaitiArr = new int[UB + 1, UB + 1];
        WillPush.CurrX = WillPush.CurrY = 0;
        stk.Push(WillPush);

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

            if (IsItimatu(Popped.BanArr) && IsUsedAllPiece(Popped.PieceHaitiArr)) {
                Console.WriteLine("解{0,3}を発見", ++AnwserCnt);
                PrintAnswer(Popped.BanArr, Popped.PieceHaitiArr);
                continue;
            }

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

            //最終行に到達した場合
            if (Popped.CurrY == UB) continue;

            //ピース未配置のマスの場合
            if (Popped.PieceHaitiArr[Popped.CurrX, Popped.CurrY] == 0) {
                int[] UsedPieceArr = Popped.PieceHaitiArr.Cast<int>().Distinct().ToArray();
                for (int PieceNo = 1; PieceNo <= 6; PieceNo++) {
                    if (UsedPieceArr.Contains(PieceNo)) continue;

                    //1番と2番は同じピース
                    if (PieceNo == 2 && UsedPieceArr.Contains(1) == false) continue;

                    //3番と4番は同じピース
                    if (PieceNo == 4 && UsedPieceArr.Contains(3) == false) continue;

                    //マス目が黒かを求める
                    bool IsHidariueBlack =
                        (DeriveCorrectColor(Popped.CurrX, Popped.CurrY) == '■');

                    //ピースの候補リスト
                    List<bool[,]> PieceList = DerivePieceList(IsHidariueBlack, PieceNo);

                    //マス目にピースを埋めれない要素をRemove
                    PieceList.RemoveAll(X =>
                        CanFillPiece(X, Popped.CurrX, Popped.CurrY, Popped.PieceHaitiArr) == false);

                    //ピースを配置する経路のPush処理
                    foreach (bool[,] AnyPieceMap in PieceList) {
                        WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                        WillPush.PieceHaitiArr = (int[,])Popped.PieceHaitiArr.Clone();
                        WillPush.CurrX = Popped.CurrX + 1;
                        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]) {
                                    WillPush.BanArr[Popped.CurrX + X, Popped.CurrY + Y] =
                                        DeriveCorrectColor(Popped.CurrX + X, Popped.CurrY + Y);
                                    WillPush.PieceHaitiArr[Popped.CurrX + X, Popped.CurrY + Y] = PieceNo;
                                }
                            }
                        }
                        stk.Push(WillPush);
                    }
                }
            }

            //現在のマス目に未配置でもOKの場合は、ピースを配置しない経路のPush
            if (Popped.BanArr[Popped.CurrX, Popped.CurrY] ==
                DeriveCorrectColor(Popped.CurrX, Popped.CurrY)) {
                WillPush.BanArr = Popped.BanArr;
                WillPush.PieceHaitiArr = Popped.PieceHaitiArr;
                WillPush.CurrX = Popped.CurrX + 1;
                WillPush.CurrY = Popped.CurrY;
                stk.Push(WillPush);
            }
        }
    }

    //盤面が市松模様かを判定
    static bool IsItimatu(char[,] pBanArr)
    {
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (pBanArr[X, Y] != DeriveCorrectColor(X, Y))
                    return false;
            }
        }
        return true;
    }

    //全てのピースを使用しているかを判定
    static bool IsUsedAllPiece(int[,] PieceHaitiArr)
    {
        IEnumerable<int> wkEnum = PieceHaitiArr.Cast<int>();
        for (int I = 1; I <= 6; I++)
            if (wkEnum.Contains(I) == false) return false;
        return true;
    }

    //マス目の正しい色を返す
    static char DeriveCorrectColor(int pTargetX, int pTargetY)
    {
        if ((pTargetX + pTargetY) % 2 == 0)
            return MigishitaColor;
        return MigishitaColor == '□' ? '■' : '□';
    }

    //ピース番号を引数として、回転させたピース配置のListを返す
    static List<bool[,]> DerivePieceList(bool IsHidariueBlack, int pPieceNo)
    {
        var WillReturn = new List<bool[,]>();
        bool[,] wkArr;

        //ピース番号の1番と2番
        if (pPieceNo == 1 || pPieceNo == 2) {
            if (IsHidariueBlack) {
                //■□
                //□
                wkArr = new bool[2, 2];
                wkArr[0, 0] = wkArr[1, 0] = true;
                wkArr[0, 1] = true; wkArr[1, 1] = false;
                WillReturn.Add(wkArr);
                return WillReturn;
            }
            //□
            //■□
            wkArr = new bool[2, 2];
            wkArr[0, 0] = true; wkArr[1, 0] = false;
            wkArr[0, 1] = wkArr[1, 1] = true;
            WillReturn.Add(wkArr);

            //□■
            //　□
            wkArr = new bool[2, 2];
            wkArr[0, 0] = wkArr[1, 0] = true;
            wkArr[0, 1] = false; wkArr[1, 1] = true;
            WillReturn.Add(wkArr);
            return WillReturn;
        }

        //ピース番号の3番と4番
        if (pPieceNo == 3 || pPieceNo == 4) {
            if (IsHidariueBlack) {
                //■
                //□■
                wkArr = new bool[2, 2];
                wkArr[0, 0] = true; wkArr[1, 0] = false;
                wkArr[0, 1] = wkArr[1, 1] = true;
                WillReturn.Add(wkArr);

                //■□
                //　■
                wkArr = new bool[2, 2];
                wkArr[0, 0] = wkArr[1, 0] = true;
                wkArr[0, 1] = false; wkArr[1, 1] = true;
                WillReturn.Add(wkArr);
                return WillReturn;
            }
            //□■
            //■
            wkArr = new bool[2, 2];
            wkArr[0, 0] = wkArr[1, 0] = true;
            wkArr[0, 1] = true; wkArr[1, 1] = false;
            WillReturn.Add(wkArr);
            return WillReturn;
        }
        //ピース番号の5番
        if (pPieceNo == 5) {
            if (IsHidariueBlack) {
                //■□
                //□
                //■
                wkArr = new bool[2, 3];
                wkArr[0, 0] = wkArr[1, 0] = true;
                wkArr[0, 1] = true; wkArr[1, 1] = false;
                wkArr[0, 2] = true; wkArr[1, 2] = false;
                WillReturn.Add(wkArr);

                //■□■
                //　　□
                wkArr = new bool[3, 2];
                wkArr[0, 0] = wkArr[1, 0] = wkArr[2, 0] = true;
                wkArr[0, 1] = wkArr[1, 1] = false; wkArr[2, 1] = true;
                WillReturn.Add(wkArr);

                //■
                //□
                //■□
                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;
                WillReturn.Add(wkArr);

                //■□■
                //□
                wkArr = new bool[3, 2];
                wkArr[0, 0] = wkArr[1, 0] = wkArr[2, 0] = true;
                wkArr[0, 1] = true; wkArr[1, 1] = wkArr[2, 1] = false;
                WillReturn.Add(wkArr);
                return WillReturn;
            }
            //□■
            //　□
            //　■
            wkArr = new bool[2, 3];
            wkArr[0, 0] = wkArr[1, 0] = true;
            wkArr[0, 1] = false; wkArr[1, 1] = true;
            wkArr[0, 2] = false; wkArr[1, 2] = true;
            WillReturn.Add(wkArr);

            //□
            //■□■
            wkArr = new bool[3, 2];
            wkArr[0, 0] = true; wkArr[1, 0] = wkArr[2, 0] = false;
            wkArr[0, 1] = wkArr[1, 1] = wkArr[2, 1] = true;
            WillReturn.Add(wkArr);
            return WillReturn;
        }

        //ピース番号の6番
        if (IsHidariueBlack) {
            //■□
            //　■
            //　□
            wkArr = new bool[2, 3];
            wkArr[0, 0] = wkArr[1, 0] = true;
            wkArr[0, 1] = false; wkArr[1, 1] = true;
            wkArr[0, 2] = false; wkArr[1, 2] = true;
            WillReturn.Add(wkArr);

            //■
            //□■□
            wkArr = new bool[3, 2];
            wkArr[0, 0] = true; wkArr[1, 0] = wkArr[2, 0] = false;
            wkArr[0, 1] = wkArr[1, 1] = wkArr[2, 1] = true;
            WillReturn.Add(wkArr);
            return WillReturn;
        }

        //□
        //■
        //□■
        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;
        WillReturn.Add(wkArr);

        //□■□
        //■
        wkArr = new bool[3, 2];
        wkArr[0, 0] = wkArr[1, 0] = wkArr[2, 0] = true;
        wkArr[0, 1] = true; wkArr[1, 1] = wkArr[2, 1] = false;
        WillReturn.Add(wkArr);

        //□■
        //■
        //□
        wkArr = new bool[2, 3];
        wkArr[0, 0] = wkArr[1, 0] = true;
        wkArr[0, 1] = true; wkArr[1, 1] = false;
        wkArr[0, 2] = true; wkArr[1, 2] = false;
        WillReturn.Add(wkArr);

        //□■□
        //　　■
        wkArr = new bool[3, 2];
        wkArr[0, 0] = wkArr[1, 0] = wkArr[2, 0] = true;
        wkArr[0, 1] = wkArr[1, 1] = false; wkArr[2, 1] = true;
        WillReturn.Add(wkArr);
        return WillReturn;
    }

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

    //解を出力
    static void PrintAnswer(char[,] pBanArr, int[,] pPieceHaitiArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                if (pPieceHaitiArr[X, Y] != 0) {
                    sb.AppendFormat("{0,2}", pPieceHaitiArr[X, Y]);
                }
                else sb.Append(pBanArr[X, Y]);
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

解  1を発見
 1 1■ 2 2
 1■ 3 3 2
 5 5 3□■
 5 6□ 4 4
 5 6 6 6 4

解  2を発見
 1 1■ 2 2
 1 3 3■ 2
 5 5 3□■
 5 6□ 4 4
 5 6 6 6 4

解  3を発見
 1 1 5 5 5
 1■ 5 6 6
■ 3 3□ 6
 2 3□ 4 6
 2 2■ 4 4

解  4を発見
 1 1 5 5 5
 1 3 5 6 6
■ 3 3□ 6
 2■□ 4 6
 2 2■ 4 4

解説

各ピースに番号を付けて、深さ優先探索してます。

問題11の右下が黒マスの解は、製品の解答カードだと6通りなのですが、
本プログラムだと解が8通り求まります。

問題14の右下が黒マスの解は、製品の解答カードだと3通りなのですが、
本プログラムだと解が4通り求まります。