数理パズル自動生成システム
【課題】
唯一解の数理パズルを高速に生成することができるシステムを提供する。
【解決手段】
複数解を持つようなパズルであれば一般に生成は容易である。
そこで本パズル自動生成エンジンはパズルの持つ解の個数に着目し、
その値が減少するように制約条件を部分的に繰り返し変更してやることで
最終的に唯一解のパズルを得ることを特徴とする。
但し解の個数を計算するのは通常困難であるため
その代用として、不確定変数の個数もしくは候補数の総和を用いる。
唯一解の数理パズルを高速に生成することができるシステムを提供する。
【解決手段】
複数解を持つようなパズルであれば一般に生成は容易である。
そこで本パズル自動生成エンジンはパズルの持つ解の個数に着目し、
その値が減少するように制約条件を部分的に繰り返し変更してやることで
最終的に唯一解のパズルを得ることを特徴とする。
但し解の個数を計算するのは通常困難であるため
その代用として、不確定変数の個数もしくは候補数の総和を用いる。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、雑誌などでよく見かける筆記具を用いて解くタイプの数理パズルの
自動生成手法に関するものである。
【背景技術】
【０００２】
従来、パズルの問題のほとんどは作家による手作りであった。
一部のパズルではプログラムを用いて問題の自動生成も行われていた。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
これは次のような欠点があった。
従来の方法では、見栄え・解き心地ともに一定のレベルを満たした問題を
高速かつ大量に生成することはできなかった。
本発明は、以上の欠点をなくすためになされたものである。
【課題を解決するための手段】
【０００４】
複数解を持つようなパズルであれば一般に生成は容易である。
そこでパズルの持つ解の個数に着目し、その値が減少するように
制約条件を部分的に繰り返し変更してやることで最終的に
唯一解のパズルを得る。但し解の個数を計算するのは一般に困難であるため
その代用として、不確定変数の個数もしくは候補数の総和を用いる。
【０００５】
本発明は、主として盤面状態を管理するステータス部(Status)、問題を解くためのソルバー部(Solver)、それらを用いて問題を生成するジェネレータ部(Generator)からなる。以下ではパズルの定義と各部の役割について説明する。
【０００６】
パズルに関する諸定義：
ここで扱うパズルとは数学的観点からすれば制約充足問題に位置づけられる。これはいくつかの変数に対して与えられた制約を満たすようにそれらの値を決定する問題である。
全ての制約充足問題のうち、変数とその制約に対してある種の枠組みを設けたものをパズルと呼ぶ。パズルの例としてはナンプレ・魔方陣・虫食い算などが挙げられる。世間一般に広く知られているパズルの特徴として、人が感覚的に理解しやすい制約が設けられているという点が挙げられる。
あるパズルのルールとして定められた枠組みの中で、変数の組とそれらに対する制約を具体的に決めたものをそのパズルに対する問題と呼ぶ。
ある問題に対し、どの制約も満たしているように変数の値が与えられたものをその問題の解と呼ぶ。通常パズルの問題は解が唯一に定まるように作られているが、ここでは説明の便宜上、解が存在しない又は複数の解があるようなものも問題と呼ぶことにする。
【０００７】
ステータス部の役割：
ステータス部は盤面状態を管理する部分である
変数の値及びそれらが取り得る候補、並びにそれらに付随する情報を管理する。
【０００８】
ソルバー部の役割：
ソルバー部は問題を解く部分である。
入力された問題に対し、制約から値が一意に確定する変数に対してはその値を出力。
複数解が存在し、変数の値が一意に定まらない場合は不定として出力。
妥当な値が存在しない場合は解なしと出力する。
【０００９】
ジェネレータ部の役割：
ジェネレータ部は問題を生成する部分である。
入力された初期解とヒント配置から特定のパズルの唯一解の問題を出力する。
【００１０】
アルゴリズムの概要：
ジェネレータは初期解とヒント配置から種となる問題（唯一解とは限らない）を生成し、ソルバーに通す。ジェネレータはソルバーの出力結果における未確定変数の個数をチェックする。これが０のとき、即ち全ての変数が一意に確定したとき問題は唯一解となり完成である。
未確定変数の個数が０でない場合、ジェネレータは問題に対して局所的な変更を行い再びソルバーに通す。このとき出力結果における未確定変数の個数が先ほどの結果より減少しているならば唯一解の問題に近づいたと判断し、その変化を残して次の変更を行う。未確定変数の個数が減少しないもしくは解が存在しない場合は変更箇所を元に戻して再び変更を行う。
以上の操作を繰り返し、未確定変数の個数が０になる（生成成功）もしくは規定以上の変更を施しても不確定変数の個数が減少しない場合（生成失敗）手続きを終了する。
本発明は、以上のアルゴリズムを適用したパズル自動生成システムである。
【発明の効果】
【００１１】
本発明の有効性を実証すべく「ナンバープレース」（以下ナンプレ）と呼ばれる種類のパズルに対して実際に自動生成エンジンを作成し問題の自動生成を試みた。
【００１２】
ナンプレのルール：
ナンプレとは３×３の九つの領域に分けられた９×９の盤面の各列および各領域に、１から９までの数を一つずつ配置するパズルである。盤面にはヒントとしてあらかじめいくつかの数字が与えられている。
【００１３】
仕様：
入力
表出数字（ヒント）の位置を意味する９×９のブーリアン配列
ナンプレの解としての条件を満たした９×９の整数配列
出力（成功時）：trueの位置を表出数字とする唯一解のナンプレ
出力（失敗時）：ジェネレータ部での処理を終えた最終盤面
【００１４】
実現方法：
アルゴリズムの概要で記した処理はパズルの種類によって具体的な実現方法が大きく異なる。ここではナンプレに特化した自動生成エンジンについて説明を行う。まずジェネレータは入力された初期解とヒント配置から種となる問題を一つ生成する。これは単に初期解から与えられたヒントパターンだけを残して他の数字を除くことで実現する。続いて種となる問題はソルバーに通され、その結果に応じてジェネレータは問題に対し局所的な変更を行っていく。ナンプレにおいてこの処理は単純に表出数字の変更である。ただし今回の仕様では表出数字となるべきパターンが固定されているため許されるのはあくまでもパターン上にある数字の変更だけで、ヒントの箇所の移動や追加は行わない。具体的な変更手順については割愛する。
【００１５】
実験内容：
一試行ごとに異なるヒント配置と初期解を入力として計一万問のナンプレを作成し、それに要した時間を計測した。用いるヒント配置のパターンはパズル作家が問題を作成する上で平均とされるヒント数が２４個付近で、かつヒントの配置が点対称になっているものとした。
【００１６】
結果：
パソコン（Windows XP, Celeron®
CPU 2.80GHz）で１問当たり約２０ミリ秒程度で作成することができた。数十分程度かかっていた手作りはもとより従来の高速とされるナンプレ自動生成エンジンと比べても二桁から三桁ほど高速化されている。
【発明を実施するための最良の形態】
【００１７】
以下、本発明を実施するための最良の形態についてナンプレを例に取り説明する。
パズルによって最適な適用法は異なる。
【００１８】
ステータス部：変数の値とその候補に加え、各列各ブロックにおいてある数が入る候補となるマス数、あるマスに入る候補数などを保持する。ソルバーはこれらの値を参照することで解答作業を効率よく行うことができる。
【００１９】
ソルバー部：いくつかの状態遷移規則（一般には手筋と呼ばれる）に基づく代入を繰り返すことで論理的に演繹できる部分のみ変数を確定させるものを使用する。ジェネレータを通して呼び出される際、他と一部だけが異なる似通った問題を高速に多数解くことが要求されるため、変化のあった周辺のみを次の探索対象にする再帰型ソルバーを用いるのが望ましい。
【００２０】
ジェネレータ部：ヒントの数字を変化させる度にソルバーを呼び出して一から解き直すのは非常に無駄である。このため、共通した箇所を持つ問題を一括りにして共通部分のみを残して解かせたものを保存しておく。その上で、異なる部分のヒントを新たに注ぎ足し、その箇所だけソルバーにかけるようにする。ここで上で述べたような特性を備えたソルバーが必要となる。
【００２１】
本アルゴリズムは単純な原理で実現されており、非常に短いコードで実現できるため
携帯、小型ゲーム機などでの利用も考えられる。
【図面の簡単な説明】
【００２２】
【図１】本発明の模式図である。
【技術分野】
【０００１】
この発明は、雑誌などでよく見かける筆記具を用いて解くタイプの数理パズルの
自動生成手法に関するものである。
【背景技術】
【０００２】
従来、パズルの問題のほとんどは作家による手作りであった。
一部のパズルではプログラムを用いて問題の自動生成も行われていた。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
これは次のような欠点があった。
従来の方法では、見栄え・解き心地ともに一定のレベルを満たした問題を
高速かつ大量に生成することはできなかった。
本発明は、以上の欠点をなくすためになされたものである。
【課題を解決するための手段】
【０００４】
複数解を持つようなパズルであれば一般に生成は容易である。
そこでパズルの持つ解の個数に着目し、その値が減少するように
制約条件を部分的に繰り返し変更してやることで最終的に
唯一解のパズルを得る。但し解の個数を計算するのは一般に困難であるため
その代用として、不確定変数の個数もしくは候補数の総和を用いる。
【０００５】
本発明は、主として盤面状態を管理するステータス部(Status)、問題を解くためのソルバー部(Solver)、それらを用いて問題を生成するジェネレータ部(Generator)からなる。以下ではパズルの定義と各部の役割について説明する。
【０００６】
パズルに関する諸定義：
ここで扱うパズルとは数学的観点からすれば制約充足問題に位置づけられる。これはいくつかの変数に対して与えられた制約を満たすようにそれらの値を決定する問題である。
全ての制約充足問題のうち、変数とその制約に対してある種の枠組みを設けたものをパズルと呼ぶ。パズルの例としてはナンプレ・魔方陣・虫食い算などが挙げられる。世間一般に広く知られているパズルの特徴として、人が感覚的に理解しやすい制約が設けられているという点が挙げられる。
あるパズルのルールとして定められた枠組みの中で、変数の組とそれらに対する制約を具体的に決めたものをそのパズルに対する問題と呼ぶ。
ある問題に対し、どの制約も満たしているように変数の値が与えられたものをその問題の解と呼ぶ。通常パズルの問題は解が唯一に定まるように作られているが、ここでは説明の便宜上、解が存在しない又は複数の解があるようなものも問題と呼ぶことにする。
【０００７】
ステータス部の役割：
ステータス部は盤面状態を管理する部分である
変数の値及びそれらが取り得る候補、並びにそれらに付随する情報を管理する。
【０００８】
ソルバー部の役割：
ソルバー部は問題を解く部分である。
入力された問題に対し、制約から値が一意に確定する変数に対してはその値を出力。
複数解が存在し、変数の値が一意に定まらない場合は不定として出力。
妥当な値が存在しない場合は解なしと出力する。
【０００９】
ジェネレータ部の役割：
ジェネレータ部は問題を生成する部分である。
入力された初期解とヒント配置から特定のパズルの唯一解の問題を出力する。
【００１０】
アルゴリズムの概要：
ジェネレータは初期解とヒント配置から種となる問題（唯一解とは限らない）を生成し、ソルバーに通す。ジェネレータはソルバーの出力結果における未確定変数の個数をチェックする。これが０のとき、即ち全ての変数が一意に確定したとき問題は唯一解となり完成である。
未確定変数の個数が０でない場合、ジェネレータは問題に対して局所的な変更を行い再びソルバーに通す。このとき出力結果における未確定変数の個数が先ほどの結果より減少しているならば唯一解の問題に近づいたと判断し、その変化を残して次の変更を行う。未確定変数の個数が減少しないもしくは解が存在しない場合は変更箇所を元に戻して再び変更を行う。
以上の操作を繰り返し、未確定変数の個数が０になる（生成成功）もしくは規定以上の変更を施しても不確定変数の個数が減少しない場合（生成失敗）手続きを終了する。
本発明は、以上のアルゴリズムを適用したパズル自動生成システムである。
【発明の効果】
【００１１】
本発明の有効性を実証すべく「ナンバープレース」（以下ナンプレ）と呼ばれる種類のパズルに対して実際に自動生成エンジンを作成し問題の自動生成を試みた。
【００１２】
ナンプレのルール：
ナンプレとは３×３の九つの領域に分けられた９×９の盤面の各列および各領域に、１から９までの数を一つずつ配置するパズルである。盤面にはヒントとしてあらかじめいくつかの数字が与えられている。
【００１３】
仕様：
入力
表出数字（ヒント）の位置を意味する９×９のブーリアン配列
ナンプレの解としての条件を満たした９×９の整数配列
出力（成功時）：trueの位置を表出数字とする唯一解のナンプレ
出力（失敗時）：ジェネレータ部での処理を終えた最終盤面
【００１４】
実現方法：
アルゴリズムの概要で記した処理はパズルの種類によって具体的な実現方法が大きく異なる。ここではナンプレに特化した自動生成エンジンについて説明を行う。まずジェネレータは入力された初期解とヒント配置から種となる問題を一つ生成する。これは単に初期解から与えられたヒントパターンだけを残して他の数字を除くことで実現する。続いて種となる問題はソルバーに通され、その結果に応じてジェネレータは問題に対し局所的な変更を行っていく。ナンプレにおいてこの処理は単純に表出数字の変更である。ただし今回の仕様では表出数字となるべきパターンが固定されているため許されるのはあくまでもパターン上にある数字の変更だけで、ヒントの箇所の移動や追加は行わない。具体的な変更手順については割愛する。
【００１５】
実験内容：
一試行ごとに異なるヒント配置と初期解を入力として計一万問のナンプレを作成し、それに要した時間を計測した。用いるヒント配置のパターンはパズル作家が問題を作成する上で平均とされるヒント数が２４個付近で、かつヒントの配置が点対称になっているものとした。
【００１６】
結果：
パソコン（Windows XP, Celeron®
CPU 2.80GHz）で１問当たり約２０ミリ秒程度で作成することができた。数十分程度かかっていた手作りはもとより従来の高速とされるナンプレ自動生成エンジンと比べても二桁から三桁ほど高速化されている。
【発明を実施するための最良の形態】
【００１７】
以下、本発明を実施するための最良の形態についてナンプレを例に取り説明する。
パズルによって最適な適用法は異なる。
【００１８】
ステータス部：変数の値とその候補に加え、各列各ブロックにおいてある数が入る候補となるマス数、あるマスに入る候補数などを保持する。ソルバーはこれらの値を参照することで解答作業を効率よく行うことができる。
【００１９】
ソルバー部：いくつかの状態遷移規則（一般には手筋と呼ばれる）に基づく代入を繰り返すことで論理的に演繹できる部分のみ変数を確定させるものを使用する。ジェネレータを通して呼び出される際、他と一部だけが異なる似通った問題を高速に多数解くことが要求されるため、変化のあった周辺のみを次の探索対象にする再帰型ソルバーを用いるのが望ましい。
【００２０】
ジェネレータ部：ヒントの数字を変化させる度にソルバーを呼び出して一から解き直すのは非常に無駄である。このため、共通した箇所を持つ問題を一括りにして共通部分のみを残して解かせたものを保存しておく。その上で、異なる部分のヒントを新たに注ぎ足し、その箇所だけソルバーにかけるようにする。ここで上で述べたような特性を備えたソルバーが必要となる。
【００２１】
本アルゴリズムは単純な原理で実現されており、非常に短いコードで実現できるため
携帯、小型ゲーム機などでの利用も考えられる。
【図面の簡単な説明】
【００２２】
【図１】本発明の模式図である。
【特許請求の範囲】
【請求項１】
唯一解の数理パズル（制約充足問題）を自動生成することを目的としたシステムで、
問題の生成過程において以下に示すような特徴を有するもの。
（イ）
複数解を持つ問題に部分的な変更を繰り返して唯一解に近づける。
（ロ）
唯一解までの距離が何らかの形で定義されている。
（ハ）
距離が減少するように制約条件の変更を行う。
【請求項１】
唯一解の数理パズル（制約充足問題）を自動生成することを目的としたシステムで、
問題の生成過程において以下に示すような特徴を有するもの。
（イ）
複数解を持つ問題に部分的な変更を繰り返して唯一解に近づける。
（ロ）
唯一解までの距離が何らかの形で定義されている。
（ハ）
距離が減少するように制約条件の変更を行う。
【図１】
【公開番号】特開２００９−２８４２８（Ｐ２００９−２８４２８Ａ）
【公開日】平成２１年２月１２日（２００９．２．１２）
【国際特許分類】
【出願番号】特願２００７−１９７６１０（Ｐ２００７−１９７６１０）
【出願日】平成１９年７月３０日（２００７．７．３０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＷＩＮＤＯＷＳ
【出願人】（３９９１２４７３８）株式会社タイムインターメディア (1)
【Ｆターム（参考）】
【公開日】平成２１年２月１２日（２００９．２．１２）
【国際特許分類】
【出願日】平成１９年７月３０日（２００７．７．３０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＷＩＮＤＯＷＳ
【出願人】（３９９１２４７３８）株式会社タイムインターメディア (1)
【Ｆターム（参考）】
[ Back to top ]