パズル自動生成エンジン

タイムインターメディアは、世界最大の合体ナンプレ問題制作や、あらゆる業務で発生する複雑な組み合わせ問題を最適化する最適化AIプラットフォーム TENKEIのサービスなど、パズル自動生成の研究によって培った技術を用いて、幅広い分野に貢献してまいりました。

そんな技術により興味を持っていただきたいとの想いから、 問題を解くプログラムの作成ではなく、さらにその先の「問題を作る(作問)プログラム」を公開します。
公開されるソースコードは、数多くのパズル問題を世に生み出し、世界記録の達成を果たした藤原 博文によって作られたものです。
パズル作家が多くの時間を費やすような難解で複雑な問題も、もちろん作成可能です。
本ソースコードと一般的なPCで、短時間で良質な問題を自動生成します。

また、世の中にある様々な最適化問題にも応用が可能な「進化計算」というAIアルゴリズムを用いた作成を行うため、今回のプログラムで学習したアルゴリズムをパズル以外のことへ応用することが可能です。

以下に、ナンプレ自動生成エンジンの作成手順とソースコードを公開しておりますので、お気軽にエンジン自作に挑戦してみてください。

ナンプレに対する取り組み、ソースコード公開へ至った想い、そしてプログラムへ挑戦する方々へのメッセージを制作者の藤原 博文からお伝えいたします。

ナンプレ(ナンバープレイス)とは、歴史ある数字パズルゲームです。
海外では、SUDOKU(数独)とも呼ばれ、世界的な流行が今も続いています。

1. 図1の様に、9×9のマスが、太さの違う罫線で描かれており、マスの一部に数字が入っています。
2. たて9マス、よこ9マス、太線で囲まれた９マス(ブロックと呼ぶ)の中には、１から９までの数字がそれぞれ１つずつ入ります。
3. 2.のルールにしたがって、空白の各マスに、から9の数字を入れます。
4. この問題を、ルールに従って解くと図2のように全マスが埋まります。どのたて列、どのよこ列、どのブロックを見ても、1から9までの数字が1つずつ配置されています。

図3のように最初から見える数字(ヒント)の配置を与えて、これらのマスの数字を適当に決めることで、解が1つだけ(ユニーク解)の問題(最初の図)を自動生成する方法を説明します。
ただ、適当に数字を並べて入れ替える程度では、延々と入れ替えを繰り返してもユニーク解にはなりません。

人工知能技術の1つに進化計算という方法があり、これは生物の進化にならって、少しずつ良くする(進化する)ことで最終的な目的を達成しようという方法です。ナンプレの自動生成の場合には、解がただ1つ(ユニーク解)のちゃんとした問題を完成させます。

人工知能技術というと高度で無理と思うかもしれませんが、とても簡単な方法しか使わないので、プログラミングを始めたばかりの方でも十分理解できると思います。プログラムもそんなに長くなく、全体を把握しやすくなっています。

人工知能の中の、進化計算という技術の中で最もやさしい手法である山登り法を用いて説明します。
山登り法は簡単な問題にしか適用できない方法ですが、ここではそれをさらに簡単化した方法を紹介しています。

9×9の標準的なナンプレ問題の自動作成なら、これでも楽勝です。
プログラミング言語はJavaを用いていますが、Java以外の言語でも全然問題ありません。Java,C,C++,C#などが一般的に適しているでしょうが、Pythonでもできます。Scratchでナンプレの自動生成を作った例もあります。

本プログラムは、2019年2月に、タイのタマサート大学シリントーン国際工学部の学生を日本に招待し、インターンシップ実習をしたときに用意したプログラムが元になっています。
当時はRaspberry Pi3で動かしており、Javaの開発環境であるEclipseも使っていませんでした。

Javaのプログラムは自由に改変してご利用ください。実際に問題を便利に作ったり、できた問題を画面上で遊ぶためにはGUIも必要でしょう。でも、本説明はあくまで自動生成はこうすれば簡単にできるという一例を示すのが目的ですので、本質的以外の部分は全部省略しています。

Javaのコーディングも、模範的でない箇所も多々あります。また、ファイル入力の扱いなど、柔軟性を欠いているところもありますが、それらも読者への課題として残したままにしています。

本格的な進化計算を行う場合は、山登り法ではなく遺伝的アルゴリズムを使うことが多くなります。また、計算量が増えるため、高速化にマルチスレッドを使うのが一般的です。
さらに、現実の最適化問題は、複数の相反する項目の調整も必要になることが多く、多目的遺伝的アルゴリズムが使われるようになります。

本プログラムのソースコードを使い、進化計算の第一歩を経験してください。
そして皆さんの技術や興味がさらに広がり、進んでいかれることを期待しています。

採用情報

タイムインターメディアでは一緒に働く技術者を募集しています。

• 新卒採用 募集要項
• キャリア採用 募集要項
• 会社説明会 開催要項

タイムインターメディア公式ブログ・SNS

• 技術者ブログ
• Facebook
• Twitter

最適化AIプラットフォーム TENKEIは難解な課題の最適解を導き出す進化計算のAIソリューションを提供します。