[パズル]小町算

「小町算(こまちざん)」とは、1～9までの数字と＋、－、×、÷ の記号を使って、計算結果が100になる式を作る数学パズルです。江戸時代にはすでに知られていたということで、歴史あるパズルです。

例えば、
１２３＋４５－６７＋８－９＝１００
はその正解の一つです。

このパズルの変形として、＋、－だけ使うものとか、（）を認めるものとか、色々あるようです。
ここでは、＋、－だけを使って100になるような式を求めています。

解き方はいろいろあると思いますが、１□２□３□４□５□６□７□８□９の四角の中に、＋、－、空白を入れてゆき、その計算結果が100になるものを求めという方法を採用しています。
つまり、これも組合せの一種ということになります。
この組合せを求めるのに、再帰処理を使うのが普通ですが、今回は、LINQのクエリ式で組合せを求めています。
例えば、

上のコードを実行すると、

という結果を得られます。このように個数が事前に分かっている場合は、LINQのfromを複数使ったクエリ式を使うととても簡単です。
つまり、

という配列に対し、

とすれば、１□２□３□４□５□６□７□８□９の四角の中に入れる組合せを求めることが出来るというわけです。
そして、

とやって、計算式としても文字列を組み立てます。例えば、"1234 + 5 - 678 * 9" のような文字列が出来上がります。
これをコンピュータに計算させれば良いわけです。
この計算をするのに、逆ポーランド記法(後置記法)に変換し、スタックを使って計算するコードを書こうかとも思ったのですが、面倒なので、System.CodeDom.Compiler.JScriptCodeProviderを使い、JScriptの式として計算させることにしました。

なお、このクラスを直接つかうのではなく、これをラップしたJScriptEvaluatorというクラスを作り、

のように簡単に計算式の結果を求められるようにしています。

残念ながら、System.CodeDom.Compiler.JScriptCodeProviderクラスは、Silverlight3では利用できないので、今回のプログラムはコンソールアプリケーションとして作成しています。

以下、C#のコードです。コメントにあるように、わずかの修正で × ÷ も使って 100 になる式を求めることが可能です。

■Program.cs

using System;
using System.Linq;

namespace komachi {
    class Program {
        static void Main(string[] args) {
            KomachiSolver sol = new KomachiSolver();
            int n = sol.Solve();
            Console.WriteLine("{0}個の解が見つかりました",n);
            Console.ReadLine();
        }
    }

class KomachiSolver {
        //private string[] os = { "", "+", "-", "*", "/" };
        private string[] os = { "", "+", "-" };
        public int Solve() {
            var q = from c1 in os
                    from c2 in os
                    from c3 in os
                    from c4 in os
                    from c5 in os
                    from c6 in os
                    from c7 in os
                    from c8 in os
                    select new { c1, c2, c3, c4, c5, c6, c7, c8 };
            JScriptEvaluator jscript = new JScriptEvaluator();
            int count = 0;
            foreach (var x in q) {
                string exp = string.Format("1{0}2{1}3{2}4{3}5{4}6{5}7{6}8{7}9",
                    x.c1, x.c2, x.c3, x.c4, x.c5, x.c6, x.c7, x.c8);
                string r = jscript.Eval(exp);
                if (Convert.ToDouble(r) == 100.0) {
                    Console.WriteLine(exp);
                    count++;
                }
            }
            return count;
        }
    }
}

■JScriptEvaluator.cs

using System;
using System.CodeDom.Compiler;
using System.Reflection;

namespace komachi {
    // Microsoft.JScript を参照に追加
    public class JScriptEvaluator {
        private Assembly asm;
        private Type type;
        private object evalObject;

public JScriptEvaluator() {
            PreCompile();
        }

public string Eval(string exp) {
            return (string)type.InvokeMember("Eval", BindingFlags.InvokeMethod,
                                              null, evalObject, new object[] { exp });
        }

private void PreCompile() {
            string source =
                @"package JsEvaluator {
                     class Evaluator {
                         public function Eval(exp : String) : String { 
                             return eval(exp); 
                         }
                     }
                  }";
            CodeDomProvider provider = new Microsoft.JScript.JScriptCodeProvider();
            CompilerParameters cparams = new CompilerParameters();
            cparams.GenerateInMemory = true;
            CompilerResults cresults = provider.CompileAssemblyFromSource(cparams, source);
            asm = cresults.CompiledAssembly;
            type = asm.GetType("JsEvaluator.Evaluator");
            evalObject = Activator.CreateInstance(type);
        }
    }
}

Gushwell's C# Programming Page

[パズル]小町算

[パズル]小町算