The Prolog interpreter is named `bp'. See the link from the course web page for a user manual on bp.

A so-called ``diabolic magic square'' is an n x n matrix whose cells contain the numbers 1..n^2, arranged in such a way that the cells in every row, column, and diagonal sum to (n^3 + n)/2. Diagonals are broadly defined: they include not only the major (corner-to-corner) diagonals, but the ``broken'' diagonals as well. If you imagine tiling a wall with a large number of identical copies of a diabolic magic square, every set of four cells in a line, horizontally, vertically, or diagonally, will add up to the same number.

Here is a 4x4 diabolic magic square:

         1   8  10  15  

        14  11   5   4  

         7   2  16   9  

        12  13   3   6

Program Version 1:

You are to write a Prolog program containing a predicate diabolic(L) that tests whether the list L represents the values in a 4x4 diabolic magic square (in row-major order). The square above would be represented as [1, 8, 10, 15, 14, 11, 5, 4, 7, 2, 16, 9, 12, 13, 3, 6]. You may want to create a permutation predicate to use for this task.

Program Version 2:

It turns out that there are exactly 384 distinct 4x4 diabolic magic squares. Given any one of them, the others can be created by applying combinations of five simple transformations: reflection, rotation about the center point, rotation of columns (e.g. remove the right-most column and tack it on the left), rotation of rows (remove the top row and tack it on the bottom), and one more complex convolution best described with a picture:

    A  B  C  D              A  D  H  E
    E  F  G  H      ==>     B  C  G  F
    I  J  K  L              N  O  K  J
    M  N  O  P              M  P  L  I

Your extended program should provide a diabolic predicate. If you type diabolic([1, 8, 10, 15, 14, 11, 5, 4, 7, 2, 16, 9, 12, 13, 3, 6]) the interpreter should print yes. If you type diabolic(L) it should print a diabolic magic square, and should print additional squares in response to semicolons.

Finally, your program must provide a zero-argument predicate named all that will compute and list all 384 4x4 diabolic magic squares, with no repetitions. Note that it is not acceptable, for the purposes of this assignment, to pre-compute the squares and store them in the Prolog database.

Extra Credit Suggestions

1. Pretty-print your squares (as a 4x4 grid instead of a list).
2. Have the all predicate write its results in lexicographic order.
3. Extend your code to work with larger (5x5, 6x6, etc.) squares. Note that while there are regular magic squares of all sizes, there are no diabolic NxN magic squares for N=2 mod 4. (A regular magic square sums to (n^3 + n)/2 in rows, columns, and the major diagonals, but not on the broken diagonals.)

The author of our textbook has a solution to the first part that consists of 22 rules, 16 of which describe the various row, column, and diagonal sums. His solution to the second part consists of only ten rules, but they're somewhat more complex: they use the cut, fail, not, assert, and retract. Both solutions use is for math. All of the features he used are described in chapter 11 of the text. While you are certainly welcome to search out a more complete introduction to the language, you shouldn't need it for this assignment.