クロスワードパズルを解くプログラムについて。

質問

学校の授業で独学でプログラミングを学ぶ授業があり、
現在授業の一環としてSWI-prologを学んでいます。

そこで、prologを用いて
キー無しのクロスワードパズルを解くプログラムを組むことになりました。

キー無しのクロスワードパズルとは、
単語群から空白に文字数の合う単語を入れて埋めていくパズルです。

今回は英単語でやろうとしています。

自力でやってみようと思ったのですが、全く手が付けられず、
先生にアドバイスをいただきましたが、自分の理解力不足なのかよくわかりませんでした。

先生がおっしゃっていたことは
・prologの辞書を用いる
・1次元配列でつくる
といったようなものでしたが、よくわかりません。
自分で本を購入し、自分なりに噛み砕きながらやってみましたができませんでした。

辞書はどこからか入手するのでしょうか。
また、1次元配列をprolog上でどうやって書けばいいのでしょうか。
C言語で配列はやっているので概念はわかっています。

そして、クロスワードパズルを解くプログラムを教えていただけないでしょうか。
文章が長くなり、申し訳ありません。

よろしくお願い致します。

回答No.6

ki073 · ベストアンサー

help(is_set).で確認してください。クロスワードの場合は同じ単語が選ばれると都合が悪いだろうと思い入れています。printは表示です。

>辞書を作る際に、どのような構造にするのが一番良いと思われるでしょうか？
No.4の方法がPrologらしくて好きなのですが。データのお持ち方と簡単なルールの定義だけですので、全然プログラムらしくない。でも他のプログラム言語ではこんな書き方ができないことが多いので。

No.1のような持ち方は嫌いではないですが、その都度文字を取り出さないといけないので、検索に時間がかかりそうです。No.4のように山盛りのルールを書く必要がないので、プログラムらしいといえばプログラムらしいのですが、どうでしょうか。

これらの2つの方法で別々に作ってみるのはどうでしょうか。そんなに手間はかからないはずです。

あとリストでもつ方法もありますが、Prologの場合にはあまりメリットはないように思います。この方法は他のプログラム言語では普通のやりかたですが。

それとアトムではなく"the"のように"で挟む方法もあります。いろいろ試してみてください。

お礼

返事が大変遅くなり申し訳ございません。
非常に助かりました。
おかげ様できちんと動作するプログラムを作成することができました。
また、質問させていただいた際にはぜひよろしくお願いいたします。

回答No.5

ki073

No.3で一時間もかかったと書きましたが、どうもバグでそうなったみたいです。
どの方法をしても1秒以内に結果がでてきます。
No.1に書いたデータの持ち方で十分なようです。
char_match()を使わずに下記のword_nth_char()に書き換えています。

テストしたのを書いておきます。
?- word_nth_char(S1, 4, 1, C1), word_nth_char(S11, 3, 1, C1),
word_nth_char(S1, 4, 3, C2), word_nth_char(S2, 3, 1, C2),
word_nth_char(S3, 4, 1, C3), word_nth_char(S11, 3, 3, C3),
word_nth_char(S3, 4, 3, C4), word_nth_char(S2, 3, 3, C4),
word_nth_char(S3, 4, 2, C5), word_nth_char(S4, 2, 1, C5),
word_nth_char(S3, 4, 4, C6), word_nth_char(S5, 2, 1, C6),
is_set([S1,S2, S3,S4,S5,S11]), print([S1, S2, S3,S4,S5,S11]).

http://park1.wakwak.com/~english/quiz/crossword.html
の真ん中あたりにあるのを使いました。枠だけ使っています。
word_nth_char(S1, 4, 1, C1)
はNo.4に書いたのと基本的には同じです。
最初の引数は単語(Atom型です), 次が単語の文字数、文字が一致する位置、一致する文字
の順番です。お騒がせしました。

もっと大きなのにすると速度差が出るかもしれませんが。

お礼

引数の数が一致している必要があるとは…
だから
words(the, t, h, e).
のように書いてもコンパイルが通らないのですね。
勉強になりました。

そしてさらなるご回答本当にありがとうございます。
非常にわかりやすいソースコードで感激しました。

No.4に書いていただいたサンプルプログラムをもとに
No.5に添付していただいたURLの例題を無事に解くことができました。
泣きそうなぐらい感激しました…本当にありがとうございます。

また質問になってしまいますが、
is_set([S1,S2, S3,S4,S5,S11]), print([S1, S2, S3,S4,S5,S11]).
の部分について詳しく解説お願いしたいです。

また、辞書を作る際に、どのような構造にするのが一番良いと思われるでしょうか？

お手数おかけしますが、よろしくお願いします…。

回答No.4

ki073

Prologは引数の数が一致している必要が有ります。
words(String1)は引数が1つですので、words(blue,b,l,u,e).などとはマッチングしません。

プログラム例を書いておきます。
words(the, t, h, e).
words(has, h, a, s).
words(use, u, s, e).
words(us, u, s).
words(his, h, i, s).

word_nth_char(Atom, 2, 1, Char) :- words(Atom, Char, _).
word_nth_char(Atom, 2, 2, Char) :- words(Atom, _, Char).
word_nth_char(Atom, 3, 1, Char) :- words(Atom, Char, _, _).
word_nth_char(Atom, 3, 2, Char) :- words(Atom, _, Char, _).
word_nth_char(Atom, 3, 3, Char) :- words(Atom, _, _, Char).
のように引数の数ごとにルールを作成しておきます。
?- word_nth_char(S1,3,2,C1), word_nth_char(S2,3,1,C1), word_nth_char(S2,3,3,C2), word_nth_char(S3,3,2,C2).

もしかしたら、
words("the").のような感じでも（確かめていませんが）そこそこ速度はでるかもしれません、

お礼

ありがとうございました。

回答No.3

ki073

No.1, 2です。
ちょっと面白そうだったので、プログラムを作ってみました。
単語を4000語程度登録して、インターネットで探したクロスワードを解いてみました。
2～4文字の6単語から構成される小さなものです。
No.1の方式のものでは、最初の答えが出るまでに一時間程度かかり、実用的とはとても言えないものでした。

単語の文字数と共通文字の位置を計算しながら実行されるので、文字数だけでもデータとして持っていた方がと思い、
words(blue, 4).
のようにしたのですが、これでも遅いままでした。
次に、文字に分け
words(blue, b, l, u, e).
のようにしたら、ものすごく速くなりました。一秒もかからずに結果がでてきました。こっちの方がPrologらしいプログラムになりますし。

お礼

お返事が遅くなり申し訳ありません。
すごくわかりやすい解説本当に助かります。

以前教えてくださったURLの単語を
words()に入れていくことで辞書が完成するのでしょうか？

以前のサンプルプログラムとこの回答を組み合わせて
このようなプログラムを煮詰めていけばいいのでしょうか…

words(red,r,e,d).
words(blue,b,l,u,e).
words(yellow,y,e,l,l,o,w).
words(green,g,r,e,e,n).
words(purple,p,u,r,p,l,e).
char_match(Match_pos1, Match_pos2, Match_Char1, String1, String2) :- words(String1), atom_chars(String1, List1), nth1(Match_pos1, List1, Match_Char1), words(String2), atom_chars(String2, List2), nth1(Match_pos2, List2, Match_Char2), Match_Char1=Match_Char2.

回答No.2

ki073

課題ということなので、まずは自力で調べてみてください。
このあたりを参考に
http://www.geocities.jp/m_hiroi/prolog/index.html
http://www.wakayama-u.ac.jp/~miurah/Knowledge-System-2012/Prolog.pdf

PrologはCなどと随分雰囲気が違うので、かなり戸惑いました。最初はプログラムをどこに書いていいのか分からなかったです。
二番目のがそのあたりのことも参考になります。

分からないことがありましたら書き込んでください。と言っても私も初心者ですが。

できればお礼欄に書き込んでください、そうするとこちらにメールが届くので、
補足欄だとメールが届かないので書き込んだことが分からなく、放置される可能性が高いです。

お礼

ありがとうございました。

回答No.1

ki073

英単語の辞書でしたら、例えば「高校までに習う英単語」などで検索すれば基本的な英単語を入手できます。
また、出現頻度別に整理されたものもあります。
http://dazy.tumblr.com/post/1036059941/horn-list-100-most-common-words

スペルチェク用の辞書で公開されているものもあります。こちらの方は数が多すぎるような気もします。

＞1次元配列でつくる
多分リストのことかなあ？

Prologはほとんど使いませんのでもっと良い方法があるかも知れませんが、サンプルプログラムを載せておきます。

words(red).
words(blue).
words(yellow).
words(green).
words(purple).
char_match(Match_pos1, Match_pos2, Match_Char1, String1, String2) :- words(String1), atom_chars(String1, List1), nth1(Match_pos1, List1, Match_Char1), words(String2), atom_chars(String2, List2), nth1(Match_pos2, List2, Match_Char2), Match_Char1=Match_Char2.
次のような感じで検索できます。
?- char_match(2, 5, C, S1, S2).
これで2番目と5番目が同じ文字単語を検索できます。

お礼

ありがとうございました。

補足

おおお非常に助かります！
すごくわかりやすいです。

また、ひとつ質問になってしまいますが、
辞書はreadやwrite関数というものを使うらしいのですが
プログラムのソースに書き込めばいいのでしょうか？