H

ICS 361, Artificial Intelligence Programming

Assignment 5

In Prolog, write a program to solve the Brainbashers' marathon logic puzzle. In particular, define a functor, race(List), that will return a list, List, of the marathon contestants in finishing order with the first place runner at the head of the list, the second place runner second in the list, etc. The last place runner should be last in the list.

After successfully writing the race(Result) program, investigate whether any of the spectators' notes are redundant. That is, if you leave out a particular spectator's notes from the race program (just comment out the line for a spectator), does that lead to multiple possble finishing orders? For example, does leaving out the information from spectator 1 that "Terry Tipton finished after Lisa Limperton and Betty Brent, but before Michael Miller." lead to multiple solutions, or is there still enough information from the other spectators to limit the result to a single unique solution?

If any spectator's notes are redundant, then write a version of the race program called raceShort that gives the same answer as race, but without the redundant spectator's notes. Likewise, if leaving out any spectator's notes would lead to multiple solutions, write a version of race called raceAmbiguous that is missing that required spectator's notes leading to multiple solutions (after typing ';' after the first displayed solution).

Include a test run of your program showing all possible solutions by typing ';' until Prolog returns false for race, raceShort (if applicable), and raceAmbiguous (if applicable). Note that SWI-Prolog may nt display all of the elements of the list because it is too long. Just type 'w' to Prolog to reprint the entire answer in full (see SWI-Prolog's Help: I want the whole answer). After the first 'w', all subsequent printing will be in full (until you type a 'p' to get back to the default printing behavior).

For documentation, add a line or two for every new predicate that describes the meaning of the predicate and the relationship(s) of its arguments. Note that the start of comment character in Prolog is a %.

Hints

One of the presuppositions of the problem is that a runner cannot finish in more than one position. For example, Lisa Limperton cannot come in both first and fourth. To implement this constraint, I recommend using the Prolog permutation functor. The List result of race(List) is a permutation of the racers competing in the BrainBashers marathon. To convert the place of a contestant in List into a counting number so that you can compare the finishing positions, I recommend using nth1. For example, nth1(P, List, paulPeterson) will put the position number of paulPeterson within List into the variable P. Now you can use '<' and '>' to compare P with the finishing order of other racers.

There are 10! = 3,628,800 different race result orderings that Prolog has to try, so depending on the speed of your computer, you may have to wail a few minutes for Prolog to finish trying them all.

To save a log of your Prolog session to a file, use the protocol('mylog.txt'). predicate followed by noprotocol.

My solution for race(L) is 24 lines of code, not counting blank lines, comment lines or raceSHort/raceAmbiguous. If your solution is taking much longer, you are probably doing something wrong and should come see me for help.

Submitting

Submit by zipping together your source code files (e.g., a5.pl) and your typescript file (e.g., typescript.txt) into a5.zip and then upload a5.zip to Assignment 5 on Laulima.


David N. Chin / Chin@Hawaii.Edu