### Search

 Search WWW Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

Support DFF - Shop

If you shop at Amazon anyway,  consider using this link.

We receive a few cents from each purchase.  Thanks

### Support DFF - Donate

If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

(Hint: If you can wait, current year calendars are usually on sale in January.)

### Contact

 Search DelphiForFun.org only

### Problem Description

Fill in the numbers 1 through 27 in the cube layers at left so that the sum of the following 31 sets of 3 numbers each are all identical:

1. Sum of each row within each layer, (9 sums)

2. Sum of each column within each layer, (9 sums)

3.  Sum of each vertical column across layers, (9 sums)

4.  Sum of each diagonal connecting the 8 corners of the cube (4 sums).

### Background & Techniques

Magic cubes are  one of many interesting detours in the  study of magic squares.    Recall that magic squares are N x N arrays of numbers containing the numbers 1 through N2 with the property that the sum of the numbers in each row, column and diagonal have the same value.

Magic Cubes extend this idea to three dimensions.  Unfortunately,  magic cubes below order 6, have a defect;  we can't get the diagonals on the 6 cube faces to add to the magic number.  For lower order cubes, we can however build examples that have identical sums for all of the rows, columns and pillars as well as the four  diagonals that connect the 8 corners of the cube .(sometimes called triagonals).  Such cubes are called semi-perfect magic cubes.   Here's a program that generates all 192 solutions for 3 x 3 x 3 cubes.  Of  the 192 solutions,  only four are unique. The rest are rotations and reflections of these four. (48 per solution).

Much of the information on this page came from the  Internet and from a chapter in Martin Gardner's book  "Time travel and other mathematical bewilderments", Freeman, 1987.

#### Notes for programmers

The program is a fairly straightforward implementation of a brute-force exhaustive search for solutions.    I'm pretty sure that here are more efficient methods, but it is comfortable  to work from first principles.   This program does, but it will run an hour or so to find all solutions.  Higher order cubes would certainly require a more efficient algorithm.

The magic constant representing the sum of each column, row or pillar for a cube with N3 elements is (N3+1)×N÷2.  You can derive this for yourself by recalling that the sum of all of the numbers in the cube is the average number, (1+N3)÷2,  times the number of numbers, N3, giving the expression  (1+N3)×N3÷2.  This number must be divided evenly across the N layers giving the sum for each layer and be divided by N again to get the sum for each row or column in the layer.       In our order 3 case, (27+1)×3÷2 = 42.

So we start by examining all sets of 3 numbers selected from 1..27 and saving those that sum to 42.  There turn out to be 85 of these triples, ignoring order.  Each of these sets of three number can be rearranged in 6 different ways, and we'll generate the 6 permutations of each triple as we test them for inclusion in layers.

Next we'll select all possible layers of the cube, a layer is a set of  three of these triples that form a square and meet the criteria that no duplicate numbers are included and the sums of the three 1st  members of the triples, the three 2nd members and the three 3rd members all sum to the magic number.    There are nearly 71,000 of these!

Once these are generated, we can start the search for three layers meeting the final criteria to make our magic cube.  Due to the length of the search,    I implemented an automatic  save/restore procedure to allow interrupted searches to resume.   Solutions are saved to a file named MagicCube.strm and automatically restored at startup time.

In order to speed testing, I decided to generate keys for each triple and for each layer that contained 1 bits for each number that was present.  Since we have only 27 possible numbers and 32 bits in a  integer type field, there is plenty of room to do this.  We will count from the left  so the key for, say 6, would be generated as 1 shl 5  (1 shifted left 5 times) = 32.  The mask for  N is generated as 1 shl (N-1).    We can  OR these mask values for each number   with a key being constructed.  The end result is an integer that has  bits turned on for each number in the triple or layer.   Two of these keys ANDed together will produce a result of 0 of the structures represented  have no numbers in common, or non-zero if they have elements in common.

This same key generation technique is used when determining whether a particular cube is unique or some transformation (rotation or reflection) of one already found.  The trick here was to recognize that the cube corners are preserved across rotations and reflections.  So if we build  keys from  the 8 cube corners, any two with the same key will be rotations or reflections of each other.    (This would not be the case for higher order cubes though.)

The simulated 3D drawing of the cube layers was another  interesting exercise that took several hours of play to develop.    Not very elegant, but it seems to work fairly well.

Enough  chit-chat, lets get to the program.

### Suggestions for Further Explorations

 Semi perfect magic cubes can start at number other than 1.  The program was written with this generalization in mind, but I did not include a user interface to allow the starting point be changed. There must be more efficient ways of finding the solutions.  If one instance of each of the four unique types could be found, generating the other 47 variations of each type would not be too hard.   Let me know if you find or run across a better way. Higher order magic squares have received much study.  Martin Gardner reports that a 16 year-old high school student in 1971 discovered a way to generate order 8 perfect magic cubes by the millions.   There are a number of books on the topic of magic squares and lots of information on the web.  Warning: it appears that some people become addicted to magic squares and cubes (and hyper-cubes) and sacrifice all of their leisure time for the remainder of their lives to the study.

 Original Date: July 12, 2002 Modified: July 29, 2017