Home More Samples
```///////////////////////////////////////////////////////////////////////////////
//
// Benjamin Franklin's 8x8 Magic Square
//
// This magic square was constructed by Benjamin Franklin and first mentioned
// in a letter to Peter Collinson of England about 1752. It was subsequently
// published in Franklin's Experiments and Observations in Electricity
// (London, 1569)
//
//  52  61  4   13  20  29  36  45
//  14  3   62  51  46  35  30  19
//  53  60  5   12  21  28  37  44
//  11  6   59  54  43  38  27  22
//  55  58  7   10  23  26  39  42
//  9   8   57  56  41  40  25  24
//  50  63  2   15  18  31  34  47
//  16  1   64  49  48  33  32  17
//
// This square has Franklin's trademark, the bent diagonals. However, because
// the main diagonals do not sum correctly, it is not a true magic square.
//
// The bent diagonals can be visualized as follows:
//
//    # - - - - - - -   # - - - - - - #
//    - # - - - - - -   - # - - - - # -
//    - - # - - - - -   - - # - - # - -
//    - - - # - - - -   - - - # # - - -
//    - - - # - - - -   - - - - - - - -
//    - - # - - - - -   - - - - - - - -
//    - # - - - - - -   - - - - - - - -
//    # - - - - - - -   - - - - - - - -
//
//    - - - - - - - -   - - - - - - - #
//    - - - - - - - -   - - - - - - # -
//    - - - - - - - -   - - - - - # - -
//    - - - - - - - -   - - - - # - - -
//    - - - # # - - -   - - - - # - - -
//    - - # - - # - -   - - - - - # - -
//    - # - - - - # -   - - - - - - # -
//    # - - - - - - #   - - - - - - - #
//
//
// There are eight bent diagonals in each of the four different directions,
// note the diagonals can wrap around. In the following table each letter
// (a,b,c,d,e,f,g,h) represents one bent diagonal.
//
//    +---+---+---+---+---+---+---+---+
//    | a | b | c | d | e | f | g | h |
//    |---+---+---+---+---+---+---+---|
//    | h | a | b | c | d | e | f | g |
//    |---+---+---+---+---+---+---+---|
//    | g | h | a | b | c | d | e | f |
//    |---+---+---+---+---+---+---+---|
//    | f | g | h | a | b | c | d | e |
//    |---+---+---+---+---+---+---+---|
//    | f | g | h | a | b | c | d | e |
//    |---+---+---+---+---+---+---+---|
//    | g | h | a | b | c | d | e | f |
//    |---+---+---+---+---+---+---+---|
//    | h | a | b | c | d | e | f | g |
//    |---+---+---+---+---+---+---+---|
//    | a | b | c | d | e | f | g | h |
//    +---+---+---+---+---+---+---+---+
//
// The other three bent diagonal directions can be obtained by rotating the
// table.
//
// As any web search can show, there are various interpretations of the magic
// square rules. We summarize them as follows:
//
// 1. All half rows and half columns sum to 130. (32 constraints)
// 2. The four entries in all 2x2 subsquares sum to 130. This includes wrap
//    around cases. (64 constraints)
// 3. All bent diagonals sum to 260. (32 constraints)
//
// All in all there are 128 distinct constraints on 64 variables.
//
// In 2006 in the article published online by the Proceedings of the Royal
// Society "Enumerating the bent diagonal squares of Dr Benjamin Franklin FRS"
// by Daniel Schindel, Matthew Rempel and Peter Loly
// the authors showed there are 1,105,920 variations of his magic square.
// (http://www.physics.umanitoba.ca/news/loly_paper.pdf)
//
// The following F1 program indeed found exactly 1,105,920 solutions.
//
///////////////////////////////////////////////////////////////////////////////
//
// To execute the program, run the query
//
//     all Franklin8x8(a)
//
///////////////////////////////////////////////////////////////////////////////
//
// NOTES:
// Although the total number of solutions and individual solutions remain the
// same, the execution time and order of various individual solutions
// depends significantly on the order of the constraints. In other words, if
// you rearrange the same constraints in different order, you will get results
// in different order (and in different time). Note that the results are not
// generated evenly in time, they come in "bunches". So if you get 300 results
// in the very first minute, don't expect 30000 in 100 minutes. To generate
// all solutions, the program can run a long time. It took about four weeks
// to find all solutions, albeit as an idle low priority background task on
// a fairly slow machine.
//
// You can find the actual results (25MB zipped text file) at
//
//      www.f1compiler.com/samples/FRANKLIN8X8.zip
//
//
///////////////////////////////////////////////////////////////////////////////

Square8x8 = [0..63]->>L[1..64]
Sum :< I = 260
Sum2 :< I = Sum/2

pred Franklin8x8(a::Square8x8) iff

// An array of 64 variables of an 8x8 square

a = [ a1, a2, a3, a4, a5, a6, a7, a8,
b1, b2, b3, b4, b5, b6, b7, b8,
c1, c2, c3, c4, c5, c6, c7, c8,
d1, d2, d3, d4, d5, d6, d7, d8,
e1, e2, e3, e4, e5, e6, e7, e8,
f1, f2, f3, f4, f5, f6, f7, f8,
g1, g2, g3, g4, g5, g6, g7, g8,
h1, h2, h3, h4, h5, h6, h7, h8] &

// Constraints to to remove symmetries. These have nothing to do
// with the Benjamin Franklin's constraints.

a1 > a8 & a1 > h1 & a1 > h8 & a8 > h1 &

// The actual Benjamin Franklin's constraints for 8x8 Magic Square
// Half rows and half columns (32 constraints)

a1 + a2 + a3 + a4 = Sum2 &
b1 + b2 + b3 + b4 = Sum2 &
c1 + c2 + c3 + c4 = Sum2 &
d1 + d2 + d3 + d4 = Sum2 &
a1 + b1 + c1 + d1 = Sum2 &
a2 + b2 + c2 + d2 = Sum2 &
a3 + b3 + c3 + d3 = Sum2 &
a4 + b4 + c4 + d4 = Sum2 &
a5 + a6 + a7 + a8 = Sum2 &
b5 + b6 + b7 + b8 = Sum2 &
c5 + c6 + c7 + c8 = Sum2 &
d5 + d6 + d7 + d8 = Sum2 &
a5 + b5 + c5 + d5 = Sum2 &
a6 + b6 + c6 + d6 = Sum2 &
a7 + b7 + c7 + d7 = Sum2 &
a8 + b8 + c8 + d8 = Sum2 &
e1 + f1 + g1 + h1 = Sum2 &
e2 + f2 + g2 + h2 = Sum2 &
e3 + f3 + g3 + h3 = Sum2 &
e4 + f4 + g4 + h4 = Sum2 &
e1 + e2 + e3 + e4 = Sum2 &
f1 + f2 + f3 + f4 = Sum2 &
g1 + g2 + g3 + g4 = Sum2 &
h1 + h2 + h3 + h4 = Sum2 &
e5 + e6 + e7 + e8 = Sum2 &
f5 + f6 + f7 + f8 = Sum2 &
g5 + g6 + g7 + g8 = Sum2 &
h5 + h6 + h7 + h8 = Sum2 &
e5 + f5 + g5 + h5 = Sum2 &
e6 + f6 + g6 + h6 = Sum2 &
e7 + f7 + g7 + h7 = Sum2 &
e8 + f8 + g8 + h8 = Sum2 &

// Bent Diagonals (8 constraints for each directions)
//  8 7 6 5 4 3 2 1
//  7 6 5 4 3 2 1 8
//  6 5 4 3 2 1 8 7
//  5 4 3 2 1 8 7 6
//  5 4 3 2 1 8 7 6
//  6 5 4 3 2 1 8 7
//  7 6 5 4 3 2 1 8
//  1 7 6 5 4 3 2 1
//  <
a8 + b7 + c6 + d5 + e5 + f6 + g7 + h8 = Sum &
a7 + b6 + c5 + d4 + e4 + f5 + g6 + h7 = Sum &
a6 + b5 + c4 + d3 + e3 + f4 + g5 + h6 = Sum &
a5 + b4 + c3 + d2 + e2 + f3 + g4 + h5 = Sum &
a4 + b3 + c2 + d1 + e1 + f2 + g3 + h4 = Sum &
a3 + b2 + c1 + d8 + e8 + f1 + g2 + h3 = Sum &
a2 + b1 + c8 + d7 + e7 + f8 + g1 + h2 = Sum &
a1 + b8 + c7 + d6 + e6 + f7 + g8 + h1 = Sum &

// The four entries in every 2x2 subsquare sum to 130.
// 8x8 = 64 constraints

a1 + a2 + b1 + b2 = Sum2 &
a2 + a3 + b2 + b3 = Sum2 &
a3 + a4 + b3 + b4 = Sum2 &
a4 + a5 + b4 + b5 = Sum2 &
a5 + a6 + b5 + b6 = Sum2 &
a6 + a7 + b6 + b7 = Sum2 &
a7 + a8 + b7 + b8 = Sum2 &
a8 + a1 + b8 + b1 = Sum2 & // wrap

b1 + b2 + c1 + c2 = Sum2 &
b2 + b3 + c2 + c3 = Sum2 &
b3 + b4 + c3 + c4 = Sum2 &
b4 + b5 + c4 + c5 = Sum2 &
b5 + b6 + c5 + c6 = Sum2 &
b6 + b7 + c6 + c7 = Sum2 &
b7 + b8 + c7 + c8 = Sum2 &
b8 + b1 + c8 + c1 = Sum2 & // wrap

c1 + c2 + d1 + d2 = Sum2 &
c2 + c3 + d2 + d3 = Sum2 &
c3 + c4 + d3 + d4 = Sum2 &
c4 + c5 + d4 + d5 = Sum2 &
c5 + c6 + d5 + d6 = Sum2 &
c6 + c7 + d6 + d7 = Sum2 &
c7 + c8 + d7 + d8 = Sum2 &
c8 + c1 + d8 + d1 = Sum2 & // wrap

d1 + d2 + e1 + e2 = Sum2 &
d2 + d3 + e2 + e3 = Sum2 &
d3 + d4 + e3 + e4 = Sum2 &
d4 + d5 + e4 + e5 = Sum2 &
d5 + d6 + e5 + e6 = Sum2 &
d6 + d7 + e6 + e7 = Sum2 &
d7 + d8 + e7 + e8 = Sum2 &
d8 + d1 + e8 + e1 = Sum2 & // wrap

e1 + e2 + f1 + f2 = Sum2 &
e2 + e3 + f2 + f3 = Sum2 &
e3 + e4 + f3 + f4 = Sum2 &
e4 + e5 + f4 + f5 = Sum2 &
e5 + e6 + f5 + f6 = Sum2 &
e6 + e7 + f6 + f7 = Sum2 &
e7 + e8 + f7 + f8 = Sum2 &
e8 + e1 + f8 + f1 = Sum2 & // wrap

f1 + f2 + g1 + g2 = Sum2 &
f2 + f3 + g2 + g3 = Sum2 &
f3 + f4 + g3 + g4 = Sum2 &
f4 + f5 + g4 + g5 = Sum2 &
f5 + f6 + g5 + g6 = Sum2 &
f6 + f7 + g6 + g7 = Sum2 &
f7 + f8 + g7 + g8 = Sum2 &
f8 + f1 + g8 + g1 = Sum2 & // wrap

g1 + g2 + h1 + h2 = Sum2 &
g2 + g3 + h2 + h3 = Sum2 &
g3 + g4 + h3 + h4 = Sum2 &
g4 + g5 + h4 + h5 = Sum2 &
g5 + g6 + h5 + h6 = Sum2 &
g6 + g7 + h6 + h7 = Sum2 &
g7 + g8 + h7 + h8 = Sum2 &
g8 + g1 + h8 + h1 = Sum2 & // wrap

h1 + h2 + a1 + a2 = Sum2 &
h2 + h3 + a2 + a3 = Sum2 &
h3 + h4 + a3 + a4 = Sum2 &
h4 + h5 + a4 + a5 = Sum2 &
h5 + h6 + a5 + a6 = Sum2 &
h6 + h7 + a6 + a7 = Sum2 &
h7 + h8 + a7 + a8 = Sum2 &
h8 + h1 + a8 + a1 = Sum2 & // wrap

// Bent Diagonals (8 constraints for each directions)
//  1 8 7 6 6 7 8 1
//  2 1 8 7 7 8 1 2
//  3 2 1 8 8 1 2 3
//  4 3 2 1 1 2 3 4
//  5 4 3 2 2 3 4 5
//  6 5 4 3 3 4 5 6
//  7 6 5 4 4 5 6 7
//  8 7 6 5 5 6 7 8
//  \/
a1 + b2 + c3 + d4 + d5 + c6 + b7 + a8 = Sum &
b1 + c2 + d3 + e4 + e5 + d6 + c7 + b8 = Sum &
c1 + d2 + e3 + f4 + f5 + e6 + d7 + c8 = Sum &
d1 + e2 + f3 + g4 + g5 + f6 + e7 + d8 = Sum &
e1 + f2 + g3 + h4 + h5 + g6 + f7 + e8 = Sum &
f1 + g2 + h3 + a4 + a5 + h6 + g7 + f8 = Sum &
g1 + h2 + a3 + b4 + b5 + a6 + h7 + g8 = Sum &
h1 + a2 + b3 + c4 + c5 + b6 + a7 + h8 = Sum &

// Bent Diagonals (8 constraints for each directions)
//  8 7 6 5 5 6 7 8
//  7 6 5 4 4 5 6 7
//  6 5 4 3 3 4 5 6
//  5 4 3 2 2 3 4 5
//  4 3 2 1 1 2 3 4
//  3 2 1 8 8 1 2 3
//  2 1 8 7 7 8 1 2
//  1 8 7 6 6 7 8 1
//   /\
h1 + g2 + f3 + e4 + e5 + f6 + g7 + h8 = Sum &
g1 + f2 + e3 + d4 + d5 + e6 + f7 + g8 = Sum &
f1 + e2 + d3 + c4 + c5 + d6 + e7 + f8 = Sum &
e1 + d2 + c3 + b4 + b5 + c6 + d7 + e8 = Sum &
d1 + c2 + b3 + a4 + a5 + b6 + c7 + d8 = Sum &
c1 + b2 + a3 + h4 + h5 + a6 + b7 + c8 = Sum &
b1 + a2 + h3 + g4 + g5 + h6 + a7 + b8 = Sum &
a1 + h2 + g3 + f4 + f5 + g6 + h7 + a8 = Sum &

// Bent Diagonals (8 constraints for each directions)
//  1 2 3 4 5 6 7 8
//  8 1 2 3 4 5 6 7
//  7 8 1 2 3 4 5 6
//  6 7 8 1 2 3 4 5
//  6 7 8 1 2 3 4 5
//  7 8 1 2 3 4 5 6
//  8 1 2 3 4 5 6 7
//  1 2 3 4 5 6 7 8
//  >
a1 + b2 + c3 + d4 + e4 + f3 + g2 + h1 = Sum &
a2 + b3 + c4 + d5 + e5 + f4 + g3 + h2 = Sum &
a3 + b4 + c5 + d6 + e6 + f5 + g4 + h3 = Sum &
a4 + b5 + c6 + d7 + e7 + f6 + g5 + h4 = Sum &
a5 + b6 + c7 + d8 + e8 + f7 + g6 + h5 = Sum &
a6 + b7 + c8 + d1 + e1 + f8 + g7 + h6 = Sum &
a7 + b8 + c1 + d2 + e2 + f1 + g8 + h7 = Sum &
a8 + b1 + c2 + d3 + e3 + f2 + g1 + h8 = Sum

```