5 ms·
Logic Puzzles with Prolog (2017)
- ThePadawan 7y ago> Example 2: A says: "I am a knave, but B isn't." > (...code here...) > > Thus, in this example, both A and B are knaves. Under the premise that knaves always lie, if A is a knave, then their statement "I am a knave" must have been a lie, thus this solution cannot be correct.
- timon999 7y agoA isn't making two statements. The (single) statement "I am a knave, but B isn't." is a conjunction that is false because it's right hand side is false.
- ThePadawan 7y agoThank you for the clarification! Still, makes me think that this could have been stated clearly instead of relying on the reader interpreting it in that manner.
- carapace 7y agoI find the biggest challenge with these kinds of logic puzzles is in translating from the English (or other human language) into symbolic logic. It's not well-documented and bug-prone. Er, (not well-documented) /\ bug-prone. Not (not (well-documented /\ bug-prone)). Like the famous Two Guardians riddle: one always lies, the other always tells the truth, you get one question, etc. There's a translation that starts "You have a wire and a NOT gate..." in which the puzzle becomes blindingly obvious. (Details omitted so as not to spoil the puzzle for anyone.) Once you have developed a facility with the special jargon of logic puzzles and know Prolog, I've found that, while some puzzles become boring ( https://swish.swi-prolog.org/p/Boring%20Sudoku.swinb https://swish.swi-prolog.org/p/Boring%20Sudoku.swinb ), many are still interesting as an art form, much like le demo scene you could imaging puzzle scene and not be too far off metaphorically.
- deleted 7y ago[deleted]
- umvi 7y agoProlog really blows my mind. I recently released a match-burning logic puzzle app[1] based on a mensa calendar puzzle I saw and it took me a while to develop an (imperfect) solver algorithm in C#. Someone then told me that the general class of these puzzles is called "Thermometer Puzzles" and that there are a ton of Prolog-based solvers[2] out there. This class of puzzle is not mentioned in the article, but I'm truly amazed at how versatile Prolog is at solving logic puzzles with so little code. I'm guessing the Prolog compiler is super complex compared to, say, a C compiler to be able to give developers that much power. [1] https://play.google.com/store/apps/details?id=com.umvirate.embergram https://play.google.com/store/apps/details?id=com.umvirate.e... [2] https://github.com/zettca/ist.lp.thermometers/blob/master/thermometers.pl https://github.com/zettca/ist.lp.thermometers/blob/master/th...
- derefr 7y ago> I'm guessing the Prolog compiler is super complex compared to, say, a C compiler to be able to give developers that much power. Nah. Both Prolog and C do a very similar step: they walk through call-sites and function signatures in your code and check them for compatibility with each-other in a way that can constrain both the call and the function, or they fail to make a match and they rewind and try again with other constraints. The only difference is that C is only doing this unification for the types of the parameters, whereas Prolog is doing it for the parameter values. Any programming language that has static types but also has an “auto” variable type, where the type is deduced from the use-def and def-use chains that statement live in, is doing absolutely everything Prolog does, and just not exposing the power of it to you. (Hindley-Milner is an even more advanced constraint-solver than Prolog is.) (Though, to be clear, if you can program in the type system, as you can in C++, then you do get an exposure to that power, and can write many backtracking algorithms with it.)
- YeGoblynQueenne 7y agoIf I understand correctly, Hindley-Milner type inference performs unification but not resolution. So I don't think the above is correct. I don't think there's any language that has built-in SLD-resolution theorem proving that isn't a logic programming language. And Prolog is not really a constraint solver. Constraint Logic Programming languages have been implemented in Prolog but the concept of "constraint" is not built-in to Prolog.
- girzel 7y agoI've been reading this book to get an overview of Prolog: http://www.learnprolognow.org/ http://www.learnprolognow.org/. It's much better than most of the tutorials I found out there, and provides a very gentle, very thorough introduction to what might be some fairly alien programming ideas (at least, they were to me). I'm still chewing over the fact that a Prolog term looks exactly the same whether it's in a knowledge base (ie it's true), or whether you're feeding it to the prompt (ie you're asking if it's true or not). Maybe I'm just spooking myself out, but the identity of facts and queries feels reminiscent of Lisp's homoiconicity between code and data.
- tom_mellior 7y ago> Maybe I'm just spooking myself out, but the identity of facts and queries feels reminiscent of Lisp's homoiconicity between code and data. Wait until you discover Prolog's homoiconicity ;-) You can treat Prolog terms as data and also add them to the database as code and call the resulting goals like all others: ?- MyFact = f(x), assert(MyFact). MyFact = f(x). ?- f(A). A = x. ?- MyRule = (f(g(X)) :- f(X)), assert(MyRule). MyRule = (f(g(X)):-f(X)). ?- f(A). A = x ; A = g(x) ; A = g(g(x)) . That is, asserting the "data" "f(x)" and "f(g(X)) :- f(X)" behaves the same as putting the identical-looking "code" in a source file. You can also query the code and get back it back as identical-looking "data": ?- Head = f(_), clause(Head, Body). Head = f(x), Body = true ; Head = f(g(_G1014)), Body = f(_G1014). (The first of these represents the fact "f(X)." as "f(X) :- true." to make things more uniform internally.) As for what this is good for, you can use it to write your own metainterpreters that execute Prolog code in the normal way, or in some nonstandard or enhanced way, recording tracing data for example. There is a good writeup on metainterpreters at https://www.metalevel.at/acomip/ https://www.metalevel.at/acomip/