Cマガ電脳クラブ(第017回) ディスコン

問題

スイスのNeaf社のDISCONというパズルを紹介する。
Fig.1のように、穴の開いた円盤が12枚ある。また、長さが円盤の厚みの3倍の丸棒が13本ある。

これを順序よく円柱状に積んだとき、丸棒すべてを、内部の空間に収めることができる。
円盤の厚みはすべて同じで、裏表の区別はない。
穴は全部で39個だから、3単位の丸棒13本使えば、穴は全部埋まってしまうことになる。
さらに2つの条件を加える。
　(1) 完成した円柱は2つ以上の独立した円柱に分割されないこと。
　(2) 丸棒の上に丸棒が直接のらないこと。
　    つまり、6や9の長さの丸棒が入ったような解は認められないのである。
さて、鏡像解も別の解とはしないという、一番きびしい数え方で、解答は何通りあるだろうか。

Fig.1

ソース

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

class Program
{
    const int UB_X = 5;
    const int UB_Y = 11;

    const char FillChar = '*'; //埋まってるスペースの文字

    struct JyoutaiDef
    {
        internal int CurrY;
        internal char[,] HaitiArr; //円盤の配置
        internal List<char> UsedEnbanList; //使用済の円盤リスト
    }

    //回転させた円盤のDictionary
    static Dictionary<char, List<int[]>> KaitenEnbanDict = new Dictionary<char, List<int[]>>();

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

        for (char wkChar = 'A'; wkChar <= 'L'; wkChar++) {
            DeriveKaitenEnbanDict(wkChar);
        }

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

        foreach (var AnyPair in KaitenEnbanDict) {
            foreach (int[] EachAnaArr in AnyPair.Value) {
                WillPush.HaitiArr = new char[UB_X + 1, UB_Y + 1];
                for (int X = 0; X <= UB_X; X++)
                    for (int Y = 0; Y <= UB_Y; Y++) WillPush.HaitiArr[X, Y] = ' ';

                EnbanSet(WillPush.HaitiArr, AnyPair.Key, EachAnaArr, WillPush.CurrY);
                WillPush.UsedEnbanList = new List<char>() { AnyPair.Key };
                stk.Push(WillPush);
            }
        }

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

            if (Popped.CurrY == UB_Y) {
                Console.WriteLine("解{0,2}を発見。経過時間={1}", ++AnswerCnt, sw.Elapsed);
                PrintAnswer(Popped.HaitiArr);
                continue;
            }

            foreach (var AnyPair in KaitenEnbanDict) {
                if (Popped.UsedEnbanList.Contains(AnyPair.Key)) continue;
                WillPush.CurrY = Popped.CurrY + 1;

                //回転と鏡像解除外で、Fは上半分固定とする
                if (AnyPair.Key == 'F' && WillPush.CurrY > UB_Y / 2) {
                    continue;
                }

                foreach (int[] EachAnaArr in AnyPair.Value) {
                    WillPush.HaitiArr = (char[,])Popped.HaitiArr.Clone();
                    EnbanSet(WillPush.HaitiArr, AnyPair.Key, EachAnaArr, WillPush.CurrY);

                    if (IsValid(WillPush.CurrY, WillPush.HaitiArr) == false) {
                        continue;
                    }

                    WillPush.UsedEnbanList = new List<char>(Popped.UsedEnbanList);
                    WillPush.UsedEnbanList.Add(AnyPair.Key);
                    stk.Push(WillPush);
                }
            }
        }
    }

    //回転させた円盤のDictionaryを求める
    static void DeriveKaitenEnbanDict(char pKey)
    {
        int[] BaseAnaArr;
        if (pKey == 'A') BaseAnaArr = new int[] { 0 };
        else if (pKey == 'B') BaseAnaArr = new int[] { 0, 1 };
        else if (pKey == 'C') BaseAnaArr = new int[] { 0, 2 };
        else if (pKey == 'D') BaseAnaArr = new int[] { 0, 3 };
        else if (pKey == 'E') BaseAnaArr = new int[] { 0, 1, 2 };
        else if (pKey == 'F') BaseAnaArr = new int[] { 0, 1, 3 };
        else if (pKey == 'G') BaseAnaArr = new int[] { 0, 2, 4 };
        else if (pKey == 'H') BaseAnaArr = new int[] { 0, 1, 2, 3 };
        else if (pKey == 'I') BaseAnaArr = new int[] { 0, 1, 2, 4 };
        else if (pKey == 'J') BaseAnaArr = new int[] { 0, 1, 3, 4 };
        else if (pKey == 'K') BaseAnaArr = new int[] { 0, 1, 2, 3, 4 };
        else BaseAnaArr = new int[] { 0, 1, 2, 3, 4, 5 };

        var AnaArrList = new List<int[]>();

        //始点変更の分
        Action<int[]> AddSitenhenkouHaiti = pAnaArr =>
        {
            for (int pKasanVal = 0; pKasanVal <= UB_X; pKasanVal++) {
                int[] WillAdd = (int[])pAnaArr.Clone();
                for (int I = 0; I <= WillAdd.GetUpperBound(0); I++) {
                    WillAdd[I] += pKasanVal;
                    if (WillAdd[I] > UB_X) WillAdd[I] -= (UB_X + 1);
                }
                Array.Sort<int>(WillAdd);
                AnaArrList.Add(WillAdd);
            }
        };

        //始点変更の分
        AddSitenhenkouHaiti(BaseAnaArr);

        //回転と始点変更の分
        for (int I = 0; I <= BaseAnaArr.GetUpperBound(0); I++) {
            if (BaseAnaArr[I] == 1) BaseAnaArr[I] = 5;
            else if (BaseAnaArr[I] == 2) BaseAnaArr[I] = 4;
            else if (BaseAnaArr[I] == 4) BaseAnaArr[I] = 2;
            else if (BaseAnaArr[I] == 5) BaseAnaArr[I] = 1;
        }
        AddSitenhenkouHaiti(BaseAnaArr);

        //穴配置のDistinct
        for (int I = AnaArrList.Count - 1; 0 <= I; I--) {
            bool HasDuplicate = false;
            for (int J = 0; J <= I - 1; J++) {
                if (AnaArrList[I].SequenceEqual(AnaArrList[J])) {
                    HasDuplicate = true;
                    break;
                }
            }
            if (HasDuplicate) AnaArrList.RemoveAt(I);
        }

        //回転と鏡像解除外で、Fは固定とする
        if (pKey == 'F') AnaArrList.RemoveRange(1, AnaArrList.Count - 1);

        //AnaArrList
        KaitenEnbanDict[pKey] = AnaArrList;
    }

    //円盤を配置
    static void EnbanSet(char[,] pHaitiArr, char pKey, int[] pAnaArr, int pTargetY)
    {
        for (int I = 0; I <= pHaitiArr.GetUpperBound(0); I++)
            pHaitiArr[I, pTargetY] = (pAnaArr.Contains(I) ? pKey : FillChar);
    }

    //現在が有効な状態か？
    static bool IsValid(int pCurrY, char[,] pHaitiArr)
    {
        //枝切り条件1 長さが3未満の穴が存在したら枝切り
        //枝切り条件2 長さが4以上の穴が存在したら枝切り

        for (int X = 0; X <= UB_X; X++) {
            bool IsAna = false;
            int AnaLength = 0;
            for (int Y = 0; Y <= pCurrY; Y++) {
                if (pHaitiArr[X, Y] == FillChar) { //アルファベットでない場合
                    if (IsAna && AnaLength < 3) return false; //枝切り条件1
                    IsAna = false;
                    AnaLength = 0;
                }
                else {//アルファベットの場合
                    IsAna = true;
                    if (++AnaLength > 3) return false; //枝切り条件2
                }
                if (Y == UB_Y)
                    if (IsAna && AnaLength < 3) return false; //枝切り条件1
            }
        }
        return true;
    }

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

実行結果

省略
解66を発見。経過時間=00:01:18.3745238
A*****
BB****
FF*F**
*G*G*G
J*JJ*J
HHH**H
EEE***
*D**D*
**C*C*
LLLLLL
KKKK*K
II*I*I

解説

ディスコンという英単語は、discontinuedを省略したものです。
このパズルでは、長さが3の縦棒を連結させないという意味でしょう。

ディスコンの紹介画像


解答例