Solving murder with Prolog | Hacker News Reader

Solving murder with Prolog

xmonader.github.io

133 pointsyarapavan18 comments

The 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.)

I 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.

Hmm 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.

The Orwell game seems to do something very similar. It's a very impressive game, I highly recommend it.

Believe it or not, there's a book along those lines, but using BASIC:

https://www.amazon.com/Elementary-Chronicled-Learning-Comput...

They just don't make CS books like that any more.

Wow, paperback is available used for over a thousand dollars.

Good example of the Amazon algorithm going nuts, or just a really amazing old book.

Probably Amazon going nuts.

I bought it from a local used book store for $6.

As 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.

I'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

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.

These are usually known as Zebra puzzles:

https://en.wikipedia.org/wiki/Zebra_Puzzle

There's a very famous one apocryphally attributed to Einstein:

https://udel.edu/~os/riddle.html

Searching for the term "zebra puzzle" will net many results e.g.: 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

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://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!

This 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.

https://www.interviewbit.com/puzzles/

These seem cool but definitely not what I'm looking for. These all look like programming puzzles whereas I just wanted more of this kind of logic/deduction puzzle.

Devils 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?

I 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-...

I'd love to see more real world examples too.

Trivia: Erlang's syntax comes from Prolog.

And 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.

This is great. Thanks for sharing.

Reply on news.ycombinator.com