C#で数学パズル - センチュリーパズル(西洋小町)を効率よく解く

小町数を使った数学パズルの第7弾です。たぶん、小町数を使ったパズルはこれが最後。

センチュリーパズルとは

1～9までの数字を1回だけ使って帯分数をつくり、その値が100を表すようにするパズルをセンチュリーパズルと言います。

別の表現だと、「K + N / D = 100」を満たす K,D,Nを求めよ。ただし、K,N,Dは1～9の数を1つずつ使用すること。

となります。

例えば、

3 + 69258 / 714 ＝ 100

は求める答えの一つです。

欧米で知られている小町数パズル（いわゆる西洋小町パズル）のひとつです。（小町: 1-9が一つずつで構成されている）

どうやって解くか

「3つの式が等しくなる小町数」では、再帰処理をし1-9の順列を求めることで解を求めました。このセンチュリーパズルも同様の手法が使えますが、ここでは別のアプローチを取ることにします。
K + N / Dのそれぞれが、正の数であることから、Kは、1から99までの値に絞られます。
つまり、

 for (int k = 1; k <= 99; k++) {
     ...
 }

というループの中で、N,D を求めてゆけば良いことになります。
k=3の場合を考えてみると、N/Dは、97になるので、
97/1, 194/2, 291/3, 388/4, 485/5,...
と調べてゆき、K,N,Dが1-9で構成されていれば、求める答えになります。

N,Dは桁数がどんどん増えてゆきますから、K, N,Dの桁数の合計が10桁以上になったら、小町を満たさなくなりますので、Kの処理を終わります。

このパズルは再帰処理を使わないので、容易に理解できると思います。

C#のコード

これをC#のコードにしたのが、以下のコードです。

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

namespace CenturyPuzzleApp {
    public class Answer {
        public int WholeNumber { get; set; }    // K K以外の名前を付けたが...
        public int Denominator { get; set; }    // D 分母
        public int Numerator { get; set; }      // N 分子
    }

    public class CenturyPuzzle {
        public IEnumerable<Answer> Solve() {
            // CenturyPuzzle
            // 整数部を基準にして、総当りで求めている
            for (int k = 1; k <= 99; k++) {
                var x = 100 - k;     // X == N / D
                var denominator = 1; // 分母 もっと大きな数から始められるはずだが...
                while (true) {
                    // 分子  K + N / D = 100 となる N を求めている --> N = D * (100 - K)  
                    var numerator = denominator * x;
                    var frac = $"{k}{numerator}{denominator}";
                    if (frac.Length > 9)
                        // これ以上やっても解はない。小町にはならない
                        break;
                    if (IsKomachi(frac)) {
                        yield return new Answer {
                            WholeNumber = k,
                            Numerator = numerator,
                            Denominator = denominator
                        };
                    }
                    denominator++;
                }
            }
        }

        // 小町数か、（引数は数値を文字列に変換したもの）
        private bool IsKomachi(string s) {
            return s.OrderBy(c => c).SequenceEqual("123456789");
        }
    }
}

using System;
using System.Text;

namespace CenturyPuzzleApp {
    class Program {
        static void Main(string[] args) {
            var cp = new CenturyPuzzle();
            var sb = new StringBuilder();
            foreach (var a in cp.Solve()) {
                sb.AppendFormat("{0} + {1} / {2} = 100\n",
                                 a.WholeNumber, a.Numerator, a.Denominator);
            }
            Console.WriteLine(sb.ToString());
        }
    }
}

結果

3 + 69258 / 714 = 100
81 + 5643 / 297 = 100
81 + 7524 / 396 = 100
82 + 3546 / 197 = 100
91 + 5742 / 638 = 100
91 + 5823 / 647 = 100
91 + 7524 / 836 = 100
94 + 1578 / 263 = 100
96 + 1428 / 357 = 100
96 + 1752 / 438 = 100
96 + 2148 / 537 = 100

最初のKの値が3からいきなり81に飛んじゃうんですね。

この記事は、Gushwell's C# Programming Pageで公開したものをに加筆・修正したものです。