Thank you very much for the publicity, I greatly appreciate your interest!
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:
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.
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).
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!
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:
(++ (karma i!by) (case dir up 1 down -1))
At first this looks nice and simple, but when you have to write `unvote`, you're in trouble (because not all votes increase karma, and you'll have to figure out whether the particular vote being unvoted did).
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.
(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?
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:
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:
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:
But the general point remains: Working - for example - with integers or Herbrand terms, or rational numbers etc., is more high-level and a more natural fit for many combinatorial tasks of practical relevance, and often allows also more efficient and more complete propagation, because more of the high-level structure of a task can be taken into account.
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!
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...
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:
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:
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!
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...
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”:
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.
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!
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.
Triska's videos are quite theoretical. Anne Ogborn has a lot of good real world programming tutorials[0]. Can highly recommend the web app tutorial[1].
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.
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).
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?
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.)
If we want to find a Ford, then we can enter this query:
?- car('Ford', Model, Year, Colour).
Any capitalised word that's not in quotes is a variable in Prolog, so they can take any value. This will give us the result:
Model = 'F150',
Year = 1999,
Colour = 'Black' ;
Press space, and we get another:
Model = 'Mustang',
Year = 1969,
Colour = 'Blue'.
And there are no more, so it returns to the REPL.
(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].
In SQL, how would you find the names of any two brands whose bicycles have the same colour? (Don't bother with the whole CSV parsing; just assume it's already a table.)
Maybe I just have particularly hard time understanding SQL, but I'd have to surf StackOverflow for at very least half an hour to do that in SQL. I wouldn't know where to start.
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):
This can be read as "What is the age of anyone, who like something?" (or more absurdly, "What does anyone, who has an age, like?", depending on what variable we focus on.)
I'm probably getting this wrong, but if we wanted LEFT OUTER JOIN it would be more like:
age(Name,Age); likes(Name, Something).
Which is more like "What's all people's ages, and what does anyone 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.
>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].
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.
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.
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:
[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]).
And this is the reply:
A = 3,
B in 1..2,
all_distinct([3, B, C]),
C in 1..2.
I can only recommend you install SWI Prolog[0] and give it a try. It's quite fun!
(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.)
A = 3,
B in 1..2,
all_distinct([3, B, C]),
C in 1..2.
you don't yet have a complete solution in which each variable is bound to a number. In fact, you don't even have a guarantee that a solution exists. To get to this point no search is necessary, but to get from this point to a guaranteed solution, you need to call a "labeling" predicate, which will do backtracking search.
> 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,
B in 1..2,
all_distinct([B, C]),
C in 1..2.
it has no unique solution seen in isolation, so search/labelling would be required; just like it would on a blank sudoku square with no hints at all.
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?
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.
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:
my_list(Ls) :-
Ls = [a,b|Rs],
Ls = [a,c|Rs].
In this example, I am using trivial constraints (only (=)/2), and the mistake is quite obvious. But the point remains: We can remove and generalize any and all goals and give explanations why a query fails.
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].
here, I have used ( * )/1 to "generalize away" a goal, using a suitable definition of ( * )/1 like:
:- op(920,fy, *). *_.
The fact that the query then succeeds tells us that the second goal is, in a sense, a reason for the failure.
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'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?
> 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.
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, ...
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]).
*/
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)
No pruning of the solution space but `all` will exit early if it can. You could change `inject` (terrible name) to pass the list of rules & call those whose signatures are fulfilled at the beginning of each for-loop, and return a list of the uncalled rules + the results of the called rules, and test the results with `all` & keep the uncalled rules handy for the next for-loop. I didn't do it because there's already too much boilerplate in the for-loops
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)
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)
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!