CIS 554 Prolog 1: Logic Puzzles
Fall 2014, David Matuszek
Purposes of this assignment
- To give you some experience with logic programming.
- To introduce lists in Prolog.
- To emphasize the declarative nature of Prolog. (The entire program consists of a statement of the problem, not some algorithm to solve the problem.)
General idea of the assignment
Read and understand the following program:
- It's a Tie -- I have provided a sample solution for this one, and a page of notes on how it works. Use this as a model for your own solutions. (The "main" function is
Solve two standard (commercial) logic puzzles.
- Alien Invasion
- Shutter Bugs
- Use SWI-Prolog for this assignment (and the next).
- Here's an (old) Concise Guide to Prolog which I wrote up. Still accurate, but not very pretty.
- One of my problems in solving these was spelling errors. Prolog checks for singleton variables, but there is no such check for misspelled atoms, such as
spiegel instead of
speigel. Be especially careful of this.
- These problems make unusually extensive use of the "not" operator,
\+. Here's what you need to know about this operator:
- Prolog tries to prove things, so if expression E contains unbound variables,
\+E will try to find variable bindings that will make E true.
\+ works as you would expect when all variables are completely instantiated (bound).
- While a logic puzzle may be difficult to solve, it is easy to check whether a solution is correct: Just check whether it satisfies each of the numbered rules in the problem.
- If you want to solve logic puzzles manually, here's how to do it. However, that isn't the way to do it by a computer!
Puzzles for you to solve
100 points if your program produces the correct solution. How can you tell? Just manually check whether the solution satisfies all of the conditions of the problem! (Checking a solution is much easier than finding one.)
We may deduct points if your style is egregiously bad.
Wednesday, September 10, before 6:00am. Please zip up and turn in three
files to Canvas--your two
.pl files, along with a file containing the two solutions (copy from the output area and paste them into a text file). This due date is for everyone; students adding the class late will not be given an extension. Note that I never accept email submissions.
Late penalty: 10 points per day, up to a maximum of 50 points. When grading of this assignment is completed and grades are posted (which will take an unpredictable amount of time), no further submissions will be accepted.