Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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

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

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

キャプチャ.PNG

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

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

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

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++;
            }
        }
    }
}

ちょっとコードの説明

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

magicstar.png

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グラフィックスが必要なものは、どうするかまだ思案中です。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした