Category Archives: PROLOG

数独を解くプログラム

昔いくつか書いたPrologのパズルソルバーのコードがリンク切れになってたので再掲します(これから4回分続きます)。

まずは数独のソルバーです。

これ書いたときはまだ制約論理プログラミングのことを知らなかったのでPure Prologで書いてます(SWI-Prolog)。

その後SWI-Prologのマニュアルのclpfdライブラリの説明の箇所の数独ソルバーのプログラムを発見して衝撃を受け、制約論理プログラミングの勉強を開始したのであった。

プログラム
解説と実行結果

以下は僕が衝撃を受けたSWI-Prologのマニュアルに載っている数独ソルバー(僕のプログラムよりエレガントかつ速い)

実行結果:

Project Euler Problem 62

Problem 62

ECLiPSe CLP で解きました。
ほぼPure Prolog で、制約論理の述語は使用してません。
自分のマシンで約9秒。

プログラム:

コマンドライン:

?- time(go).
Yes (9.22s cpu)

標準出力:

<解答伏せます。>

Success, times: 9.218750s thread, 9.219+0.000s process, 9.224s real

Project Euler Problem 59

Problem 59

全体の文字数 – 「何文字がA-Z a-zの範囲だったか」 の数値をコストとして計算し、一番コストが小さくなるものをbb_minで調べました。
あんまり効率よくないプログラムで、1900秒くらいかかりました…遅いな…
あとテキストの文字数が3の倍数というところは前もって調べてて、それをあてにしたプログラムになってます(文字数が3の倍数でないとdecryptでこける)

ソース

実行結果

Project Euler Problem 52

Problem52

ECLiPSeで解きました。
処理時間は自分のマシン(Intel(R) Core(TM) i5-3340M CPU @ 270GHz)で6.5秒くらい。
見どころ?はECLiPSeのlogical-loopで書いた順列permutationと、propiaで数値を入れ替えた制約を作っているところ
logical loop はループ用のサブ述語みたいなアホっぽい定義がなくなってコードがエレガントになるのでSWI-Prologでもぜひ正式採用してほしい。
桁のところは一般化してなく、1桁、2桁、3桁… と手入力で増やしながら確認しました
(bb_minでそれぞれの桁での最小の数値が取れるようにしてます)。

プログラム:

実行結果(解答伏せます):

Project Euler Problem79

久しぶりにProject Eulerやってみました。
制約論理プログラミングで解きました。ほとんど頭使ってない…
SWI-Prologです。

Problem79

回答伏せます

[Prolog] DCGで双方向性のある述語を作成

最近stackoverflowでPrologの質問に良く回答しているのですが、面白そうな問題があり、自分でもプログラムを作ってみました。

質問

内容は、[1,2,3,4,1,4,7,5,7,8,9] のようなリストが与えられた際に「続いている数字は[最初の数字,最後の数字]の形で表し、そうでないものは単体の数字で表したようなリストを生成する という問題です。
[1,2,3,4,1,4,7,5,7,8,9]は[[1,4],1,4,7,5,[7,9]] に変換されます。

作っているうちにどんどんアイデアがわいてきて、はじめは長いプログラムだったのがDCG使ってエレガントな方法で実装する方法を思いつき、最後には入出力逆転してもOKなような非常に汎用的な形で作成できました。

ECLiPSeで作成(多分他の環境でも問題なく動きます):

実行結果:

最後のマッチング例は「やってみたら、できた」という実験で、自分の予想を上回る汎用性が実現できていてびっくりしました。

入出力がどちらもリストの述語を作成するときは、工夫すると双方向性が実現できることがあると思います。

Prologの真髄に触れたような気がしました。

[Prolog]最近の勉強

最近あんまりPrologのブログ書いてませんが、ずっと研究してます(具体的にブログに書けるような結果が出てない)現在はECLiPse(IDEのほうじゃなくて制約プログラミングのほう)の勉強してます。

書くネタないので今までのPrologの勉強の流れを説明すると以下のような感じで進んできました(スパンは数年単位)

広井さんのページでPrologの基礎を把握しいくつかのパズルのソルバーを作る(20年近く前に大学の授業で受けていたがあまり深いところまで理解していなかった)

SWI-Prologのマニュアル読み込むうちCLPFDを発見し衝撃を受け、勉強開始

ProjectEulerでPrologで問題を解くうち、正答者スレでECLiPseを用いてSWIの自分のプログラムよりはるかに速いスピード(数十倍)で結果を出している人を発見して衝撃を受ける。プログラムの内容自体はCLPFDを使用した自分のとそんなに変わらなかった。

ECLiPseの勉強を始める。だんだんSWI-PrologのCLPFDがSicstusやECLiPseの制約ソルバーに比べると「オモチャ」レベルだったということがわかってくる。また、SWI-PrologのCLPFD開発者のmarkus triskaさんは開発の継続をsicstusで行うみたいな記述を最新のSWIのマニュアルで見つけた。

また、ECLiPse は node.jsを使用してjavascriptで呼び出せるらしく、ECLiPseの勉強はWeb系の仕事でのちのち面白い威力を発揮するかもしれないと期待を抱く。

ECLiPseには、自分がSWIのCLPFDでどうしてもできなかった自作制約の作成がPropiaとCHRの2種類の方法で可能なことを知り、そちらの勉強を開始。SWIのCLPFDの自作制約の作成方法はマニュアルが意味不明だった(まだ完成してないとも書いてある)

Propiaのほうは大体の概要を把握。任意の述語をそのまま制約にできて、Propagationの厳密さをinferという述語の引数でコントロールするという仕組みらしい

CHRの勉強に移る。ルール自体は少ないが結構難しくてどのように作ればよいかなかなか理解できない。CHRはHaskellやJavaなどでも使用できるようだ。

CHRが並列計算に向いていると知り、ハードウェアで実行したりGPUを使用したりして解くといった論文をネットで見つけて読み始め、少しECLiPseの勉強から浮気する。

「CHRをGPUを用いて計算する」方法を記載した論文を見つけるが実際にやった時の速度比較が載ったものを見つけることができなかったので、そういう論文が出ないかを定期的にウォッチすることに決め、とりあえず論文リサーチはやめる。CHRをハードウェアでやった論文では数万倍とかのスピードで解いてるの見つけたが良く読むとCHRの機構だけではなくプログラムのほうもハードウェア化していてちょっとちがうだろという感じだった(論文で使用している最大公約数求めるみたいな単純なロジックしかハードウェア化できなくて現実的ではないし、そもそもそれってCHR自体の速さではない)

またECLiPseのCHRの勉強に戻る

△いまここです。

まあ日本語の情報がないです。
ずーーっと英語読んでます。ECLiPse、日本で使ってる人100人もいないんじゃなかろうか。日本のECLiPse界では望まずして第一人者になりそうです。もしそういう人たちいれば仲間に入れてほしい。誰か一緒に勉強しませんか?情報交換して一緒に研究の成果を教えあいましょう

CHRはルール自体は3種類しかなくて単純なんだけど以下が良くわかってなくてまだ自作の制約を作るまで至ってない

・labelingの振る舞い
・制約の述語の変数に「値を設定した時?」と「新しい制約がセットされたとき?」に再度bodyがfireされるらしいがそこらへんの振る舞い

多分CHRの制約の形が「自分がCLPFDを勉強してきた上で持っている制約のイメージ」とかなりずれているのが理解が滞ってる理由だと思います。

自分の数年の目標であるTantrixというパズルのソルバーをECLiPseの自作制約でいつか作れれば良いなあ。手続き型だと現在のスキルで多分作れるが制約プログラミングで作るという目標がありわざとそういう手法では作ってない

…………………………うーん。

この記事書いてるうちになんで自分がCHRを必死に勉強してるのか分かんなくなってきた…
Propiaで間に合ってるような気がしてきたので、そっちでやるかな…。CHRは「つかうとすごいスピードが出るケースが見つかる(並列処理とかで)」とか「CHRで書かれためちゃくちゃエレガントなコードを見つける」みたいな状況になってから改めて勉強しようかな。
CHRの良さをご存じの方いらっしゃればぜひ koyahata*koyahatataku.com(*を@に変更) にメール下さい。そうでなくてもProlog関連で勉強中の人はぜひ連絡取り合って一緒に勉強しましょう

ブログまとめるのも自分の行動を見直す良い機会になりますね

よし方向転換

PrologでForループ

SicstusやECLiPSeではイテレータとかいうのを使ってDo-Loopが記述できるのですが、もともとECLiPSeで実現されていた論理プログラミングのループ(Logical Loop)を紹介する以下の論文を2002年にSchimpfさんという人が書いていて、これでLogical Loopが広まったようです?

Logical Loop

まだ深く読み込んでませんが、SWIにもなんかの方法で実装できるような気もする… lambdaライブラリとかを使う?

発見

CLP(B)を使ってProjectEuler の No.172を解いている記事を見つけた。

CLPFD の開発者のMarkus Triskaさんが書いている。

The Boolean Constraint Solver of SWI-Prolog: System Description

他にも No.161 に関する記載もありますね。

…しかし律儀に全数を数え上げる方法を使ってるからムチャクチャ効率悪くて、メモリ20Gbyte積んだマシン使って7時間もかかって解いてる…ダメだなこりゃ…

Probrem 185 Number Mind

Project Eulerの問題はものすごくたくさんあるし(2017.05.12現在で600問弱)自分の目的はProlog関連技術の威力を試すためにやっている側面が強く全問制覇が目標ではないので、これからはまずそれに適した問題から解いてゆこうと思う。

Probrem 185 Number Mind

この問題は「ザ・制約論理プログラミング用問題」というくらい制約論理プログラミングに向いていると感じ手を付けた。ほとんど探索の工夫をせずに問題の定義のみ書いて、ちゃんと解けている。

今回プログラムを作っていてハマってしまった箇所があり、勉強になった。
・術語内で制約論理用変数を使いそれを呼び元に返さない状態でlabelingを行うと、それらの変数がガベージコレクトされておかしくなる。
・上記のエラーメッセージはguess述語の呼び出しをかなり減らした状態から順々に増やしてゆかないと見ることができない(全て書いた状態で実行すると一晩返ってこないプログラムとなり時間をかけて正しく動いているようにも見え、プログラムが間違っているという手がかりは全く得られなかった)

上記のような手続き型言語と異なる独自の開発ノウハウが結構あるので、これからも要勉強である。

labelingのオプションでも相当速度が変わる。基本はffもしくはffcをつけるで良いと思う。

この問題は Difficulty Rating が55% で、 2017年5月12日現在で解いた人が 2273 人しかいない問題だそうで、今まで自分が解いた中では一番難しい問題のようだ。

個人的には今までチャレンジかつ正答した問題の中では 191 Prize String が一番難しく、これは1週間位組み合わせ・順列系のサイトを調べまくって解いた。自分の解き方はエレガントでなかったが、正答者のみ見れるスレッドによると動的計画法でエレガントかつ超スピードで解けるようだ。

Number Mindの問題は前述のハマり以外はとくに問題はなかった。正答者スレによるとECLiPSeとかいう(IDEのほうではない)同じく制約論理ライブラリを使って解いている人がいた。その人のコードもほぼ問題の定義のみが記述されているエレガントなものだった。自分のスピードより数十倍速いようだったので、Eclipse恐るべしと思った。いつか勉強するかも。

正答者スレを見ることにより、自分より遥かに優秀な取り組み方をしている人の使用言語やソースコードを確認できるのも Project Euler の良いところだと思う。

ソースコード:

実行結果: