Write a Prolog program to solve the Riding Stable Puzzle:
Last Saturday, all six of the horses in Johnson Stables were rented to children for the day, all of them regulars. Each of the horses (whose names are Boris, Hunter, Lady, Ranger, Santa Fe, and Topper) lives in one of the six stalls, numbered one to six from west to east. The children included three boys (Brian, Curtis, and Roy) and three girls (Lily, Michelle, and Theresa), each a different age (15, 14, 12, 10, 9, and 7 years old).The following facts are known about the horses and the children who rode them that day:
- Topper lives two or more stalls to the east of Theresa's horse.
- The nine-year-old's horse lives somewhere to the west of Brian's horse.
- Three horses in consecutive stalls, from west to east, are Boris, Brian's horse, and the 12-year-old's horse.
- The child who rode Topper is three years older than the one who rode the horse in stall 4, while Roy is three years older than Michelle. (These are 4 different children).
- Ranger's rider is three years older than Lily, who in turn is two years older than the girl who rode Lady.
- Santa Fe lives somewhere to the west of Curtis's horse.
- Brian is just one year older than Theresa.
- Roy didn't ride the horse in stall 6.
Can you determine each horse's stall number, and the name and age of the child who rode him or her that day?
For full marks, implement your solution such that the puzzle can be solved by the query
?- solve.
In this case, your Prolog program should format the results in tabular form, with the headings and spacing illustrated in the following table.
Stall Horse Child Age
----- -------- -------- ---
1 Topper Theresa 9
2 Boris Lily 10
3 Hunter Roy 14
4 Lady Curtis 15
5 Santa Fe Brian 12
6 Ranger Michelle 7
Note that the body of this table does not constitute a correct solution to the puzzle. However, the table shows that the horses' and children's names should be left-aligned and the children's ages should be right aligned under their respective headings.
If you do not have time to do the appropriate formatting of the results, you may submit for reduced marks a program which presents the correct result as a list of sublists of the form
[[horse1, child1, age1], [horse2, child2, age2], . . . ]
This program would be invoked by querying the solve/1 predicate (i.e., a solve predicate of arity 1), as in
?- solve(S).
It would return the same data as illustrated in the table above in the following form:
[[topper, theresa, 9], [boris, lily, 10], [hunter, roy, 14], [lady, curtis, 15], [santa_fe, brian, 12], [ranger, michelle, 7]]
A program which implements solve/1 but does not correctly implement solve/0 (i.e., produce correctly formatted tabular output) will be penalized by 10%.
It is easy to convert an implementation of the solve/1 predicate to the zero-arity form: just add a top-level predicate such as the following and implement the output formatting predicates below a general predicate such as write_solution/1.
solve :-
solve(Stable),
% Write the solution in formatted form.
write_solution(Stable).
The header is easily generated using the write/1 predicate, since the argument to write can be a single-quoted constant, as in
write('This is a string constant.').
Remember that, in Prolog, the name of a constant can be capitalized and include spaces if the name is enclosed in single quotes, while a string in double quotes is equivalent to a list of integers (i.e., ASCII codes):
write("Hello").
results in
[72, 101, 108, 108, 111]
SWI Prolog also provides a writef/2 predicate which implements formatted output. For a full specification of the predicate, use Prolog's help facility:
help(writef).
The predicate resembles C's printf function in that the first argument is a format string; however, the second argument is a list of the arguments to be inserted at the points specified by escape sequences in the format string.
As an example of the use of writef,
writef('%5r', [Age]).
prints the value of the variable Age right-aligned in a field of width 5.
It would be poor design to implement write_solution/1 as a long sequence of write, writef, and nl terms, one set for each stall in the stable. Instead, it should probably format the header, then call a subsidiary predicate which would iterate through the stable (extracting the head of the list and calling itself recursively on the tail of the list until the stable is reduced to the empty list), calling another subsidiary predicate to format each line of the body of the table (each stall). The stall number could be specified by a second argument to the subsidiary predicate, which is increased by one on each recursive call.
It would no doubt be possible to write a procedure which would convert the constant names of the horses and children to appropriately formatted strings (with capital letters and spaces as appropriate); for example, Prolog's name/2 predicate can convert an atom name to a list of ASCII values. However, given the complexities of converting 'sante_fe' to "Santa Fe", for example, it is much easier and quite acceptable to use clauses such as
write_horse(santa_fe) :-
write('Santa Fe ').
or
capitalize(santa_fe, "Santa Fe").
The latter form can be used to instantiate a variable as a string, which can then be printed using the '%s' escape sequence in the format string of writef. (Unfortunately, it is not possible to specify a field size with the '%s' escape sequence, so you will have to ensure that all strings are of the same length.)
Please hand in a hardcopy listing of your solution to this assignment (to ensure that the formatting which you carefully prepared is preserved) and submit the source code for your solution using one of the following forms.
EITHER by file upload:
OR by cutting and pasting text:
Your assignment submissions are password-protected. These passwords apply only to form data submitted via the Web server. They are separate from (and typically different from) your network password or the password for your Unix account (if you have one).
Your solution should display the following characteristics as they are applicable to Prolog: correctness, logical design, reasonable efficiency, good style, internal documentation, and knowledge of the language.
The weightings of the various factors for grading will be approximately as follows:
| Correctness | 60% | |
| Design and Efficiency | 20% | |
| Style and Documentation | 20% |
Internal documentation should be "in the prescribed format" as shown on pages 114-116 of Prolog Programming in Depth.
The idiomatic use of Prolog is included under the "design" category.
Assignments will be accepted after the due date and time, but late submissions will be assessed a penalty of 1% per hour or portion of an hour.
Copyright © 2002 Jonathan Mohr