Cマガ電脳クラブ(第008回) ネイバーズ

問題

ガラスの円盤に縦4×横4、合計16個のまるいクボミがあり、
その底にはどこも赤、黄、青、白、黒のどれかの色で縫ってある(Fig.1)。

周囲のトレンチには、色つきのビー玉が16個 (赤3個、青3個、黄3個、黒3個、白4個) 入っている。
すべてのビー玉を1個ずつクボミに置けば完成なのだが、置き方に以下の制約がある。
 1：玉と同じ色のクボミには置けない。
 2：玉と同じ色のクボミのトナリには置けない。この場合、45度方向のトナリも含まれる。
 3：ビー玉を置いたら、以降そのクボミの色は置かれた玉の色に変わる。

つまりあるクボミに、ある色のビー玉がいま置けなくても
「周囲にほかのビー玉が置かれて、その場所の色が変われば」置けるようになる順序が問題なのである。
最終的な盤の配色が同じでも、それに至る道筋は何通りもあるだろう。

しかし今回は仕上げの配色だけを問題にする。仕上げの配色には何通りあるか。
それぞれの仕上がり図と、それに至る道筋を1通りだけ例として添えていただきたい。

Fig.1
青  黒  白  黄
黄  赤  青  黒
白  黒  白  黄
赤  青  赤  青

ソース

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

class Program
{
    const int UB = 4 - 1;

    struct JyoutaiDef
    {
        internal char[,] BanArr;
        internal bool[,] AlreadyHaitiArr;
        internal List<char> RestList;
        internal List<char[,]> BanLog;
        internal List<string> OpeLog;
    }

    static void Main()
    {
        JyoutaiDef WillPush;

        char[,] wkBan = {{'青','黒','白','黄'},
                         {'黄','赤','青','黒'},
                         {'白','黒','白','黄'},
                         {'赤','青','赤','青'}};
        //X座標とY座標を変換してセット
        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] = wkBan[Y, X];
            }
        }

        WillPush.AlreadyHaitiArr = new bool[UB + 1, UB + 1];

        WillPush.RestList = new List<char>();
        WillPush.RestList.AddRange(Enumerable.Repeat('赤', 3));
        WillPush.RestList.AddRange(Enumerable.Repeat('青', 3));
        WillPush.RestList.AddRange(Enumerable.Repeat('黄', 3));
        WillPush.RestList.AddRange(Enumerable.Repeat('黒', 3));
        WillPush.RestList.AddRange(Enumerable.Repeat('白', 4));

        WillPush.BanLog = new List<char[,]>();
        WillPush.OpeLog = new List<string>();

        var stk = new Stack<JyoutaiDef>();
        stk.Push(WillPush);

        var AnswerBanList = new List<char[,]>();
        int AnswerCnt = 0;

        var VisitedSet = new HashSet<string>();
        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            if (Popped.RestList.Count == 0) {
                AnswerBanList.Add(Popped.BanArr);
                Console.WriteLine("解{0}を発見しました", ++AnswerCnt);

                for (int I = 0; I <= Popped.BanLog.Count - 1; I++) {
                    Console.WriteLine("{0}手目は {1}", I + 1, Popped.OpeLog[I]);
                    PrintBan(Popped.BanLog[I]);
                }
                continue;
            }

            foreach (char HaitiColor in Popped.RestList.Distinct()) {
                for (int X = 0; X <= UB; X++) {
                    for (int Y = 0; Y <= UB; Y++) {
                        if (Popped.AlreadyHaitiArr[X, Y]) continue;

                        if (CanHaiti(X, Y, Popped.BanArr, HaitiColor) == false) continue;

                        WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                        WillPush.BanArr[X, Y] = HaitiColor;

                        WillPush.AlreadyHaitiArr = (bool[,])Popped.AlreadyHaitiArr.Clone();
                        WillPush.AlreadyHaitiArr[X, Y] = true;

                        WillPush.RestList = new List<char>(Popped.RestList);
                        WillPush.RestList.Remove(HaitiColor);

                        WillPush.BanLog = new List<char[,]>(Popped.BanLog);
                        WillPush.BanLog.Add(WillPush.BanArr);

                        WillPush.OpeLog = new List<string>(Popped.OpeLog);
                        WillPush.OpeLog.Add(string.Format("[{0},{1}]に{2}を配置。{3}",
                                            X, Y, HaitiColor, DeriveRestLog(WillPush.RestList)));
                        if (VisitedSet.Add(GetHash(WillPush.BanArr, WillPush.AlreadyHaitiArr)))
                            stk.Push(WillPush);
                    }
                }
            }
        }
    }

    static bool CanHaiti(int pX, int pY, char[,] pBanArr, char pHaitiColor)
    {
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (Math.Abs(pX - X) > 1 || Math.Abs(pY - Y) > 1) continue;
                if (pBanArr[X, Y] == pHaitiColor) return false;
            }
        }
        return true;
    }

    static string DeriveRestLog(List<char> pRestList)
    {
        var sb = new System.Text.StringBuilder("残りは");
        sb.AppendFormat("赤{0},", pRestList.Count(X => X == '赤'));
        sb.AppendFormat("青{0},", pRestList.Count(X => X == '青'));
        sb.AppendFormat("黄{0},", pRestList.Count(X => X == '黄'));
        sb.AppendFormat("黒{0},", pRestList.Count(X => X == '黒'));
        sb.AppendFormat("白{0},", pRestList.Count(X => X == '白'));
        return sb.ToString();
    }

    static string GetHash(char[,] pBanArr, bool[,] pAlreadyHaitiArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                sb.Append(pBanArr[X, Y]);
                sb.Append(pAlreadyHaitiArr[X, Y] ? 0 : 1);
            }
        }
        return sb.ToString();
    }

    static void PrintBan(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        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());
    }
}

実行結果

解1を発見しました
1手目は [0,0]に白を配置。残りは赤3,青3,黄3,黒3,白3,
白黒白黄
黄赤青黒
白黒白黄
赤青赤青

2手目は [0,1]に青を配置。残りは赤3,青2,黄3,黒3,白3,
白黒白黄
青赤青黒
白黒白黄
赤青赤青

3手目は [1,2]に黄を配置。残りは赤3,青2,黄2,黒3,白3,
白黒白黄
青赤青黒
白黄白黄
赤青赤青

4手目は [2,3]に黒を配置。残りは赤3,青2,黄2,黒2,白3,
白黒白黄
青赤青黒
白黄白黄
赤青黒青

5手目は [0,3]に黒を配置。残りは赤3,青2,黄2,黒1,白3,
白黒白黄
青赤青黒
白黄白黄
黒青黒青

6手目は [1,0]に黄を配置。残りは赤3,青2,黄1,黒1,白3,
白黄白黄
青赤青黒
白黄白黄
黒青黒青

7手目は [1,1]に黒を配置。残りは赤3,青2,黄1,黒0,白3,
白黄白黄
青黒青黒
白黄白黄
黒青黒青

8手目は [2,2]に赤を配置。残りは赤2,青2,黄1,黒0,白3,
白黄白黄
青黒青黒
白黄赤黄
黒青黒青

9手目は [3,3]に白を配置。残りは赤2,青2,黄1,黒0,白2,
白黄白黄
青黒青黒
白黄赤黄
黒青黒白

10手目は [2,0]に赤を配置。残りは赤1,青2,黄1,黒0,白2,
白黄赤黄
青黒青黒
白黄赤黄
黒青黒白

11手目は [2,1]に白を配置。残りは赤1,青2,黄1,黒0,白1,
白黄赤黄
青黒白黒
白黄赤黄
黒青黒白

12手目は [3,2]に青を配置。残りは赤1,青1,黄1,黒0,白1,
白黄赤黄
青黒白黒
白黄赤青
黒青黒白

13手目は [3,0]に青を配置。残りは赤1,青0,黄1,黒0,白1,
白黄赤青
青黒白黒
白黄赤青
黒青黒白

14手目は [3,1]に黄を配置。残りは赤1,青0,黄0,黒0,白1,
白黄赤青
青黒白黄
白黄赤青
黒青黒白

15手目は [0,2]に赤を配置。残りは赤0,青0,黄0,黒0,白1,
白黄赤青
青黒白黄
赤黄赤青
黒青黒白

16手目は [1,3]に白を配置。残りは赤0,青0,黄0,黒0,白0,
白黄赤青
青黒白黄
赤黄赤青
黒白黒白

解説

コレクションクラスを駆使してます。