Cマガ電脳クラブ(第016回) ぶらさがり覆面算

問題

今回はちょっと変わった覆面算(Fig.1)だ。
文字が同じならば隠されている数字は同じで、文字が違えば数字が違うのは、普通の覆面算と同じである。
ただし、* にはどの数字を当てはめてもよい。
さて、ここで肝心なのは、「横に隣り合った数の差 (絶対値) が必ずその下にある」ということだ。
Fig.2に簡単な復元例を示す。Fig.1を復元してください。

Fig.1
C C L A N G U A G E
 * * * * * * * * *
  * * * * * * * *
   * * * * * * *
    * * * * * *
     C M A G A
      * * * *
       * * *
        * *
         *

Fig.2
M A G I C   3 1 2 5 9
 G A M E     2 1 3 4
  * * *       1 2 1
   * *         1 1
    *           0

ソース

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

class Program
{
    const bool IsSampleQuestion = false; //サンプル問題ならTrue

    const int Level1Length = (IsSampleQuestion ? 5 : 10);
    const int NodeCnt = Level1Length * (Level1Length + 1) / 2; //等差数列の和の公式

    static void Main()
    {
        List<int[]> TopNodesCombiList = DeriveTopNodeCombiList();

        foreach (int[] AnyIntArr in TopNodesCombiList) {
            int[] wkArrP = FillAbs(AnyIntArr);

            if (IsSampleQuestion && IsOK_Sample(wkArrP)) {
                Console.WriteLine("解を発見。");
                PrintAnswer(wkArrP);
            }
            else if (!IsSampleQuestion && IsOK_Honmon(wkArrP)) {
                Console.WriteLine("解を発見。");
                PrintAnswer(wkArrP);
            }
        }
    }

    //最上位のノードの数字の組み合わせをInt配列のListジェネリックで返す
    static List<int[]> DeriveTopNodeCombiList()
    {
        var WillReturnList = new List<int[]>();
        var stk = new Stack<List<int>>();

        for (int I = 0; I <= Level1Length; I++) {
            stk.Push(new List<int> { I });
        }

        while (stk.Count > 0) {
            List<int> PoppedList = stk.Pop();

            if (PoppedList.Count == Level1Length) {
                WillReturnList.Add(PoppedList.ToArray());
                continue;
            }

            for (int I = 0; I <= 9; I++) {
                if (IsSampleQuestion) {
                    if (IsValidTop_Sample(PoppedList, I) == false) continue;
                }
                if (!IsSampleQuestion) {
                    if (IsValidTop_Honmon(PoppedList, I) == false) continue;
                }

                stk.Push(new List<int>(PoppedList) { I });
            }
        }
        return WillReturnList;
    }

    //有効なトップノードかのチェック(サンプル問題用)
    static bool IsValidTop_Sample(List<int> pList, int pAddVal)
    {
        int AddP = pList.Count;

        //文字の重複チェック
        if (IsSampleQuestion && 1 <= AddP && AddP <= 4) {
            if (pList.Contains(pAddVal)) return false;
        }
        return true;
    }

    //有効なトップノードかのチェック(本問用)
    static bool IsValidTop_Honmon(List<int> pList, int pAddVal)
    {
        int AddP = pList.Count;

        //文字の一致チェック
        if (AddP == 1 && pList[0] != pAddVal) return false;
        if (AddP == 7 && pList[3] != pAddVal) return false;
        if (AddP == 8 && pList[5] != pAddVal) return false;

        //文字の重複チェック
        if (2 <= AddP && AddP <= 6 || AddP == 9) {
            if (pList.Contains(pAddVal)) return false;
        }

        return true;
    }

    //トップノードの配列を受け取り、下位ノードを絶対値で埋めた配列を返す
    static int[] FillAbs(int[] pTopNodes)
    {
        int[] FilledArr = new int[NodeCnt];
        Array.Copy(pTopNodes, FilledArr, Level1Length);

        int CurrP = pTopNodes.GetUpperBound(0) + 1;
        for (int Y = Level1Length - 1; Y >= 1; Y--) {
            for (int X = 1; X <= Y; X++) {
                int WK1 = FilledArr[CurrP - Y - 1];
                int WK2 = FilledArr[CurrP - Y];
                FilledArr[CurrP++] = Math.Abs(WK1 - WK2);
            }
        }
        return FilledArr;
    }

    //絶対値を埋めたツリーが解かのチェック(サンプル問題用)
    static bool IsOK_Sample(int[] pArr)
    {
        if (pArr[2] != pArr[5]) return false; //2レベル目のG
        if (pArr[1] != pArr[6]) return false; //2レベル目のA
        if (pArr[0] != pArr[7]) return false; //2レベル目のM

        //2レベル目のE
        if (Array.IndexOf<int>(pArr, pArr[8], 0, 8) >= 0) return false;

        return true;
    }

    //絶対値を埋めたツリーが解かのチェック(サンプル問題用)
    static bool IsOK_Honmon(int[] pArr)
    {
        if (pArr[40] != pArr[0]) return false; //5レベル目のC
        if (pArr[42] != pArr[3]) return false; //5レベル目のA
        if (pArr[43] != pArr[5]) return false; //5レベル目のG
        if (pArr[44] != pArr[3]) return false; //5レベル目のA

        //5レベル目のM
        if (Array.IndexOf<int>(pArr, pArr[41], 0, Level1Length) >= 0) return false;

        return true;
    }

    //解を出力
    static void PrintAnswer(int[] pArr)
    {
        int CurrP = 0, SPCnt = 0;
        for (int XCnt = Level1Length; 1 <= XCnt; XCnt--) { //出力する行のループ
            Console.Write(new string(' ', SPCnt++));//空白を出力
            for (int I = 1; I <= XCnt; I++) { //1行に対する出力のループ
                Console.Write("{0} ", pArr[CurrP++]);
            }
            Console.WriteLine();
        }
    }
}

実行結果

解を発見。
0 0 7 3 8 2 4 3 2 9
 0 7 4 5 6 2 1 1 7
  7 3 1 1 4 1 0 6
   4 2 0 3 3 1 6
    2 2 3 0 2 5
     0 1 3 2 3
      1 2 1 1
       1 1 0
        0 1
         1

解説

下記のように、CCLANGまで確定すれば、
5レベル目のCが確定するので5レベル目のCで枝切りしてもいいです。
C C L A N G
 * * * * *
  * * * *
   * * *
    * *
     C
同様に、
CCLANGUまで確定すれば、5レベル目のMで枝切り
CCLANGUAまで確定すれば、5レベル目のAで枝切り
といった枝切りも可能です。