Cマガ電脳クラブ(第098回) 絶対なるかけひき

問題

Fig.1において、nのマスの数は左上(a)、上(b)、右上(c)の数で決まり、
|a×c−b| ("||"は絶対値) という式で導かれる。
各マスには1桁の数字しか入れない。
よって結果が10以上になった場合は1の位の数字のみを使うことにする。

Fig2は、太文の数字が与えられた場合に、この規則に従って順次数字を書き込んだものである。
さて、Fig.3のような覆面算がある。
文字が同じならば隠されている数字は同じで、文字が違えば数字が違う。'*'はどんな数字でもかまわない。
前述の規則を満たすようにしてこの覆面算を復元してほしい。

ソース

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

class Program
{
    struct PointDef
    {
        internal int X;
        internal int Y;
    }

    static int UB_X;
    static int UB_Y;

    struct JyoutaiDef
    {
        internal int CurrUB_X;
        internal int CurrUB_Y;
        internal Dictionary<char, char> StrNumDict;
        internal char[,] BanArr;
    }

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

        string[] QuestionStrArr = {"CMAGAZINE",
                                   "L********",
                                   "A********",
                                   "N**E*****",
                                   "G***N****",
                                   "U****I***",
                                   "A*****G**",
                                   "G******M*",
                                   "E*******A"};

        UB_X = QuestionStrArr[0].Length - 1;
        UB_Y = QuestionStrArr.GetUpperBound(0);

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrUB_X = WillPush.CurrUB_Y = 0;
        WillPush.StrNumDict = new Dictionary<char, char>();
        WillPush.BanArr = new char[UB_X + 1, UB_Y + 1];
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                WillPush.BanArr[LoopX, LoopY] = QuestionStrArr[LoopY][LoopX];
            }
        }
        stk.Push(WillPush);

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

            //クリア判定
            if (Popped.BanArr.Cast<char>().All(A => '0' <= A && A <= '9')) {
                Console.WriteLine("解を発見。経過時間={0}", sw.Elapsed);

                PrintAnswer(Popped.BanArr);
                foreach (var EachPair in Popped.StrNumDict.OrderBy(A => A.Key)) {
                    Console.WriteLine("{0}={1}", EachPair.Key, EachPair.Value);
                }
                return;
            }

            //数値が未確定の文字の座標を求める
            PointDef MikakuteStrPoint =
                DeriveMikakuteStrPoint(Popped.BanArr, Popped.CurrUB_X, Popped.CurrUB_Y);

            //数値が未確定の文字が存在する場合
            if (0 <= MikakuteStrPoint.X && 0 <= MikakuteStrPoint.Y) {
                for (char I = '0'; I <= '9'; I++) {
                    if (Popped.StrNumDict.ContainsValue(I)) continue;
                    char CurrStr = Popped.BanArr[MikakuteStrPoint.X,
                                                 MikakuteStrPoint.Y];
                    WillPush.CurrUB_X = Popped.CurrUB_X;
                    WillPush.CurrUB_Y = Popped.CurrUB_Y;
                    WillPush.StrNumDict = new Dictionary<char, char>(Popped.StrNumDict);
                    WillPush.StrNumDict.Add(CurrStr, I);
                    WillPush.BanArr = (char[,])Popped.BanArr.Clone();

                    //盤面の指定文字に指定数値を設定
                    TargetStrToNum(WillPush.BanArr, CurrStr, I);

                    stk.Push(WillPush);
                }
                continue;
            }

            //数値が未確定の文字が存在しない場合
            bool WillEdakiri = false;
            for (int LoopX = 1; LoopX <= Popped.CurrUB_X; LoopX++) {
                for (int LoopY = 1; LoopY <= Popped.CurrUB_Y; LoopY++) {
                    char wkA = Popped.BanArr[LoopX - 1, LoopY];
                    char wkB = Popped.BanArr[LoopX - 1, LoopY - 1];
                    char wkC = Popped.BanArr[LoopX, LoopY - 1];
                    char wkN = DeriveNMasuValue(wkA, wkB, wkC);

                    //*の場合は、埋める
                    if (Popped.BanArr[LoopX, LoopY] == '*') {
                        Popped.BanArr[LoopX, LoopY] = wkN;
                    }

                    //数値の場合は、計算通りでなかったら枝切り
                    else if (Popped.BanArr[LoopX, LoopY] != wkN) {
                        WillEdakiri = true;
                        break;
                    }
                }
                if (WillEdakiri) break;
            }
            if (WillEdakiri) continue;

            //Push処理
            WillPush.CurrUB_X = Math.Min(Popped.CurrUB_X + 1, UB_X);
            WillPush.CurrUB_Y = Math.Min(Popped.CurrUB_Y + 1, UB_Y);
            WillPush.StrNumDict = Popped.StrNumDict;
            WillPush.BanArr = Popped.BanArr;
            stk.Push(WillPush);
        }
    }

    //数値が未確定の文字の座標を求める
    static PointDef DeriveMikakuteStrPoint(char[,] pBanArr, int pCurrUB_X, int pCurrUB_Y)
    {
        for (int LoopX = 0; LoopX <= pCurrUB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= pCurrUB_Y; LoopY++) {
                char CurrMasu = pBanArr[LoopX, LoopY];
                if (CurrMasu == '*') continue;
                if ('0' <= CurrMasu && CurrMasu <= '9') continue;
                return new PointDef() { X = LoopX, Y = LoopY };
            }
        }
        return new PointDef() { X = -1, Y = -1 };
    }

    //盤面の指定文字に指定数値を設定
    static void TargetStrToNum(char[,] pBanArr, char pTargetStr, char pTargetNum)
    {
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                if (pBanArr[LoopX, LoopY] == pTargetStr)
                    pBanArr[LoopX, LoopY] = pTargetNum;
            }
        }
    }

    //nのマスの値を求める
    static char DeriveNMasuValue(char pA, char pB, char pC)
    {
        int IntA = int.Parse(pA.ToString());
        int IntB = int.Parse(pB.ToString());
        int IntC = int.Parse(pC.ToString());

        int wkInt = Math.Abs(IntA * IntC - IntB) % 10;
        return char.Parse(wkInt.ToString());
    }

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

実行結果

解を発見。経過時間=00:00:02.8746318
813436752
912513581
361325217
571213116
434754101
043787311
322111410
458654511
263069143

A=3
C=8
E=2
G=4
I=7
L=9
M=1
N=5
U=0
Z=6

解説

深さ優先探索で、埋める対象のX軸の上限とY軸の上限を増やしながら探索してます。