Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)
1–10 of 23 posts
Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)
#2After having spent time doing these puzzles as a child, it strikes me just now that they have a large similarity to Sudoku puzzles.
Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)
#3Seems perfectly crafted for prolog. So... I'd love to see how this compares to a solution in http://docs.racket-lang.org/racklog/
Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)
#4Seems perfectly crafted for prolog. So... I'd love to see how this compares to a solution in http://docs.racket-lang.org/racklog/
Prolog solution in Lisp, here LispWorks:
Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)
#5For an elegant and efficient solution method for this class of problems (which includes sudoku), check out donald knuths dancing links algorithm.
Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)
#6Seems perfectly crafted for prolog. So... I'd love to see how this compares to a solution in http://docs.racket-lang.org/racklog/
http://rosettacode.org/wiki/Zebra_puzzle#Racket
Clojure, using core.logic, is also there for good measure.
Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)
#7Hmm, seems like this could potentially be solved in a cool way using the amb operator. Might have to give that a shot later today.
Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)
#8After having spent time doing these puzzles as a child, it strikes me just now that they have a large similarity to Sudoku puzzles.
Interesting, they are very similar. Both are constraint satisfaction problems.
I got the algorithms from the "AI a modern Approach" book by Peter Norvig.
This is a solution to a Sudoku. https://github.com/huherto/aima3/blob/master/src/csp/Sudoku....
This is a solution to the Map Coloring problem. https://github.com/huherto/aima3/blob/master/src/csp/MapColo...
I thought I also have a solution for the Einstein riddle using this framework, but did that with a regular search. http://humbertook.blogspot.com/2010/12/resolucion-algoritmic...
Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)
#9Hmm, seems like this could potentially be solved in a cool way using the amb operator. Might have to give that a shot later today.
Definitely. For anybody interested, http://mitpress.mit.edu/sicp/full-text/sicp/book/node90.html offers a nice introduction to the amb operator.
One issue that I found when solving problems like this is that, to achieve speed, it can become necessary to use many nested lets. That could hurt readability. Nobody wants to see a line of code nested 20 tabs deep!
Re: Who owns the fish? A Common Lisp solution to "Einstein's Riddle" (2004)
#10One way to elegantly describe and solve such a problem would be Answer Set Programming.