An octagon with sides of lengths 1, 2, 3, 4, 5, 6, 7, and 8, in some order, is placed within a rectangle, as illustrated below (not to scale):
+----------------+
| G |
| F|
| E |
| +---------+
| |*********|
| D|*********|
| |*********|
|H +----+****|
| C |****|
| |****|
| B|****|
| |****|
| A |****|
+-----------+----+
The problem is to choose the lengths of the sides of the octagon so that the area of the shaded hexagon is maximized.
Write a Prolog program to solve the Octagon Puzzle.
Implement your solution such that the puzzle can be solved by the query
?- solve(Max,[A,B,C,D,E,F,G,H]).
where Max is the maximal area of the shaded hexagon in the diagram above and A, B, C, ..., H correspond to the edges of the octagon as labelled in the diagram.
The following query is equivalent, where Permutation is an ordered list of edge lengths, with edges listed in the order A, B, C, ..., H.
?- solve(Max,Permutation).
While it would seem that, as with the Riding Stable Puzzle, an exhaustive generate-and-test approach would take too long, it is actually quite easy and fast to solve this puzzle by generating permutations of the integers from 1 to 8 because, by the application of constraints, there are only 36 permutations for which the area of the shaded hexagon needs to be calculated.
It is possible to solve this puzzle using any of the three approaches suggested in §6.4, "Finding the Smallest, Largest, or 'Best' Solution", pages 157-158 in the Prolog textbook.
However, I found it just as easy and fast to use assert and retract to keep track of the best solution found so far in Prolog's built-in fact database. You may find it helpful to use the if-then-else structure, discussed in §4.7, on page 99 of the textbook, in conjunction with this method. (Note that the else part is optional.) Note that in order to be able to update a fact in Prolog's fact database at run-time, the predicate must be declared to be dynamic; see §2.8, p. 42.
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 the following form.
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 © 2004 Jonathan Mohr