DownloadA Constraint-Based Local Search solver for the Water Retention on Magic Squares-problem.
The problem is a very hard combinatorial optimisation problem, invented by Craig Knecht. More can be read about it at:
http://en.wikipedia.org/wiki/Water_retention_on_mathematical_surfaces
Craig's website for the problem:
http://www.knechtmagicsquare.paulscomputing.com/
The solver is mainly based on the theory and ideas from my bachelor thesis, which I wrote at Uppsala University, Sweden, for the Astra Group which does research about Constraint Programming and related technologies:
Water Retention on Magic Squares with Constraint-Based Local Search
http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-176018
I 'm posting two solvers in this project. One written in C++ which is the fastest, at least for the heavier objective functions, and a Dynadec Comet solver which lets you easily post new constraints along with the Magic-constraints.
Author: Johan Öfverstedt
Project Samples
Follow Water Retention on Magic Squares Solver
User Reviews
-
Many famous mathematicians have previously signed the magic square guest book - Ben Franklin, Euler, Planck. De La Loubere's method for constructing magic squares shows the ingenuity of a bygone era. Johan's program is the modern equivalent of the De La Loubere's method. The magic square community is ecstatic to have this capability. Check out the tribute to Durer's 1514 magic square in the Associative_magic_square wiki that this program made possible. See the adaptations being make to this code in Harry White's Bordered Magic Square website (COMPLETE utility in the download section) My suggestion for Johan's next update would be to add the capability of specifying a set pattern to be searched. Example: I tried to find the maximum retention for the 13 x 13 associative magic square. It is always fun to be the first one to find a new record with a new free program. The program uses all its time searching for the best solution .. 6928 was what I found. I put the skeleton of that pattern .. ie the lake and pond borders into the F1 compiler and was able to boost the retention to 6944. This program is going to easily produce new records but it needs a second pass refinement capability of being able to specify the pattern from the first search as the basis of a second search. Great work Johan, Thanks !