×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

[パズル]3つの式が等しくなる小町数

問題
「○○ー○ = ○○ / ○ = ○ + ○ × ○ 」の○の部分に、1−9までの数がひとつづつ入るようにせよ。
真ん中の式は、割り切れる数にすること。

いわゆる小町数パズルのひとつです。
パズルに興味がある方は、ボタンを押す前に、実際に自分で解いてみてください。
意外と難しいです。僕は答えがわかりませんでした。

この問題を解くには、基本的には、総当たりで調べてゆくプログラムを書けば良いですね。
それには、1ー9までの数のすべての順列を求めて、その順列に対し、式が成り立つかを調べれば答えを求めることができます。
例えば、求めた順列が、3,5,6,9,8,2,1,4,7 ならば、35 - 6 = 98 / 2 = 1 + 4 * 7 という式が成り立つかを調べればいいですね。

つまり、順列を求めるプログラムが書ければ、それを少し変形することで、この問題を解くプログラムを書くことができます。

ただ、単なる総当たりだと時間がかかりすぎますので、明らかに条件に一致しないことが分かった時点で、その探索をやめ、次の候補を調べるようにしています。いわゆる「枝刈り」処理ですね。
このプログラムでは、枝刈りをするために、順列のうち最初の6つが求まった時点で先頭2つの式が等しいか調べ、等しくなかったら、それ以上続けることは意味がないので、7つめの要素を求めるのをやめて、次の順列を求めるようにしています。

なお、このプログラムではやっていませんが、さらに速くしたいのならば、1つ目の式と2つ目の式を入れ替えて、順列の最初の3つの要素が求まった時点で、割り切れるかどうかを調べれば、もっと早い段階での枝切りが可能になり、高速化につながります。

このプログラムが難しいと感じる方は、まずは、「すべての順列を求める」で掲載しているコードを理解してみてください。また、併せてこちら「再帰メソッドで、yield returnしたい」もご覧いただけると良いかと思います。


以下、C#のコードです。

■Solver.cs

■MainPage.xaml.cs

■MainPage.xaml