Andrew Howroyd has been
investigating magic stars.
Email of Feb. 24, 2005. I have reformatted this slightly for improved clarity.
I have some
information on magic stars that you might be interested in.
NUMBER OF SOLUTIONS
The following are the
number of magic stars for orders from 10 to 13. My figures agree with
yours for orders 6 to 11 inclusive. The counting was done by computer
using a brute force approach with some optimizations. I have tried a
couple of different algorithms and consistently come to the same results,
and given that they also agree with yours that indicates a good chance of
10a: 10,882 (0.5
WHEN COUNTS ARE THE
The following list shows which pairs of star type have a 1-1 relation between them. This list is complete up to order 20 and has also been verified by computer search.
7b ~ 7a
Some points of interest:
All of the order 12-types are different - there are no pairs at all. Some other orders (15, 18, 20) have fewer than the full complement of pairs. Notably these orders are neither prime nor twice a prime.
The transformations between two types of the same order can be divided into two groups. Firstly there are those like 8b <-> 8a. Here the outside points are swapped with the valley points. Other transformations like 10c <-> 10a keep outside points as outside points.
The following is a formula to test if two types are paired.
Calculate 2 * step1 * step2 - step1 - step2
where step1 is the step between points of the first type (i.e. 2 for type 11a, 3 for 11b, 4 for 11c, 5 for 11d etc) and step2 is the step between points of another type to test.
Both step1 and step2
are between 2 and half the order.
Example 1: To test if
type 11b and 11d are paired
Example 2: To test if
type 8a and 8b are paired
Pick any row on the star to be transformed. If the points are A,B,C,D rearrange them to be A,C,B,D (if outside points remain outside points) or B,D,A,C (if outside points are swapped with valley points) and place the line anywhere on the target star. Now pick another line that crosses the first line at any point and transform the points as before and place the line in the only position allowed. Continue in this manner until the whole star has been transformed.
Some star types can be re-arranged other than by simple rotation / reflection to give new stars. For example, all 80 type 6 stars can be obtained from a core set of 20. Permutations do not, however, exist for all star types - in fact they are fairly rare. The main group is the sequence 6a, 10b, 14c, 18d.... The following table shows the star type vs. the number of permutations.
Type 6a 4
The fact that Type 10b has a permutation count of 16 (preceding paragraphs) explains why there are so many more 10b stars compared with 10c/10a. If numbers of permutations are factored out then the number of stars appears to increase strictly with the number of points. There are really only 20 primitive type 4 stars which is less than the number of type 7 stars (72). Similarly, if each of the 16 type 10b stars is only counted as one then the total number of type 10 stars will come in as less than the number of type 11 stars.
Other special permutations also exist for some star types.
In particular if 2 * k * k - 2k is an exact multiple of the order or one less where k is the step between outside points.
Type 12b 2
To perform the transform just use the same procedure as for transforming a star from one type to another.
There are no other general purpose transforms for orders up to 20.
Email of Feb. 26, 2005
Yes, please feel free to add my information to your web site in the way you feel best. I have absolutely no intention of starting my own web site!! Your web site is superb and is actually what got me onto exploring magic stars and squares in a bit of detail.
--- Some material deleted ---
When it comes to searching for solutions I have two separate algorithms. The one that is most interesting consists of the functions scangroup, scanblkalt and scanblkall (between lines about 700-1000). This is my second attempt: the code is quite flexible and is driven by tables that are set up in scanblkall (the main function). Because of the table driven approach, it would not be too difficult to adapt the code to other tasks.
The important ideas are:
1) the first stage (scanblkalt) searches for all solutions modulo some small number (say 5). This can be done pretty quickly as there are not too many solutions. The second stage (scangroup) then expands those into real solutions.
2) the zero is placed in a fixed position on the star. (I am numbering from zero upwards for coding simplicity). There are only two options: either it is an outside point or it is an inside point. This gives rise to a slightly different definition of a normal star than your. I always put the zero on the first outside point, or the valley point immediately to the right. In the later case, the first outside point is unlikely to be the least outside point. This optimization reduces the search by one point - which is pretty significant.
3) the order in which points are resolved has a major influence on performance. This was the down-fall of my first attempt which uses a fixed order - one that works very well for the type 10a .. type 13a etc, but deteriates rapidly for the 'b' types and can't cope with higher steps at all. This is the motivation behind the table driven strategy.
The first part of the code in 'scanblkall' puts the order the points will be processed into the array 'm_ptindex'. I have one default strategy (which also only works well for small steps - because it is similar to my first attempt), but for the types 12c, 12d and 13c I have designed custom orders. These are just my first attempts and I have not tried other plausible alternatives. If you look at the definitions for ms_order12c, ms_order12d, ms_order13c it might initially appear that there is not much logic. (and may be there is not). In defining these tables the principals I have adopted are. a) Always fill out lines with only one remaining point, before lines with only two remaining points, before lines with three remaining points. That just seems to be common sense. b) Try to get around the star in a circle so as to create an intersection with the starting line as early as possible. (this strategy is only good for step sizes that are a large percentage of the number of points). In the case of 12c this is easy as 3 lines make a triangle. In the case of 12d, I drop back one point after each line to achieve the same thing. (you probably need to look at the point order and draw it out on a bit of paper or one of your diagrams to see what is going on). The only restriction on the point order is that point zero should be the first point and the second point should be a valley point (pref the one just to the right).
Once the point processing order is defined, the next bit of code sets up the control tables. (m_row1, m_row2 and m_action) and then the code jumps into the recursive function 'scanblkalt'. In turn once scanblkalt discovers a solution modulo the group count (a small number) it jumps into the recursive function 'scangroup'. When scangroup completes it increments a counter (m_count). There are some commented out bits of code here - this is where you would add something to do anything with the solutions. For example, isSolution() tests if the solutions is valid and saveSolution() adds the solution to an array for subsequent post-processing or saves the result to a file.
My first attempt at an algorithm occupies the functions scanloop to scanall (lines 1000 - 1300). The algorithm uses a fixed point order and does not employ the modulo trick - yet this is the code that produces the incredible times for types 12a and 13a - it's also the one for the 12b and 13b, but that seems to be about the cross over point. I have not yet spent the time to understand why this algorithm hugely out performs my new improved version on the 12a/13a types. (It should not do). The main differences are:
a) uses double linked
list instead of single linked list for tracking unused available values.
As I say, I have not yet determined which of the above reasons causes the old algorithm to out perform the smart one for the type 'a' problems. I suspect there is still room for improvement on the new algorithm, but sometimes it seems easier to wait a couple of hours for processing rather than spend a couple of days tweaking.... I am sure you have been there. Getting numbers for the 14's might not be straight forward - In particular, I suspect type 14c will have about 500 million solutions (given the x64 multiplier) - this could be avoided by only counting 1 in 64, but how?
I hope the above explanation goes some way to making up for a lack of comments.
There were two attachments: Scanstar.jpx and ScanStar.java
There were two attachments to the above email: Scanstar.jpx and ScanStar.java
This descriptive text appeared at the start of the program listing in
This descriptive text appeared two-thirds of the way through the program listing in ScanStar.java.
// This block of code
is used for enumerating and counting solutions.