5 ms·
Solving murder with Prolog
- gavanwoolery 8y agoI always thought the deductive power of prolog would be perfect for a mystery game (it need not expose the user to the language). Or for that matter, any sort of game involving story-telling. It becomes particularly interesting when the deductions are chained 3+ levels deep.
- jayd16 8y agoHmm so maybe a game where you play as Waston collecting clues while a Prolog driven Sherlock deduces the mystery once enough information is available? Seems neat! Of course the narrative writing is still the bulk of the work.
- Something1234 8y agoThe Orwell game seems to do something very similar. It's a very impressive game, I highly recommend it.
- jlarocco 8y agoBelieve it or not, there's a book along those lines, but using BASIC: https://www.amazon.com/Elementary-Chronicled-Learning-Computer-Sherlock/dp/0394524233/ https://www.amazon.com/Elementary-Chronicled-Learning-Comput... They just don't make CS books like that any more.
- brownbat 8y agoWow, paperback is available used for over a thousand dollars. Good example of the Amazon algorithm going nuts, or just a really amazing old book.
- jlarocco 8y agoProbably Amazon going nuts. I bought it from a local used book store for $6.
- drusepth 8y agoAs I understand it, resellers will often put used books up for ridiculous prices when there aren't any other listed used books, just in case someone REALLY needs it. It's usually something more like $400-500 for a book like this, but I guess $1000+ isn't too farfetched.
- ykevinator 8y agoThis is great. Thanks for sharing.
- ams6110 8y agoTrivia: Erlang's syntax comes from Prolog.
- KMag 8y agoAnd so do the internals of its VM, being based on Warren's Abstract Machine. They did some internal experimentation and found that Prolog was nearly ideal for their use case, but the backtracking made it too easy to accidentally write O(N*N) algorithms.
- starshadowx2 8y agoI'm not a programmer but I love logic puzzles. I didn't read past the clues and wanted to see if I could solve this beforehand. I did so and it only took me an hour but I had started over early on so the actual solution was just a bit less. Here's my solution if anyone is interested - https://imgur.com/a/MQFDdXu https://imgur.com/a/MQFDdXu As an aside, does anyone have any good sites/links to logic puzzles like these? I really do enjoy spending time graphing them out and solving them.
- olooney 8y agoThese are usually known as Zebra puzzles: https://en.wikipedia.org/wiki/Zebra_Puzzle https://en.wikipedia.org/wiki/Zebra_Puzzle There's a very famous one apocryphally attributed to Einstein: https://udel.edu/~os/riddle.html https://udel.edu/~os/riddle.html Searching for the term "zebra puzzle" will net many results e.g.: https://www.brainzilla.com/logic/zebra/ https://www.brainzilla.com/logic/zebra/ They can be solved by hand, as you've noted, with vanilla Prolog using the technique in the article, or with constraint logic programming for which Prolog has a very powerful library (vanilla Prolog is just doing an exhaustive search.) https://en.wikipedia.org/wiki/Constraint_logic_programming https://en.wikipedia.org/wiki/Constraint_logic_programming http://www.swi-prolog.org/man/clpfd.html http://www.swi-prolog.org/man/clpfd.html Another approach is to translate them into an exact cover problem and feed them into a solver like DLX. https://en.wikipedia.org/wiki/Exact_cover https://en.wikipedia.org/wiki/Exact_cover https://www.geeksforgeeks.org/exact-cover-problem-algorithm-x-set-2-implementation-dlx/ https://www.geeksforgeeks.org/exact-cover-problem-algorithm-... This class of problem is NP-complete so don't feel bad if larger problems are too hard to solve - no one knows how to solve them efficiently!
- starshadowx2 8y agoThis is great, thank you. I'll give the "Einstein" one a go when I have some time. With a glance it looks like the same manual solution method as I did earlier, just with more charts.
- bunny9 8y agohttps://www.interviewbit.com/puzzles/ https://www.interviewbit.com/puzzles/
- waterhouse 8y agoThe author's interpretation of clue 2 seemed odd: % % 3. Clue 2: Barbara was either in the study or the bathroom; Yolanda was in the other. % % Which room was Barbara found in? woman(Bathroom), woman(Study), \+christine=Bathroom, \+christine=Study, \+barbara=Dining, \+barbara=Kitchen, \+barbara=Livingroom, \+barbara=Pantry, I thought, surely there's a better way to write that, a way that closely resembles the English "either a and b, or c and d". And Prolog in fact has disjunctions. (Prolog noob here, first time I've ever run a Prolog program.) Thus: (barbara=Study, yolanda=Bathroom ; barbara=Bathroom, yolanda=Study), I verified that the program still works with that change, and the performance seems equivalent. (Takes about 7 seconds to run on my 1.3Ghz fanless laptop.)
- deleted 8y ago[deleted]
- ktpsns 8y agoDevils advocate: Solving this kind of puzzles is the usual demo for showing Prolog's strengths. Are there any more-real-world-like demonstrations which problems can be solved with Prolog?
- quantisan 8y agoI used Clojure's logic programming library to write a finite state machine for solving state transitions in equity trading https://www.quantisan.com/event-driven-finite-state-machine-for-a-distributed-trading-system/#.XC0SyS2B0Wo https://www.quantisan.com/event-driven-finite-state-machine-... I'd love to see more real world examples too.