C#で数学パズル - MagicStarパズルを解く

マジックスター(MagicStar)というパズルをＣ＃で解くプログラムを書いてみました。

マジックスター(MagicStar)パズルとは

マジックスターは、下の図の12個ある○に 1から12までの数字をひとつずつ入れていき、直線上の4個の数字の合計が、すべて 26 になるように、数字を配置するというものです。

このパズル、手で解くとなると結構難しく、頭を悩ませることになるのですが、下記に示すプログラムを実行していただければわかる通り、解が想像以上に多いのにびっくりします。

すべての解を紙と鉛筆で求めるとなると、よっぽど根気のある人でないと無理なんじゃないかと思います。

でも、コンピュータで解かせれば、すべての解をあっという間に求めることができます。
もちろん、プログラミングにはそれなりの時間がかかりますが...

C#のコード

まずは、C#のコードを載せます。説明はその後で。

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

namespace MagicStarApp {
    public class MagicStarsSolver {
        // 解が入る配列
        private int[] _star = new int[12];

        // 対称性を省くためのDictionary
        private Dictionary<int, int> _ansPos0 = new Dictionary<int, int>();

        // 位置0 を除いた直線の端の位置を示す。対称性を省くために利用 
        private int[] _tipIndexes = { 1, 4, 7, 10, 11 };

        public IEnumerable<int[]> Solve() {
            // 〇の中に入れる数字1,2,3,...12 を生成して、_Solveを呼ぶ。
            return _Solve(Enumerable.Range(1, 12));
        }

        private IEnumerable<int[]> _Solve(IEnumerable<int> rest) {
            int count = rest.Count();
            if (count == 0) {
                if (IsAnswer()) {
                    _ansPos0[_star[0]] = 1; // 位置0に置いた番号を記憶する 対称性排除のため
                    yield return _star.ToArray();
                }
                yield break;
            }
            if (IsCorrect()) {
                int nextix = 12 - count;
                foreach (var n in rest) {
                    // 回転して得られる対称解を省く
                    if (_tipIndexes.Contains(nextix) && _ansPos0.ContainsKey(n))
                        continue;

                    _star[nextix] = n;
                    foreach (var ans in _Solve(rest.Where(x => x != n)))
                        yield return ans;
                    _star[nextix] = 0;
                }
            }
        }

        // 解か？
        public bool IsAnswer() {
            return GetLines(_star).All(line => line.Sum() == 26);
        }

        // 正しいか （途中の状態を調べる）
        public bool IsCorrect() {
            foreach (var line in GetLines(_star)) {
                // 26より大きければダメ
                if (line.Sum() > 26)
                    return false;
                // 直線に数字が全て埋まっていて、26より小さければダメ
                if (line.All(x => x > 0) && line.Sum() < 26)
                    return false;
                // 鏡像を省く
                if ((_star[2] != 0 && _star[3] != 0) && (_star[2] > _star[3]))
                    return false;
            }
            return true;
        }

        // 6本の直線を列挙する
        public IEnumerable<int[]> GetLines(int[] stars) {
            yield return new int[] { stars[0], stars[2], stars[5], stars[7] };
            yield return new int[] { stars[0], stars[3], stars[6], stars[10] };
            yield return new int[] { stars[1], stars[2], stars[3], stars[4] };
            yield return new int[] { stars[1], stars[5], stars[8], stars[11] };
            yield return new int[] { stars[7], stars[8], stars[9], stars[10] };
            yield return new int[] { stars[4], stars[6], stars[9], stars[11] };
        }
    }
}

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

namespace MagicStarApp {
    class Program {
        static void Main(string[] args) {
            var solver = new MagicStarsSolver();
            var answers = solver.Solve();
            foreach (var (ans, i) in answers.Enumerate(1)) {
                Console.WriteLine($"#{i}");
                Print(ans);
            }
        }

        private static void Print(int[] stars) {
            Console.WriteLine("      ({0,2})", stars[0]);
            Console.WriteLine("({0,2})({1,2})({2,2})({3,2})", stars[1], stars[2], stars[3], stars[4]);
            Console.WriteLine("  ({0,2})    ({1,2})", stars[5], stars[6]);
            Console.WriteLine("({0,2})({1,2})({2,2})({3,2})", stars[7], stars[8], stars[9], stars[10]);
            Console.WriteLine("      ({0,2})", stars[11]);
            Console.WriteLine();
        }
    }

    // これはちょっとしたお遊び。
    // こんな拡張メソッド書けば、インデックス付きのforeachができる。
    static class EnumerableExtensions {
        public static IEnumerable<(T, int)> Enumerate<T>(this IEnumerable<T> seq, int startIndex) {
            var i = startIndex;
            foreach (var e in seq) {
                yield return (e, i);
                i++;
            }
        }
    }
}

ちょっとコードの説明

マジックスターパズルは１２個の数値を扱うので、解が入る要素１２の配列を用意し、そこに数値を入れていきます。
このプログラムでは、下の図のように、配列のインデックスと○の位置の対応付けをしています。

MagicStarsSolverクラスのSolveメソッドで、private の _Solveメソッドを呼び出しています。この_Solveメソッドの引数には、まだ○の位置に置かれていない数値のリストを渡します。最初は1-12までの数値です。

この_Solveメソッドがバックトラックの手法を使って、パズルを解いています。
_Solveメソッドでは、空いている○に引数で与えられたリストの中の数値を置き、解の条件に合致しているかを調べ、合致していたら、リストからその数値を取り除き、_Solveメソッドを再帰呼び出しします。
合致していなかったら、空いている○に数値を置かずに、メソッドを抜けます。

これを再帰的に繰り返すことで、解を求めています。

なお、回転や鏡像を排除するためにちょっと工夫をしています。
詳しくはソースコードを見てください。

実行結果

#1
      ( 1)
( 2)( 4)(12)( 8)
  (10)    ( 6)
(11)( 5)( 3)( 7)
      ( 9)

#2
      ( 1)
( 2)( 6)(10)( 8)
  (12)    ( 4)
( 7)( 3)( 5)(11)
      ( 9)

#3
      ( 1)
( 2)( 7)(11)( 6)
  ( 8)    ( 5)
(10)( 4)( 3)( 9)
      (12)

#4
      ( 1)
( 2)( 7)(12)( 5)
  (10)    ( 4)
( 8)( 3)( 6)( 9)
      (11)

以下省略

もっと解を知りたい方は、是非プログラムを動かしてみてください。

このMagicStarパズルの解き方についてもっと詳しく知りたい方は、こちらのページ（言語はC言語ですが）がとても参考になると思います。

終わりに

この記事は、Gushwell's C# Programming Pageで公開したものをに加筆・修正したものです。このプログラムを最初に公開した時は、Silverlightアプリとして公開しました。しかし、Silverlightも既に終わりの時を迎えています。

このQiitaに再掲載するにあたって、WPF, UWPで再作成とも考えたのですが、いろいろ考えた末、アルゴリズムを主としたこの手のプログラムは、コンソールアプリケーションで作成するのが一番だという思いが強くなり、コンソールアプリケーションとして再作成することにしました。

僕が示したいのはアルゴリズム部分なので、そのほうが応用がきくと思います。

これから、Gushwell's C# Programming PageでSilverlightアプリとして公開していたプログラムを見直して、Qiitaで多数公開するつもりでいますが、基本はコンソールアプリケーションで作成しようと思っています。

2Dグラフィックスが必要なものは、どうするかまだ思案中です。