Solving Sudoku with Prolog (2016)(metalevel.at)
metalevel.at
Solving Sudoku with Prolog (2016)
https://www.metalevel.at/sudoku/
77 comments
I've truly enjoyed all the Prolog videos on your channel[0].
I had to program a timetabling system where each event had a specific set of requirements, and your article and video about solving sudokus and the n-queens helped me grasp the problem.
I have only been using Prolog for a month, but I could not go back to Lisp now (at least not without MiniKanren). There's still plenty of stuff I don't understand about Prolog, but it feels very expressive and powerful even with just a superficial understanding of the language.
Thank you so much for your work! Your teaching materials are very accessible for beginners. Hope you will one day make a video about DCGs (Definite Clause Grammars). I wonder if reading Noam Chomsky will help my understanding of them?
Since we are on Hacker News, I think it's interesting to look at PG's experience with Prolog, which unfortunately hasn't been as rewarding as mine:
> There are features, most notably Prolog-style pattern-matching, that seem to promise great savings in length, but turn out only to be useful for writing a few basic sequence operations like append, remove, and so on. Prolog is a great language for writing append; after that it's all downhill.[1]
> A way of expressing programs that was more abstract, but made your programs longer, would not be very enticing. (This is not just a hypothetical example. It happens in Prolog.)[2]
From watching your videos, it's easy to see how concise Prolog programs are though. I find that my own Prolog programs also tend to be extremely brief (compared to Lisp or SQL).
[0]: https://invidio.us/channel/UCFFeNyzCEQDS4KCecugmotg
[1]: http://www.paulgraham.com/arcchallenge.html
[2]: http://www.paulgraham.com/arcll1.html
I had to program a timetabling system where each event had a specific set of requirements, and your article and video about solving sudokus and the n-queens helped me grasp the problem.
I have only been using Prolog for a month, but I could not go back to Lisp now (at least not without MiniKanren). There's still plenty of stuff I don't understand about Prolog, but it feels very expressive and powerful even with just a superficial understanding of the language.
Thank you so much for your work! Your teaching materials are very accessible for beginners. Hope you will one day make a video about DCGs (Definite Clause Grammars). I wonder if reading Noam Chomsky will help my understanding of them?
Since we are on Hacker News, I think it's interesting to look at PG's experience with Prolog, which unfortunately hasn't been as rewarding as mine:
> There are features, most notably Prolog-style pattern-matching, that seem to promise great savings in length, but turn out only to be useful for writing a few basic sequence operations like append, remove, and so on. Prolog is a great language for writing append; after that it's all downhill.[1]
> A way of expressing programs that was more abstract, but made your programs longer, would not be very enticing. (This is not just a hypothetical example. It happens in Prolog.)[2]
From watching your videos, it's easy to see how concise Prolog programs are though. I find that my own Prolog programs also tend to be extremely brief (compared to Lisp or SQL).
[0]: https://invidio.us/channel/UCFFeNyzCEQDS4KCecugmotg
[1]: http://www.paulgraham.com/arcchallenge.html
[2]: http://www.paulgraham.com/arcll1.html
Thank you very much for your kind words! I greatly appreciate your feedback, and I am very glad that you benefit from the videos!
Also, I would like to take this opportunity to thank you all collectively for your thoughtful participation in this thread, your comments and endorsements. Your feedback, encouragement and insights are making this work especially worthwhile!
Also, I would like to take this opportunity to thank you all collectively for your thoughtful participation in this thread, your comments and endorsements. Your feedback, encouragement and insights are making this work especially worthwhile!
> more abstract, but made your programs longer
There are a few main reasons for Prolog code to come out longer than Lisp:
- Prolog style is mostly first order -- there's not a direct equivalent of lambda.
- Mutation is also used less.
- There's an equivalent of Lisp macros, but it's also less common.
- You don't nest function calls, but pass common named arguments instead.
So I can see where he was coming from. On the other hand I'd guess he had his Prolog experience before constraint logic programming was well supported, and certainly before MiniKanren which gives back the conveniences of Lisp and helps you take the pure-declarative subset further.
There are a few main reasons for Prolog code to come out longer than Lisp:
- Prolog style is mostly first order -- there's not a direct equivalent of lambda.
- Mutation is also used less.
- There's an equivalent of Lisp macros, but it's also less common.
- You don't nest function calls, but pass common named arguments instead.
So I can see where he was coming from. On the other hand I'd guess he had his Prolog experience before constraint logic programming was well supported, and certainly before MiniKanren which gives back the conveniences of Lisp and helps you take the pure-declarative subset further.
PG does indeed use a lot of mutation in his Arc code. "Karma" on `vote-for` on HN is just incremented like this:
I was reading through The Reasoned Schemer (which covers MiniKanren). They do a lot of unnesting when translating from functional to logical programming. And yes, this does introduce an additional variable each time, making the logical version slightly longer.
Apart from the `markdown` in the Hacker News code, there is an `unmarkdown` function[0] (whose job is to translate back from HTML to markdown!). In Prolog you could have gotten away with one predicate for that. That's a 50% saving just there. And you could perhaps use DCGs to cut it down further.
Not sure I about Prolog being mostly first order. Plenty of built-in predicates that take predicate arguments, like `maplist`, `findall` and `foldl` that seem to be as commonly used as in Lisp. You might be right about lambdas missing though, so not sure you can emit a predicate (although you could emit the name of a predicate and call it). I'm too new to Prolog to tell, really.
[0]: https://github.com/arclanguage/anarki/blob/master/lib/markdo...
(++ (karma i!by) (case dir up 1 down -1))
I was reading through The Reasoned Schemer (which covers MiniKanren). They do a lot of unnesting when translating from functional to logical programming. And yes, this does introduce an additional variable each time, making the logical version slightly longer.
Apart from the `markdown` in the Hacker News code, there is an `unmarkdown` function[0] (whose job is to translate back from HTML to markdown!). In Prolog you could have gotten away with one predicate for that. That's a 50% saving just there. And you could perhaps use DCGs to cut it down further.
Not sure I about Prolog being mostly first order. Plenty of built-in predicates that take predicate arguments, like `maplist`, `findall` and `foldl` that seem to be as commonly used as in Lisp. You might be right about lambdas missing though, so not sure you can emit a predicate (although you could emit the name of a predicate and call it). I'm too new to Prolog to tell, really.
[0]: https://github.com/arclanguage/anarki/blob/master/lib/markdo...
Re: lambda expressions, it turns out there was a proposal to add them. Maybe it or something like it is in common use by now; I wouldn't know. http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hi...
(It's true that you can write higher-order programs without them. The style was often clumsier and used less, at least as I saw it back when I read much Prolog.)
Re: unnesting, I've toyed with the idea of a slightly fancier Prolog syntax that lets you write nested calls which get desugared to the use of an extra parameter. Of course they'd have to look distinct from functors as data.
(It's true that you can write higher-order programs without them. The style was often clumsier and used less, at least as I saw it back when I read much Prolog.)
Re: unnesting, I've toyed with the idea of a slightly fancier Prolog syntax that lets you write nested calls which get desugared to the use of an extra parameter. Of course they'd have to look distinct from functors as data.
I'm not sure if this is a well-formed question, but ... how does this approach compare to solving such problems with general SAT-solvers? Don't the latter allow you to use techniques that search the space more efficiently?
Or is it hot-swappable in some sense? Could you take Prolog and have it solve a CP problem with a SAT solver doing the work under the hood?
Or is it hot-swappable in some sense? Could you take Prolog and have it solve a CP problem with a SAT solver doing the work under the hood?
The question is perfectly well-formed!
It is, however, very broad, and I try to answer it very broadly.
First, SAT solvers are powerful and efficient. SAT is one of the most studied problems in CS, both from a theoretical and practical perspective. Donald Knuth dedicates a huge portion of The Art of Computer Programming to exactly this topic. For example, quoting from https://www-cs-faculty.stanford.edu/~knuth/news.html:
Satisfiability is far from an abstract exercise in understanding formal systems. Revolutionary methods for solving such problems emerged at the beginning of the twenty-first century, and they've led to game-changing applications in industry. These so-called “SAT solvers” can now routinely find solutions to practical problems that involve millions of variables and were thought until very recently to be hopelessly difficult.
I highly recommend this as a profound treatment of the subject for readers at all levels of expertise.
Second, SAT solvers can be combined seamlessly with Prolog. In Prolog terminology, SAT is CLP(B), constraint logic programming over Boolean variables.
From the perspective of a Prolog application programmer, you simply state what must hold about the variables, using Prolog predicates like conjunction, disjunction etc., you state which variables must be 1 and which must be 0 etc.
Internally, a Prolog system may invoke an external SAT solver, or implement its own version of SAT solving, to find a satisfying assignment. Both approaches exist in the literature and in practice. For example, see A Pearl on SAT Solving in Prolog by Jacob M. Howe and Andy King:
http://www.staff.city.ac.uk/~jacob/solver/
As another approach and reference, I have put together a small page about a different CLP(B) system that internally uses Binary Decision Diagrams (BDDs) to solve SAT instances:
https://www.metalevel.at/clpb/
Third and finally, SAT is a comparatively low-level approach for expressing combinatorial tasks. Perfectly doable (for example, by automatic translation/compilation to SAT), but still low-level. That does not mean that it's inadequate. In fact, some aspects of the "true structure" of a problem may reveal themselves and allow an efficient solution only at that low level.
It is perfectly possible to express Sudoku as a SAT problem, using CLP(B). For example:
It is, however, very broad, and I try to answer it very broadly.
First, SAT solvers are powerful and efficient. SAT is one of the most studied problems in CS, both from a theoretical and practical perspective. Donald Knuth dedicates a huge portion of The Art of Computer Programming to exactly this topic. For example, quoting from https://www-cs-faculty.stanford.edu/~knuth/news.html:
Satisfiability is far from an abstract exercise in understanding formal systems. Revolutionary methods for solving such problems emerged at the beginning of the twenty-first century, and they've led to game-changing applications in industry. These so-called “SAT solvers” can now routinely find solutions to practical problems that involve millions of variables and were thought until very recently to be hopelessly difficult.
I highly recommend this as a profound treatment of the subject for readers at all levels of expertise.
Second, SAT solvers can be combined seamlessly with Prolog. In Prolog terminology, SAT is CLP(B), constraint logic programming over Boolean variables.
From the perspective of a Prolog application programmer, you simply state what must hold about the variables, using Prolog predicates like conjunction, disjunction etc., you state which variables must be 1 and which must be 0 etc.
Internally, a Prolog system may invoke an external SAT solver, or implement its own version of SAT solving, to find a satisfying assignment. Both approaches exist in the literature and in practice. For example, see A Pearl on SAT Solving in Prolog by Jacob M. Howe and Andy King:
http://www.staff.city.ac.uk/~jacob/solver/
As another approach and reference, I have put together a small page about a different CLP(B) system that internally uses Binary Decision Diagrams (BDDs) to solve SAT instances:
https://www.metalevel.at/clpb/
Third and finally, SAT is a comparatively low-level approach for expressing combinatorial tasks. Perfectly doable (for example, by automatic translation/compilation to SAT), but still low-level. That does not mean that it's inadequate. In fact, some aspects of the "true structure" of a problem may reveal themselves and allow an efficient solution only at that low level.
It is perfectly possible to express Sudoku as a SAT problem, using CLP(B). For example:
sudoku(Rows) :-
length(Rows, 9), maplist(same_length(Rows), Rows),
maplist(row_booleans, Rows, BRows),
maplist(booleans_distinct, BRows),
transpose(BRows, BColumns),
maplist(booleans_distinct, BColumns),
BRows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
blocks(As, Bs, Cs), blocks(Ds, Es, Fs), blocks(Gs, Hs, Is).
blocks([], [], []).
blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
booleans_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
blocks(Ns1, Ns2, Ns3).
booleans_distinct(Bs) :-
transpose(Bs, Ts),
maplist(card1, Ts).
card1(Bs) :- sat(card([1],Bs)).
row_booleans(Row, Bs) :-
same_length(Row, Bs),
maplist(cell_boolean, Row, Bs).
cell_boolean(Num, Bs) :-
length(Bs, 9),
sat(card([1],Bs)),
element(Num, Bs, 1).
Thanks for your hard work. I really want to like Prolog, but I often don't know how to fit it into an actual system of use.
My field is power systems which involves solving numerical problems with large sparse matrices and very large scale optimization problems (millions of constraints) using LP and MIP solvers.
The first class of problems can be easily solved with tools like Matlab, Fortran, Python, Julia, C++...etc. The optimization problems can be solved with any language that has a library to talk to a solver.
Prolog is really cool, but I doubt it could solve problems of that size even if given days, much less a few minutes. I'd love to be proven wrong, but it seems like it really excels at these small toy problems. Could you enlighten my ignorance on how it can be used on larger scale problems? Thanks in advance!
My field is power systems which involves solving numerical problems with large sparse matrices and very large scale optimization problems (millions of constraints) using LP and MIP solvers.
The first class of problems can be easily solved with tools like Matlab, Fortran, Python, Julia, C++...etc. The optimization problems can be solved with any language that has a library to talk to a solver.
Prolog is really cool, but I doubt it could solve problems of that size even if given days, much less a few minutes. I'd love to be proven wrong, but it seems like it really excels at these small toy problems. Could you enlighten my ignorance on how it can be used on larger scale problems? Thanks in advance!
I haven't used Prolog at that scale myself, but I'll just add completely unsubstantiated hearsay from the ##Prolog IRC on FreeNode: Someone reported no problems using SWI Prolog for running queries on "59 million facts".
It might also be worth checking Triska's video about n-queens[0] where the last 2/3 is all about optimising the search and using different labelling strategies.
Don't know if it's relevant for your problem, but memoization is also a thing in Prolog[1] like in other languages.
Maybe not the answer you're looking for. Is your system relatively simple to describe? Then we can give it a try...
[0]: https://invidio.us/watch?v=l_tbL9RjFdo
[1]: https://swish.swi-prolog.org/example/tabling.swinb
It might also be worth checking Triska's video about n-queens[0] where the last 2/3 is all about optimising the search and using different labelling strategies.
Don't know if it's relevant for your problem, but memoization is also a thing in Prolog[1] like in other languages.
Maybe not the answer you're looking for. Is your system relatively simple to describe? Then we can give it a try...
[0]: https://invidio.us/watch?v=l_tbL9RjFdo
[1]: https://swish.swi-prolog.org/example/tabling.swinb
59M sounds pretty sweet!
I'll check out Triska's videos when I pick up my Prolog book on writing a text adventure again. It's pretty much the only Prolog book that helps walk me through it without the theory. I do like theory, but I need a high level overview first before I can make sense of anything.
The basics of the system are very easy to describe, but realistic system implementations are waaay more complex and have hundreds of pages of solver code and SQL packages. A very simple example on a tiny system would be the below:
https://www.juliaopt.org/notebooks/Dvorkin%20-%20Power%20sys...
I'll check out Triska's videos when I pick up my Prolog book on writing a text adventure again. It's pretty much the only Prolog book that helps walk me through it without the theory. I do like theory, but I need a high level overview first before I can make sense of anything.
The basics of the system are very easy to describe, but realistic system implementations are waaay more complex and have hundreds of pages of solver code and SQL packages. A very simple example on a tiny system would be the below:
https://www.juliaopt.org/notebooks/Dvorkin%20-%20Power%20sys...
I studied prolog years ago at university and more recently rediscovered the power of solvers (like SCIP). Is not really thought about how the 2 crossed over before. How does prolog compare to a solver these days?
The primary attraction of CLP, i.e., the combination of constraint programming (CP) and logic programming (LP), is that you get a full-blown programming language (most frequently: Prolog) and in addition seamlessly integrated solvers (over integers, rational numbers, Herbrand terms etc.).
CP can of course be hosted on — or provided as library for — other languages too. However, it blends in most seamlessly with a logic programming language like Prolog as its host language.
Regarding efficiency, the top-of-the-line Prolog systems provide many of the most efficient and most sophisticated algorithms for combinatorial optimization tasks that are commercially used.
See for example the customers page of SICStus Prolog for several interesting applications:
https://sicstus.sics.se/customers.html
CP can of course be hosted on — or provided as library for — other languages too. However, it blends in most seamlessly with a logic programming language like Prolog as its host language.
Regarding efficiency, the top-of-the-line Prolog systems provide many of the most efficient and most sophisticated algorithms for combinatorial optimization tasks that are commercially used.
See for example the customers page of SICStus Prolog for several interesting applications:
https://sicstus.sics.se/customers.html
CLP shares some similarity with Satisfiability Modulo Theories (SMT). Is there much overlap in how they are used in practice? When would you reach for SMT over CLP?
I've toyed with trying to use Prolog for procedural map generation in my hobby RPG game. The idea is to feed it a high level human designed map and let it fill in the details. Not sure if you have any thoughts on if it might be suitable for something like that or not.
In general, Prolog is extremely well suited for tasks where partial information needs to be taken into account.
The presence of logic variables, i.e., "true" variables in the sense of logic, is one of the defining characteristics of logic programming languages like Prolog. In comparison, what other programming languages call a "variable", is not really a variable but just some concrete value. In contrast, a logic variable truly stands for anything at all and may be bound to any term (in its domain).
For this reason, Prolog is especially well suited for data that has "holes" in it. For example, Prolog was successfully used to investigate the folding structure of DNA, where hypotheses were available about some aspects, but the overall structure of parts was yet unknown. A Prolog specification allows to "leave out" parts of the specification that are unknown.
Hence, a map generation task where some constraints are specified sounds like a very nice project and potentially great application for a logic programming language. Enjoy!
The presence of logic variables, i.e., "true" variables in the sense of logic, is one of the defining characteristics of logic programming languages like Prolog. In comparison, what other programming languages call a "variable", is not really a variable but just some concrete value. In contrast, a logic variable truly stands for anything at all and may be bound to any term (in its domain).
For this reason, Prolog is especially well suited for data that has "holes" in it. For example, Prolog was successfully used to investigate the folding structure of DNA, where hypotheses were available about some aspects, but the overall structure of parts was yet unknown. A Prolog specification allows to "leave out" parts of the specification that are unknown.
Hence, a map generation task where some constraints are specified sounds like a very nice project and potentially great application for a logic programming language. Enjoy!
It's interesting how Prolog has no concept of 'null' as such; just fresh variables whose value we don't know (yet).
No more null pointer exceptions!
No more null pointer exceptions!
In fact, in some domains (such as SQL), ‘null’ stands for values we dont know: https://modern-sql.com/concept/three-valued-logic
Yes, looks like SQL got that right as well.
I think Prolog is the answer to the question: What if the full stack was relational; not just the database?
I think Prolog is the answer to the question: What if the full stack was relational; not just the database?
[deleted]
I love the simplicity or prolog; I often think it/datalog would be great as a query language for applications.
e.g. instead of Jira having its JQL or whatever, it would just have a prelude, then you'd write things like:
e.g. instead of Jira having its JQL or whatever, it would just have a prelude, then you'd write things like:
my_team_working_on_it(ticket) :-
assigned(ticket, user),
on_team(user, team),
on_team(current_user, team).
assigned(_, current_user)Check out datomic database
Thought it rang a bell from a databases lecture - seems it 'extends' datalog:
https://docs.datomic.com/cloud/whatis/data-model.html#datalo...
Thanks for reminding me, must find an excuse to play with it!
https://docs.datomic.com/cloud/whatis/data-model.html#datalo...
Thanks for reminding me, must find an excuse to play with it!
Also datascript
Prolog is good for discrete search like this, mostly because it's just hiding the underlying search algorithm that other languages would be to be explicit about (but as a result, other languages can search more efficiently).
Other languages can search more efficiently if you write a more efficient search in them, but Prolog can search more efficiently if you write a more efficient search in it, too.
"That's it. On backtracking, this generates increasingly longer lists Ls, and invokes p/1 only on lists of bounded length. Bamm! Iterative deepening. [..] asymptotically optimal under very general assumptions, and you can make it easily available in Prolog yourself. I guess mostly for this reason, the default execution strategy is kept extremely simple. When needed, you can easily implement other search strategies on top of it." - https://www.reddit.com/r/prolog/comments/47fchf/why_depthfir...
"That's it. On backtracking, this generates increasingly longer lists Ls, and invokes p/1 only on lists of bounded length. Bamm! Iterative deepening. [..] asymptotically optimal under very general assumptions, and you can make it easily available in Prolog yourself. I guess mostly for this reason, the default execution strategy is kept extremely simple. When needed, you can easily implement other search strategies on top of it." - https://www.reddit.com/r/prolog/comments/47fchf/why_depthfir...
All computer science problems can be reduced to sorting & searching. ;-D
Is this really true? I was wondering about complexity analysis, for example.
Solving Sudoku smartly with Prolog.
The nice thing with Prolog is that if you don't understand how to program but you understand the rules/logic of the problem. In this case you understand the rules of Sudoku, you can define the board and the rules and Prolog will brute force it for you. Harder to do in other languages.
The nice thing with Prolog is that if you don't understand how to program but you understand the rules/logic of the problem. In this case you understand the rules of Sudoku, you can define the board and the rules and Prolog will brute force it for you. Harder to do in other languages.
I can’t help but to feel delightfully nostalgic whenever I read about Prolog, thanks for writing this up. If you’re interested, I’ve created a set of Prolog exercises about 10 years ago when I was teaching this in college, including one for “advanced Sudoku”:
https://github.com/maebert/prolog_puzzles/blob/master/readme...
https://github.com/maebert/prolog_puzzles/blob/master/readme...
This was a final project in a course I took in college surveying programming languages. I thought Prolog was insanely interesting. Through most of the project I thought it was crazy, but when I finished it made excellent sense.
Since then I've thought a lot about using Prolog for optimized job/task scheduling, but I've never had an actual need to do it.
Since then I've thought a lot about using Prolog for optimized job/task scheduling, but I've never had an actual need to do it.
I did a module in my undergrad degree that used Prolog as the learning tool/language. At the time I didn't understand why Prolog was such a different paradigm (declarative); all I remember is feeling a true sense of joy writing prolog code and running it.
I've never found/made up a reason to try it out since then and no language/system/paradigm has given me the same enjoyment since!
I've never found/made up a reason to try it out since then and no language/system/paradigm has given me the same enjoyment since!
I love the embedded PostScript in the source code. Its always fun to see how other people write their code.
Thank you for noting this!
PostScript is currently underappreciated, and I highly recommend learning it. Among many other uses, I like to use PostScript as a portable animation language to visualize search processes like in this case.
Also, programming PostScript is great fun and in a sense quite timeless: In all likelihood, these definitions will work without change also in the distant future, because PostScript is so widely spread and frequently used.
Newer graphics languages and concepts also take many ideas from PostScript, but PostScript is in my experience still the most fun and flexible of them, at least for a very large set of important use cases.
PostScript is currently underappreciated, and I highly recommend learning it. Among many other uses, I like to use PostScript as a portable animation language to visualize search processes like in this case.
Also, programming PostScript is great fun and in a sense quite timeless: In all likelihood, these definitions will work without change also in the distant future, because PostScript is so widely spread and frequently used.
Newer graphics languages and concepts also take many ideas from PostScript, but PostScript is in my experience still the most fun and flexible of them, at least for a very large set of important use cases.
The only thing prevents me using prolog for proper tasks is not getting its IO: reading/writing files: csv, json.
Any cool (video) tuts on it? I searched a lot but did not find anything "easy".
Any cool (video) tuts on it? I searched a lot but did not find anything "easy".
Say you have a file, `foo.json`, with the content:
Say `foo.csv` containts:
I don't know any good videos that cover this. I'm happy to help with what I can though, and I've also found the ##Prolog IRC on Freenode helpful.
[0]: http://www.pathwayslms.com/swipltuts/
[1]: http://www.pathwayslms.com/swipltuts/html/index.html
{"foo":"bar"}
?- [library(http/json)].
true.
?- open('foo.json', read, Stream), json_read(Stream, Term).
Stream = <stream>(0x557f0cbfb1c0),
Term = json([foo=bar]).
Say `foo.csv` containts:
foo,bar
?- [library(csv)].
true.
?- csv_read_file("foo.csv",Rows).
Rows = [row(foo, bar)].
I don't know any good videos that cover this. I'm happy to help with what I can though, and I've also found the ##Prolog IRC on Freenode helpful.
[0]: http://www.pathwayslms.com/swipltuts/
[1]: http://www.pathwayslms.com/swipltuts/html/index.html
Curious about 2 things:
1) Can it solve especially hard Sudoku puzzles? (ie, expert level where humans often get stuck)
2) Is there a resource somewhere that lists the types of Prolog problems that it excels at solving?
1) Can it solve especially hard Sudoku puzzles? (ie, expert level where humans often get stuck)
2) Is there a resource somewhere that lists the types of Prolog problems that it excels at solving?
1) Yes, and (when there is only one unique solution) it can apparently be found in Prolog without doing an search at all by using constraint logic programming. Check the video in the sudoku article.
2) I'm not the best at answering this as I'm quite new to Prolog, but I'll try. I'd say a) anything you'd use a general purpose programming languge for, b) anything you'd use SQL for, and c) anything that's too difficult to do in either of those.
SWI Prolog[0] has a large standard library and feels very "batteries included".
Perhaps what I wouldn't use it for is mobile apps..? (But then again, there's Tau Prolog[1] which could probably work in a Cordova app).
[0]: http://www.swi-prolog.org/
[1]: http://tau-prolog.org/
2) I'm not the best at answering this as I'm quite new to Prolog, but I'll try. I'd say a) anything you'd use a general purpose programming languge for, b) anything you'd use SQL for, and c) anything that's too difficult to do in either of those.
SWI Prolog[0] has a large standard library and feels very "batteries included".
Perhaps what I wouldn't use it for is mobile apps..? (But then again, there's Tau Prolog[1] which could probably work in a Cordova app).
[0]: http://www.swi-prolog.org/
[1]: http://tau-prolog.org/
How is Prolog ideal for when you'd use SQL? I can understand it if you're talking about querying a CSV file, but the advantage to SQL is that the database with all your data natively supports SQL and it can usually run pretty fast.
Btw: what would it look like to query a small sample CSV file. Like the below example if you wanted to find all cars that are made by Ford?
Brand,Model,Year,Color/n Ford,F150,1999,Black/n Toyota,Yaris,2013,Yellow/n Ford,Mustang,1969,Blue/n
Edit: sorry for not knowing how to format HN properly and show the newline on each of the rows.
Btw: what would it look like to query a small sample CSV file. Like the below example if you wanted to find all cars that are made by Ford?
Brand,Model,Year,Color/n Ford,F150,1999,Black/n Toyota,Yaris,2013,Yellow/n Ford,Mustang,1969,Blue/n
Edit: sorry for not knowing how to format HN properly and show the newline on each of the rows.
Hey, this is good practice!
First we can load the csv library, then read the rows of the csv file, and assert those rows as facts using the `car` identifier. (Doesn't mean `car` like in lisp, obviously, but automobile.)
(I should really have discarded the first line, because right now there's a car, whose brand is 'Brand', and so on. Well, well...)
If we just wanted a list of all the results, we could use the findall/3 predicate.
Something that's neat in Prolog is that you can define recursive relations. In SQL it's easy to define a parent/child relation, but what about ancestor/descendant? (Yes, you can use common table expressions, but the syntax is incredibly complicated.)
Also, you don't need to create database schemas and Prolog, and unification feels seamless as opposed to explicitly declaring the JOINs.
But, in my opinion, where Prolog really shines compared to SQL is that there just isn't that whole object-relational impedance mismatch[0].
[0]: https://en.wikipedia.org/wiki/Object-relational_impedance_mi...
Edit: Ok, my turn quiz!! Say we have these bicycles:
In Prolog that would be:
First we can load the csv library, then read the rows of the csv file, and assert those rows as facts using the `car` identifier. (Doesn't mean `car` like in lisp, obviously, but automobile.)
?- [library(csv)],
csv_read_file('cars.csv',Rows, [functor(car)]),
maplist(assert, Rows).
?- car('Ford', Model, Year, Colour).
Model = 'F150',
Year = 1999,
Colour = 'Black' ;
Model = 'Mustang',
Year = 1969,
Colour = 'Blue'.
(I should really have discarded the first line, because right now there's a car, whose brand is 'Brand', and so on. Well, well...)
If we just wanted a list of all the results, we could use the findall/3 predicate.
Something that's neat in Prolog is that you can define recursive relations. In SQL it's easy to define a parent/child relation, but what about ancestor/descendant? (Yes, you can use common table expressions, but the syntax is incredibly complicated.)
Also, you don't need to create database schemas and Prolog, and unification feels seamless as opposed to explicitly declaring the JOINs.
But, in my opinion, where Prolog really shines compared to SQL is that there just isn't that whole object-relational impedance mismatch[0].
[0]: https://en.wikipedia.org/wiki/Object-relational_impedance_mi...
Edit: Ok, my turn quiz!! Say we have these bicycles:
Brand, Colour, Year
Mosquito, Blue, 2010
Raleigh, Red, 2005
Suzuki, Red, 1998
In Prolog that would be:
bicycle(One_brand, Colour, _),
bicycle(Another_brand, Colour, _),
One_brand \= Another_brand.
Nice quiz :-) My attempt would be:
select b1.Brand as brand1, b2.Brand as brand2
from bicycles as b1
inner join bicycles as b2
on (b1.Colour = b2.Colour)
where b1.Brand <> b2.BrandCool! That's actually really close to the Prolog version.
True that. Only major difference is that I had to explicitly specify how to relate the two brands together in SQL whereas in Prolog it's implicit by using the same variable in two different patterns. I find the idea of a simple Prolog, like a Datalog, very intriguing as a potential simple query engine for apps in mainstream languages–not having to worry about the maps, filters, reduces, flatmaps, and all the other operations we have to do to coax data into the right shapes in line-of-business apps. Unfortunately I just haven't been able to figure out how to do a left outer join (or if that's even the right approach in Prolog :-)
> Unfortunately I just haven't been able to figure out how to do a left outer join (or if that's even the right approach in Prolog :-)
That is probably my main issue with SQL: That the names of some of the keywords are very table-ish and not very semantic; like LEFT OUTER JOIN. I mean, if we have some facts, like how old people are, and what they like to eat, then what does it even mean that any of those facts is to the left or on the inside of another? I can't fit that into my brain.
But let's take an example. We have these sets of facts (which, if they were in SQL, would be in two different tables):
I'm probably getting this wrong, but if we wanted LEFT OUTER JOIN it would be more like:
In Prolog, the comma means 'and', and the semicolon means 'or', so in the second query anyone, who has an age but doesn't like anything, will still be included. In this query, that would be Beatrice. That's a bit like a LEFT OUTER JOIN, isn't it?
> I find the idea of a simple Prolog, like a Datalog, very intriguing as a potential simple query engine for apps in mainstream languages–not having to worry about the maps, filters, reduces, flatmaps, and all the other operations we have to do to coax data into the right shapes in line-of-business apps.
Seen DataScript?[0] I think MiniKanren has also been implemented in most languages. I like how Prolog "forces" a declarative style though.
[0]: https://github.com/tonsky/datascript
That is probably my main issue with SQL: That the names of some of the keywords are very table-ish and not very semantic; like LEFT OUTER JOIN. I mean, if we have some facts, like how old people are, and what they like to eat, then what does it even mean that any of those facts is to the left or on the inside of another? I can't fit that into my brain.
But let's take an example. We have these sets of facts (which, if they were in SQL, would be in two different tables):
age(alice, 20).
age(beatrice, 30).
age(charlie, 90).
likes(alice, carrots).
likes(alice, chips).
likes(charlie, crumpets).
age(Name,Age), likes(Name, Something).
I'm probably getting this wrong, but if we wanted LEFT OUTER JOIN it would be more like:
age(Name,Age); likes(Name, Something).
In Prolog, the comma means 'and', and the semicolon means 'or', so in the second query anyone, who has an age but doesn't like anything, will still be included. In this query, that would be Beatrice. That's a bit like a LEFT OUTER JOIN, isn't it?
> I find the idea of a simple Prolog, like a Datalog, very intriguing as a potential simple query engine for apps in mainstream languages–not having to worry about the maps, filters, reduces, flatmaps, and all the other operations we have to do to coax data into the right shapes in line-of-business apps.
Seen DataScript?[0] I think MiniKanren has also been implemented in most languages. I like how Prolog "forces" a declarative style though.
[0]: https://github.com/tonsky/datascript
Thanks for working through my example question.
I may have to give Prolog another shot at some point!
I may have to give Prolog another shot at some point!
>how would you find the names of any two brands whose bicycles have the same colour?
At first glance I thought it'd just be a group by + having followed by some sort of SELECT to get the first 2 in each group. But apparently doing that top-k in each group is a nightmare in SQL [1].
[1] https://stackoverflow.com/questions/8748986/get-records-with...
At first glance I thought it'd just be a group by + having followed by some sort of SELECT to get the first 2 in each group. But apparently doing that top-k in each group is a nightmare in SQL [1].
[1] https://stackoverflow.com/questions/8748986/get-records-with...
I'm curious on your first point. There are puzzles that have multiple legal plays but only a single solution. In those, guessing/searching is basically required, right?
A valid Sudoku puzzle is such that the given clues admit precisely one solution.
Hence, if you somehow manage to take into account all the initially available information, then no search is required, because, in a sense, the given hints already narrow down the entire space of (ostensibly) possible assignments to a single one.
There are constraint solvers that do this. For example, with the CLP(B) version based on BDDs that I mentioned, the solver internally constructs a Binary Decision Diagram (BDD) which is like a (ideally: more compact) truth table of all assignments that satisfy the requirements.
Therefore, with the CLP(B) version I posted, search is never necessary for valid Sudoku puzzles, because they admit precisely one solution, and the constraint solver deduces this unique solution by reasoning about the decision diagram.
There's a severe drawback to this: The BDD may be exponential in the number of variables. That's a problem, because there are dozens of variables in many Sudoku puzzles. In practice, we are often lucky, and the worst-case space requirements do not arise.
For comparison, the CLP(FD/ℤ) formulation is based on constraint propagation that ensures a certain kind of consistency for all individual constraints in isolation, but not necessarily for the combination of all constraints, i.e., the problem as a whole.
In practice, at least for Sudoku puzzles, this also often leads to finding the unique solution without any search. This may also be the case if only the minimum number of clues for a valid Sudoku puzzle (i.e., 17, per https://arxiv.org/abs/1201.0749) is specified, as the parent mentions. In general, search is still required. In the concrete case of (standard) Sudoku, the required search, if there is any at all, is typically very small, because the many constraints usually narrow down the entire space considerably.
Reducing the amount of required search is the key attraction and goal of the consistency techniques that are used by constraint systems. The available systems differ in how much and how fast they are able to prune inconsistent values, leading to notions such as global consistency, domain consistency, bounds consistency etc. that give some indication of propagation strength.
Hence, if you somehow manage to take into account all the initially available information, then no search is required, because, in a sense, the given hints already narrow down the entire space of (ostensibly) possible assignments to a single one.
There are constraint solvers that do this. For example, with the CLP(B) version based on BDDs that I mentioned, the solver internally constructs a Binary Decision Diagram (BDD) which is like a (ideally: more compact) truth table of all assignments that satisfy the requirements.
Therefore, with the CLP(B) version I posted, search is never necessary for valid Sudoku puzzles, because they admit precisely one solution, and the constraint solver deduces this unique solution by reasoning about the decision diagram.
There's a severe drawback to this: The BDD may be exponential in the number of variables. That's a problem, because there are dozens of variables in many Sudoku puzzles. In practice, we are often lucky, and the worst-case space requirements do not arise.
For comparison, the CLP(FD/ℤ) formulation is based on constraint propagation that ensures a certain kind of consistency for all individual constraints in isolation, but not necessarily for the combination of all constraints, i.e., the problem as a whole.
In practice, at least for Sudoku puzzles, this also often leads to finding the unique solution without any search. This may also be the case if only the minimum number of clues for a valid Sudoku puzzle (i.e., 17, per https://arxiv.org/abs/1201.0749) is specified, as the parent mentions. In general, search is still required. In the concrete case of (standard) Sudoku, the required search, if there is any at all, is typically very small, because the many constraints usually narrow down the entire space considerably.
Reducing the amount of required search is the key attraction and goal of the consistency techniques that are used by constraint systems. The available systems differ in how much and how fast they are able to prune inconsistent values, leading to notions such as global consistency, domain consistency, bounds consistency etc. that give some indication of propagation strength.
I'll see if I can find my references again, but pretty sure this is not true. You can have a specified puzzle that has a single solution but requires a guess. I agree most are not this way, but they can be made.
If you find such a puzzle, please let me know!
Assuming the CLP(B) solver is correctly implemented, the CLP(B) solution I posted will give the unique solution without any search.
On the other hand, it is comparatively easy to find puzzles where the CLP(ℤ) version will require search, even if only a small amount.
Assuming the CLP(B) solver is correctly implemented, the CLP(B) solution I posted will give the unique solution without any search.
On the other hand, it is comparatively easy to find puzzles where the CLP(ℤ) version will require search, even if only a small amount.
I'll have to dive on it more, but https://news.ycombinator.com/item?id=14246452 is last time I remember discussing it. I thought the point was that sometimes searches were needed. Did I misunderstand? Have things changed? (Neither would surprise me.)
It seems a bit misleading to talk about not needing search, if you are only referring to a very specific part in the implementation of a constraint solver. Without context, I would have interpreted it as being able to avoid an exponential search over the solution space, which is (for general sudoku, under mild assumptions) impossible. So while it appears to be an advantage in principle, the claim is actually 'sometimes this is faster in practice'.
> In those, guessing/searching is basically required, right?
Apparently no guessing is required!
In Prolog it's fine for a variable (that represents a square in a sudoku puzzle) to be somewhere between 1 and 9. (Yes, that can be a bit mind-boggling, because in most other programming languages a variable can't really be either this or that. As far as I know, not even in SQL which is also somewhat declarative.)
You might get in a situation where one square (let's call it A) is between 1 and 3 and two other squares on the same row (let's call them B and C) are both between 1 and 2. One constraint that we have given is that all numbers on a row must be distinct (because that's one of the rules of a sudoku puzzle), so given those constraints and facts, Prolog can deduce that the value of the first square must be 3.
Therefore no guessing (or searching + backtracking) is required; only constraint propagation.
This is what the query would look like in a Prolog REPL:
(Triska's explanation is probably more in depth and correct, but I thought I'd just chip in with my newbie way of explaining how I understand this. But seriously, check his videos. They're great stuff. The illustrations make the explanations accessible.)
[0]: http://www.swi-prolog.org/
Apparently no guessing is required!
In Prolog it's fine for a variable (that represents a square in a sudoku puzzle) to be somewhere between 1 and 9. (Yes, that can be a bit mind-boggling, because in most other programming languages a variable can't really be either this or that. As far as I know, not even in SQL which is also somewhat declarative.)
You might get in a situation where one square (let's call it A) is between 1 and 3 and two other squares on the same row (let's call them B and C) are both between 1 and 2. One constraint that we have given is that all numbers on a row must be distinct (because that's one of the rules of a sudoku puzzle), so given those constraints and facts, Prolog can deduce that the value of the first square must be 3.
Therefore no guessing (or searching + backtracking) is required; only constraint propagation.
This is what the query would look like in a Prolog REPL:
[library(clpfd)], % load library for constraint logic over finite domains
A in 1..3, B in 1..2, C in 1..2, all_distinct([A,B,C]).
A = 3,
B in 1..2,
all_distinct([3, B, C]),
C in 1..2.
(Triska's explanation is probably more in depth and correct, but I thought I'd just chip in with my newbie way of explaining how I understand this. But seriously, check his videos. They're great stuff. The illustrations make the explanations accessible.)
[0]: http://www.swi-prolog.org/
But when you are at a state like
A = 3,
B in 1..2,
all_distinct([3, B, C]),
C in 1..2.
> In fact, you don't even have a guarantee that a solution exists.
If there's more than one soluton or no possible solution, then it's not a "well-posed" sudoku puzzle; at least according to Wikipedia here:
> The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.[0]
But yes, I guess for puzzles with multiple solutions, you'd necessarily have to search for them. It's also possible to make a mine sweeper field that has no valid assignment of mines[1], yet usually mine sweeper games don't do that.
As you note about this state,
[0]: https://en.wikipedia.org/wiki/Sudoku
[1]: https://worldcomp-proceedings.com/proc/p2016/PDP7565.pdf
If there's more than one soluton or no possible solution, then it's not a "well-posed" sudoku puzzle; at least according to Wikipedia here:
> The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.[0]
But yes, I guess for puzzles with multiple solutions, you'd necessarily have to search for them. It's also possible to make a mine sweeper field that has no valid assignment of mines[1], yet usually mine sweeper games don't do that.
As you note about this state,
B in 1..2,
all_distinct([B, C]),
C in 1..2.
[0]: https://en.wikipedia.org/wiki/Sudoku
[1]: https://worldcomp-proceedings.com/proc/p2016/PDP7565.pdf
You're right about Sudoku of course, but I thought we were talking of the general case. Even more general than recreational puzzles: Real-world applications of constraint programming won't generally be so nice as to have a single solution.
Right, I think this is somewhat just talking past each other. You don't have to backtrack on the values, but it is essentially searching on the constraints.
That is, if you have a board where there are multiple legal moves on every open position, but only one solution, you still have to pick which constraint to propagate to find the solution. No?
That is, if you have a board where there are multiple legal moves on every open position, but only one solution, you still have to pick which constraint to propagate to find the solution. No?
[deleted]
In my experience you need a very contrived Sudoku instance to make it hard for a computer. Usually even the "hard" instances can be quickly solved by a computer search.
Peter Norvig's Sudoku solver using constrain propagation is a nice demonstration of the mini-Kanren approach.[0]
I spoke at RubyConf a few years ago on the basics of logic programming and constraint propagation, and demoed a (poorly-coded) solver interface.[1]
[0]https://norvig.com/sudoku.html
[1]https://m.youtube.com/watch?v=f5Bi6_GOIB8
I spoke at RubyConf a few years ago on the basics of logic programming and constraint propagation, and demoed a (poorly-coded) solver interface.[1]
[0]https://norvig.com/sudoku.html
[1]https://m.youtube.com/watch?v=f5Bi6_GOIB8
In my opinion, a key attraction of Prolog is the regularity of its syntax and the relation between its syntax and semantics.
I mean not only homoiconicity, but something beyond that.
For example, one of the first questions of Prolog beginners is usually: "Why does my predicate fail for a specific query?"
Prolog allows us to mechanically find and give a minimal explanation why a query fails. We can do this by systematically generalizing the program and show a minimal fragment that still fails. We can mechanically generalize a program by using logic variables instead of concrete values, and by removing goals (i.e., constraints) from conjunctions.
A key attraction of Prolog is that if you take any pure program, and replace any of the goals by true/0, you still get a valid and more general (or at least equally general) program.
For example, take the Prolog program:
For example, why does the most general query, i.e., ?- my_list(Ls)., fail?
A possible explanation could like like this:
No other language I have seen gives comparable guarantees and ways of debugging. For example, suppose I remove a single form in a miniKanren program. The result may no longer even constitute a valid program, and even if it does, I am not aware of any meaningful general property that can be said about the remaining program.
The ability to systematically generate explanations like this seems to be quite unique to logic programming languages like Prolog.
I mean not only homoiconicity, but something beyond that.
For example, one of the first questions of Prolog beginners is usually: "Why does my predicate fail for a specific query?"
Prolog allows us to mechanically find and give a minimal explanation why a query fails. We can do this by systematically generalizing the program and show a minimal fragment that still fails. We can mechanically generalize a program by using logic variables instead of concrete values, and by removing goals (i.e., constraints) from conjunctions.
A key attraction of Prolog is that if you take any pure program, and replace any of the goals by true/0, you still get a valid and more general (or at least equally general) program.
For example, take the Prolog program:
my_list(Ls) :-
Ls = [a,b|Rs],
Ls = [a,c|Rs].
For example, why does the most general query, i.e., ?- my_list(Ls)., fail?
A possible explanation could like like this:
my_list(Ls) :-
Ls = [a,b|Rs],
* Ls = [a,c|Rs].
:- op(920,fy, *). *_.
No other language I have seen gives comparable guarantees and ways of debugging. For example, suppose I remove a single form in a miniKanren program. The result may no longer even constitute a valid program, and even if it does, I am not aware of any meaningful general property that can be said about the remaining program.
The ability to systematically generate explanations like this seems to be quite unique to logic programming languages like Prolog.
I personally think it is a little overkill to use Prolog to solve sudokus, as there is a simple mapping of sudokus to exact covers. The resulting exact covers are rather small and can usually be solved within a fraction of a second using Knuth's Algorithm X, even for hard sudokus. http://www.iwriteiam.nl/D1009.html#9
I would love to see Prolog implemented in hardware like the Lisp machines.
It's been done, though only in an academic setting:
https://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5991.html
https://www.researchgate.net/publication/242056713_Special_o... (sorry to link to ResearchGateKeeper, though somehow by closing the tab, deleting cookies, and opening the tab I managed to get it to give me the PDF without needing to log in, lol)
https://www.sciencedirect.com/science/article/pii/S074310669... (Elsevier, urgh)
I'm sure a bit of web searching will turn up more. It looks like having special purpose hardware for Prolog is useful, which I don't find too surprising. But if you make hardware, you need someone to give you money for it.
As an aside, I wonder now much of the use of Lisp machines was non-academic. I know that there were actual commercial companies selling them, but where those mostly university spinoffs selling back to universities?
https://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/5991.html
https://www.researchgate.net/publication/242056713_Special_o... (sorry to link to ResearchGateKeeper, though somehow by closing the tab, deleting cookies, and opening the tab I managed to get it to give me the PDF without needing to log in, lol)
https://www.sciencedirect.com/science/article/pii/S074310669... (Elsevier, urgh)
I'm sure a bit of web searching will turn up more. It looks like having special purpose hardware for Prolog is useful, which I don't find too surprising. But if you make hardware, you need someone to give you money for it.
As an aside, I wonder now much of the use of Lisp machines was non-academic. I know that there were actual commercial companies selling them, but where those mostly university spinoffs selling back to universities?
> It's been done, though only in an academic setting
See the Melcom PSI computer from Mitsubishi.
http://museum.ipsj.or.jp/en/computer/other/0009.html
> As an aside, I wonder now much of the use of Lisp machines was non-academic. I know that there were actual commercial companies selling them, but where those mostly university spinoffs selling back to universities?
I would think that roughly 10000 hardware Lisp machines were built (incl. embedded boards). Quite a lot went into research, but not just academic research, but also company R&D.
Some machines were built as deployment machines and were used by military, government agencies (like NASA) and also commercial.
Notable were for example the graphics systems by Symbolics which were widely used in high-end graphics for TV and animation studios. A lot of computer animated logos you were seeing in TV in the mid/end 80s were done with them.
Examples:
https://www.youtube.com/watch?v=Cwer_xKrmI4
https://www.youtube.com/watch?v=n21FSKDjObg
But there were a bunch of other early deployed applications on Lisp Machines: 3d cad (iCAD), American Express Authorizer (credit authorization expert system), scheduling for the Hubble Space Station, scheduling for power plant operations, seat allocation optimization for swissair, early military troop virtual reality training system, satellite image processing, ...
See the Melcom PSI computer from Mitsubishi.
http://museum.ipsj.or.jp/en/computer/other/0009.html
> As an aside, I wonder now much of the use of Lisp machines was non-academic. I know that there were actual commercial companies selling them, but where those mostly university spinoffs selling back to universities?
I would think that roughly 10000 hardware Lisp machines were built (incl. embedded boards). Quite a lot went into research, but not just academic research, but also company R&D.
Some machines were built as deployment machines and were used by military, government agencies (like NASA) and also commercial.
Notable were for example the graphics systems by Symbolics which were widely used in high-end graphics for TV and animation studios. A lot of computer animated logos you were seeing in TV in the mid/end 80s were done with them.
Examples:
https://www.youtube.com/watch?v=Cwer_xKrmI4
https://www.youtube.com/watch?v=n21FSKDjObg
But there were a bunch of other early deployed applications on Lisp Machines: 3d cad (iCAD), American Express Authorizer (credit authorization expert system), scheduling for the Hubble Space Station, scheduling for power plant operations, seat allocation optimization for swissair, early military troop virtual reality training system, satellite image processing, ...
Triska on the front page! Sweet.
It was in large part thanks to "The Power of Prolog" that I was able to figure out a nice solution to the "Zebra" puzzle:
It was in large part thanks to "The Power of Prolog" that I was able to figure out a nice solution to the "Zebra" puzzle:
/*
Via https://www.metalevel.at/prolog/puzzles
The "Zebra Puzzle" https://en.wikipedia.org/wiki/Zebra_Puzzle
- There are five houses.
- The Englishman lives in the red house.
- The Spaniard owns the dog.
- Coffee is drunk in the green house.
- The Ukrainian drinks tea.
- The green house is immediately to the right of the ivory house.
- The Old Gold smoker owns snails.
- Kools are smoked in the yellow house.
- Milk is drunk in the middle house.
- The Norwegian lives in the first house.
- The man who smokes Chesterfields lives in the house next to the man with the fox.
- Kools are smoked in the house next to the house where the horse is kept.
- The Lucky Strike smoker drinks orange juice.
- The Japanese smokes Parliaments.
- The Norwegian lives next to the blue house.
Now, who drinks water? Who owns the zebra?
In the interest of clarity, it must be added that each of the five houses is painted
a different color, and their inhabitants are of different national
extractions, own different pets, drink different beverages and smoke
different brands of American cigarets [sic].
One other thing: in statement 6, right means your right.
*/
:- use_module(library(clpfd)).
house_next_to(H0, H1) :- abs(H0 - H1) #= 1.
/* Thanks https://www.metalevel.at/prolog/puzzles */
puzzle(Vars) :-
Vars = [GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse,
Englishman, Spaniard, Ukrainian, Norwegian, Japanese,
Dog, Snails, Fox, Horse, Zebra,
Coffee, Tea, Milk, OrangeJuice, Water,
OldGold, Kools, Chesterfields, LuckyStrike, Parliaments
],
Vars ins 1..5,
all_distinct([GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse]),
all_distinct([Englishman, Spaniard, Ukrainian, Norwegian, Japanese]),
all_distinct([Dog, Snails, Fox, Horse, Zebra]),
all_distinct([Coffee, Tea, Milk, OrangeJuice, Water]),
all_distinct([OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]),
Englishman #= RedHouse,
Spaniard #= Dog,
Coffee #= GreenHouse,
Ukrainian #= Tea,
GreenHouse #= 1 + IvoryHouse,
OldGold #= Snails,
Kools #= YellowHouse,
Milk #= 3,
Norwegian #= 1,
house_next_to(Chesterfields, Fox),
house_next_to(Kools, Horse),
LuckyStrike #= OrangeJuice,
Japanese #= Parliaments,
house_next_to(Norwegian, BlueHouse).
/*
Then to print out the solution after loading the program above use:
puzzle([
GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse,
Englishman, Spaniard, Ukrainian, Norwegian, Japanese,
Dog, Snails, Fox, Horse, Zebra,
Coffee, Tea, Milk, OrangeJuice, Water,
OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]),
label([
GreenHouse, RedHouse, IvoryHouse, YellowHouse, BlueHouse,
Englishman, Spaniard, Ukrainian, Norwegian, Japanese,
Dog, Snails, Fox, Horse, Zebra,
Coffee, Tea, Milk, OrangeJuice, Water,
OldGold, Kools, Chesterfields, LuckyStrike, Parliaments]).
*/
/*
Boring Prolog Sudoku.
*/
:- use_module(library(clpfd)).
puzzle(Vars) :-
Vars = [
A11, A12, A13, A14, A15, A16, A17, A18, A19,
A21, A22, A23, A24, A25, A26, A27, A28, A29,
A31, A32, A33, A34, A35, A36, A37, A38, A39,
A41, A42, A43, A44, A45, A46, A47, A48, A49,
A51, A52, A53, A54, A55, A56, A57, A58, A59,
A61, A62, A63, A64, A65, A66, A67, A68, A69,
A71, A72, A73, A74, A75, A76, A77, A78, A79,
A81, A82, A83, A84, A85, A86, A87, A88, A89,
A91, A92, A93, A94, A95, A96, A97, A98, A99],
Vars ins 1..9,
all_distinct([A11, A12, A13, A14, A15, A16, A17, A18, A19]),
all_distinct([A21, A22, A23, A24, A25, A26, A27, A28, A29]),
all_distinct([A31, A32, A33, A34, A35, A36, A37, A38, A39]),
all_distinct([A41, A42, A43, A44, A45, A46, A47, A48, A49]),
all_distinct([A51, A52, A53, A54, A55, A56, A57, A58, A59]),
all_distinct([A61, A62, A63, A64, A65, A66, A67, A68, A69]),
all_distinct([A71, A72, A73, A74, A75, A76, A77, A78, A79]),
all_distinct([A81, A82, A83, A84, A85, A86, A87, A88, A89]),
all_distinct([A91, A92, A93, A94, A95, A96, A97, A98, A99]),
all_distinct([A11, A21, A31, A41, A51, A61, A71, A81, A91]),
all_distinct([A12, A22, A32, A42, A52, A62, A72, A82, A92]),
all_distinct([A13, A23, A33, A43, A53, A63, A73, A83, A93]),
all_distinct([A14, A24, A34, A44, A54, A64, A74, A84, A94]),
all_distinct([A15, A25, A35, A45, A55, A65, A75, A85, A95]),
all_distinct([A16, A26, A36, A46, A56, A66, A76, A86, A96]),
all_distinct([A17, A27, A37, A47, A57, A67, A77, A87, A97]),
all_distinct([A18, A28, A38, A48, A58, A68, A78, A88, A98]),
all_distinct([A19, A29, A39, A49, A59, A69, A79, A89, A99]),
all_distinct([A11, A21, A31, A12, A22, A32, A13, A23, A33]),
all_distinct([A41, A51, A61, A42, A52, A62, A43, A53, A63]),
all_distinct([A71, A81, A91, A72, A82, A92, A73, A83, A93]),
all_distinct([A14, A24, A34, A15, A25, A35, A16, A26, A36]),
all_distinct([A44, A54, A64, A45, A55, A65, A46, A56, A66]),
all_distinct([A74, A84, A94, A75, A85, A95, A76, A86, A96]),
all_distinct([A17, A27, A37, A18, A28, A38, A19, A29, A39]),
all_distinct([A47, A57, A67, A48, A58, A68, A49, A59, A69]),
all_distinct([A77, A87, A97, A78, A88, A98, A79, A89, A99]).For comparison, here is my own solution in Python 3 to the Zebra Puzzle. To me this solution seems sorter and easier to understand:
from itertools import permutations as perms
houses = range(1,6) # houses numbered 1,2,3,4,5
for Englishman, Spaniard, Ukrainian, Norwegian, Japanese in perms(houses):
if Norwegian != 1: continue # rule 10
for red, green, ivory, yellow, blue in perms(houses):
if Englishman != red: continue # rule 2
if green != ivory + 1: continue # rule 6
if Norwegian not in [blue-1,blue+1]: continue # rule 15
for coffee, tea, milk, oj, water in perms(houses):
if coffee != green: continue # rule 4
if Ukrainian != tea: continue # rule 5
if milk != 3: continue # rule 9
for oldgold, kools, chesterfields, luckys, parliaments in perms(houses):
if kools != yellow: continue # rule 8
if luckys != oj: continue # rule 13
if Japanese != parliaments: continue # rule 14
for dog, snails, fox, horse, zebra in perms(houses):
if Spaniard != dog: continue # rule 3
if oldgold != snails: continue # rule 7
if chesterfields not in [fox-1,fox+1]: continue # rule 11
if kools not in [horse-1, horse+1]: continue # rule 12
person = {Englishman: 'Englishman', Spaniard: 'Spainard',
Ukrainian: 'Ukrainian', Norwegian: 'Norwegian', Japanese: 'Japanese'}
print(f'{person[water]} drinks water')
print(f'{person[zebra]} owns the zebra')The deep nesting and negation of the tests made this look weird to me and harder to see how the main idea was exhaustive searching of all permutations. I think it's clearer when the constraints are separated from the searching:
People = collections.namedtuple('People', ['Englishman', 'Spaniard', 'Ukrainian', 'Norwegian', 'Japanese']) # etc.
def rule_10(people): return people.Norwegian == 0
def rule_2(people, color): return people.Englishman == color.Red
def rule_6(color): return color.Ivory - color.Green == 1
def rule_15(people, color): return abs(people.Norwegian - color.Blue) == 1
def rule_4(beverage, color): return beverage.Coffee == color.Green
# etc.
constraints = [ rule_1, rule_2, ... ] # etc.
def inject(func, vars=locals):
signature = inspect.signature(func)
args_from = operator.attrgetter(signature.parameters.keys())
return func(*args_from(vars))
houses = range(0,5)
for people in map(People._make, perms(houses)):
for color in map(Color._make, perms(houses)):
for beverage in map(Beverage._make, perms(houses)):
for cigarette in map(Cigarette._make, perms(houses)):
for pet in map(Pet._make, perms(houses)):
if all(map(inject, constraints)):
print(f'The {People._fields[beverage.Water]} drinks water')
print(f'The {People._fields[pet.Zebra]} owns the zebra')
sys.exit(0)
print(f'Sorry, no idea who drinks water or owns a zebra')
sys.exit(1)
Enumerating all solutions and checking will always be the simplest approach for find the set of inputs returning true for a decision problem. However, a constraint solver will not necessarily have to enumerate all solutions.
Yes it would take a long time to do it that way since there would be roughly 25 billion solutions to evaluate. My Python program doesn’t do this and runs very fast. Elapsed time for this program is approximately 0.03 seconds on my 2013 desktop and it finds all possible solution (in this case one).
Normally, inner loops are executed more times than outer loops, but in this program the bodies of the inner loops are skipped (because of the continue statements) when constraints fail in the the outer loops. The five loop bodies are executed a total of 120, 2880, 1440, 1440, 960 times respectively (I put counters in each loop to determine this, all counters were initialized before any of the loops begin).
I wrote this program (for a different version of this same problem) while waiting for my daughter to come downstairs to be driven to school one morning around five years ago. (See https://news.ycombinator.com/item?id=7734998)
Normally, inner loops are executed more times than outer loops, but in this program the bodies of the inner loops are skipped (because of the continue statements) when constraints fail in the the outer loops. The five loop bodies are executed a total of 120, 2880, 1440, 1440, 960 times respectively (I put counters in each loop to determine this, all counters were initialized before any of the loops begin).
I wrote this program (for a different version of this same problem) while waiting for my daughter to come downstairs to be driven to school one morning around five years ago. (See https://news.ycombinator.com/item?id=7734998)
Brilliant! Cool to see the two paradigms side-by-side.
If there was a similar puzzle that had more than one solution, would it be straight-forward to do that using for loops as well in Python? (Curious if you can do backtracking that way)
If there was a similar puzzle that had more than one solution, would it be straight-forward to do that using for loops as well in Python? (Curious if you can do backtracking that way)
Yes, this approach does find every solution and it is using backtracking. See my other reply to a sibling comment.
[deleted]
Prolog is extremely well-suited for solving combinatorial tasks like Sudoku puzzles, and also for tough practical challenges such such as timetabling, scheduling and allocation tasks on an industrial scale.
The key feature that makes Prolog so efficient and frequently used for such tasks is constraint propagation, provided via libraries or as a built-in feature in many Prolog system. Fast and efficient constraint propagation is often an important reason for buying a commercial Prolog system.
In this example, I am using CLP(FD/ℤ), constraint logic programming over finite domains/integers, the amalgamation of constraint programming (CP) and logic programming (LP), which blend especially seamlessly. I have uploaded a short video that shows how it works for Sudoku puzzles:
https://www.metalevel.at/prolog/videos/sudoku
If you are interested in constraint solving, a few related videos may also be useful:
https://www.metalevel.at/prolog/videos/n_queens
https://www.metalevel.at/prolog/videos/knights_and_knaves
https://www.metalevel.at/prolog/videos/map_colouring
These videos are all work in progress, and they may be replaced by better versions at any time. However, the links above will always point to the latest version.
Enjoy!