Re:Solving murder with Prolog
by starshadowx2 on Tuesday December 25, 2018 @05:18AM
(#18756822)
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://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!