小町算

1□2□3□4□5□6□7□8□9 = 100 という数式の□の中に、+, -, 空白のいずれかを入れて、正しい数式を完成させるプログラムです。

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

class Program {
    const int EMPTY = -1; // 空白
    const int ADD   = -2; // 足し算
    const int SUB   = -3; // 引き算

    static int Eval(int[] xs) {
        // EMPTY を取り除く。
        var expr = new List<int>();
        expr.Add(xs[0]);
        for (int i = 2; i < xs.Length; i += 2) {
            if (xs[i-1] == EMPTY) { // 数字を連結する
                expr[expr.Count-1] = 10 * expr[expr.Count-1] + xs[i];
            }
            else {
                expr.Add(xs[i-1]);
                expr.Add(xs[i]);
            }
        }

        // 式を評価する
        int ret = expr[0];
        for (int i = 2; i < expr.Count; i += 2) {
            switch (expr[i-1]) {
            case ADD:
                ret += expr[i];
                break;

            case SUB:
                ret -= expr[i];
                break;

            default:
                throw new InvalidOperationException();
            }
        }
        return ret;
    }

    static void Show(int[] xs) {
        var ss = new List<string>();
        foreach (int x in xs) {
            if (x == EMPTY) continue;

            if (x == ADD)
                ss.Add(" + ");
            else if (x == SUB)
                ss.Add(" - ");
            else
                ss.Add(x.ToString());
        }
        Console.WriteLine(string.Join("", ss));
    }

    static void Calc(int p, int[] xs, int k) {
        if (p == xs.Length) {
            if (Eval(xs) == 100) {
                Show(xs);
            }
            return;
        }

        foreach (int op in new[] { EMPTY, ADD, SUB }) {
            xs[p] = op;
            xs[p+1] = k;
            Calc(p+2, xs, k+1);
        }
    }

    static void Main() {
        var xs = new int[9+8]; // 数値が 9 つと、演算子(+, -, 空白)が 8 つ。
        xs[0] = 1;
        Calc(1, xs, 2);
    }
}

実行結果です。

123 + 45 - 67 + 8 - 9
123 + 4 - 5 + 67 - 89
123 - 45 - 67 + 89
123 - 4 - 5 - 6 - 7 + 8 - 9
12 + 3 + 4 + 5 - 6 - 7 + 89
12 + 3 - 4 + 5 + 67 + 8 + 9
12 - 3 - 4 + 5 - 6 + 7 + 89
1 + 23 - 4 + 56 + 7 + 8 + 9
1 + 23 - 4 + 5 + 6 + 78 - 9
1 + 2 + 34 - 5 + 67 - 8 + 9
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9

リンク